[알골90제] 63번 - 인접행렬(가중치 방향그래프) / 무방향그래프, 방향그래프

* 인접행렬은 그래프를 표현하는 방법

 

- 정점 node / vertex

- 간선 edge

- 그래프는 정점과 간선의 집합

 

 

무방향그래프 인접행렬로 만드는 법

1)

 

5 -> 정점의 개수

6 -> 간선의 개수

 

- 무방향은 1->2 / 2->1 둘다 가능함

- 2차원 배열에 그래프의 연결정보를 넣어주는 것

- 2차원 배열의 행/열 번호가 정의 번호와 1:1대응임

 

2) 배열은 전역 변수를 잡아서 0으로 초기화 시킴

3) 1,2를 읽었으면 2차원 배열의 (2.1) , (1,2) 둘다 1을 넣어줌

4) 행이 출발 정점, 열이 도착정점 

 

 

 

방향그래프 인접행렬로 만드는 법

1) 1->2로만 간다는 것, (1,2)만 체크함 

2) 2 5 는 2->5로 가는 것, (2, 5)만 체크함

반대로 체크하게 하면 암됨!

 

 

가중치 방향그래프 인접행렬로 만드는 법

(방향그래프인데, 간선에 가중치(비용)가 있는 것)

 

1) 1  2  3 => 1행에서 2행으로 가고 간선이 비용은 3이라는 뜻

2) 1행 2열에 (1,2) 간선 값(가중치) 3이 들어감

scanf("%d %d %d", &a, &b, &c); //1 2 3 읽음

map[a][b] = c;

 

3) 가중치 방향그래프의 인접행렬

 

//63번 - 인접행렬(가중치 방향그래프)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int map[51][51]; //인접행렬 : 정점의 개수 50개라고 예상

int main() {

	freopen("input.txt", "rt", stdin);
	int n, m, a, b, c; //정점의 개수 간선의 개수

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		map[a][b] = c; //a행에서 b열로 간다. 이때 간선의 비용값은 c다
		//map[a][b] = 1; //무방향 그래프일시
		//map[b][a] = 1; //무방향 그래프일시
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}