그래프와 인접행렬

그래프는 기호로 G(V,E)

V- Vertex (점)

E - edge (간선)

 

인접행렬은 그래프간의 관계를 배열로 나타낸 것

1. 무방향 그래프

방향이 없는, 양방향이라고도 볼 수 있다

 

*인접행렬 

ex. 1과 2가 이어져 있으므로

graph[1][2] = 1;

graph[2][1] = 1;

해당 점이 행과 열인 칸을 1로 채워준다

 

-행번호를 탐색해서 값이 1인 열이 행번호점과 연결된 점이라고 판별 가능

⬇️1번행에서 2,3열 값이 1이므로 그래프에서 볼 수 있듯이 1번점은 2번과 3번점과 연결되어 있음

0	1	1	0	0
1	0	0	1	1
1	0	0	1	0
0	1	1	0	0
0	1	0	0	0

 

2. 방향 그래프

이동하는 방향이 정해진 그래프

 

*인접행렬

ex. 1에서 2로 이동하는 방향이므로

graph[1][2] = 1;

 

-값 1이 있는 행에서 열로 그래프가 이동한다고 판별 가능

⬇️1행 2열 값이 1이므로 1->2라고 알 수 있다.

0	1	1	0	0
0	0	0	0	1
0	0	0	1	0
0	1	0	0	0
0	0	0	0	0

 

3. 가중치 방향그래프

방향 + 가중치가 정해진 그래프

 

*인접행렬

ex. 1에서 2로 이동하는 방향이 가중치가 2이므로

graph[1][2] = 2; (값에 1대신 가중치를 입력)

 

-특정 행에서 열로 이동하면서 값 만큼의 가중치를 가진다고 판별 가능

⬇️1행 3열 값이 4이므로 1->3 이동시 가중치가 4라는 것을 알 수 있다.

0	2	4	0	0
0	0	0	0	5
0	0	0	5	0
0	2	0	0	0
0	0	0	0	0