[PS] 인프런 강의 - Graph 1. 그래프와 인접행렬

 

그래프 종류

 

1. 무방향 그래프 인접행렬

 

입력값 : a b

1 2

1 3

2 4

2 5

3 4

행-> 열 로, 갈 수 있다면 값1 을 집어넣는다.

 

	1	2	3	4	5
1	0	1	1	0	0
2	1	0	0	1	1
3	1	0	0	1	0
4	0	1	1	0	0
5	0	1	0	0	0

graph[a][b] = 1;

graph[b][a] = 1;

 

2. 방향 그래프 인접행렬

 

입력값 : a b

1 2

1 3

2 5

3 4

4 2

 

	1	2	3	4	5
1	0	1	1	0	0
2	0	0	0	0	1
3	0	0	0	1	0
4	0	1	0	0	0
5	0	0	0	0	0

graph[a][b] = 1;

 

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

ex) 비용

 

입력값 : a b c

1 2 2

1 3 4

2 5 5

3 4 5

4 2 2

 

	1	2	3	4	5
1	0	2	4	0	0
2	0	0	0	0	5
3	0	0	0	5	0
4	0	2	0	0	0
5	0	0	0	0	0

graph[a][b] = 1;