<자료구조 알고리즘> 그래프 표현 2. adjacency Matrix (인접 행렬)

그래프가 무엇인지 모르시는 분들은 아래 글을 참고하길 바랍니다.
https://jjoonleo.tistory.com/11

<자료구조 알고리즘> 그래프 개념

그래프의 표현 방식

이번 글에서는 그래프의 표현 방식에 대해 알아 보도록 하겠다.
그래프는 배열이나 큐 스택과는 다르게 어떻게 구현해야 할지 바로 떠오르지는 않는 것 같다.(나만 그랬나??)
그래프의 표현 방식에는 3가지가 있다.

1. Adjacency List (인접 리스트)
2. Adjacency matrix (인접 행렬)
3. edge list (간선 리스트)

 

 

2. Adjacency Matrix

Adjacency Matrix는 두 노드 사이에 정점이 있는지 없는지를 2차원 배열에 저장한다.
즉 정점 x에서 y로 가는 간선이 있다면 adj[x][y] 의 값이 1 없다면 0이 된다. 또한 ajd[x][x]는 항상 0이다.
위의 그래프를 adjacency matrix로 나타낸다면 다음과 같을 것이다.

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

이는 2차원 벡터를 이용해서 구현할 수 있다.
노드의 개수 * 노드의 개수 크기의 2차원 벡터를 만들고 각 간선의 양 끝 노드에 대한 정보 x y가 주어지면 adj[x][y]값을 1로 해주면 되기 때문에 구현이 굉장히 쉽다.
(구현이라고 할게 없어서 코드를 적진 않겠다.)

 

반응형

 

무방향 그래프

그래프가 무방향 그래프라면 양쪽 모두로 방향이 있다고 생각하고 adj[x][y]와 adj[x][y]를 모두 1로 수정해 주면 된다.
그래서 결론적으로 무방향 그래프의 adjency matrix는 x=y인 대각선에 대칭인 모양을 가지게 된다.
위의 그래프가 무방향이라고 가정하고 행렬을 만들어 보면 빨간색을 기준으로 양쪽이 대칭임을 알 수 있다.
(그 말은 굳이 양쪽을 모두 쓰지 않고 x<y인 한 쪽만 사용해도 된다는 이야기이다.)

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

 

가중 그래프

그래프가 가중 그래프라면 도착 노드와 함께 가중치도 저장해 주어야 하므로 1대신 가중치 값을 저장해 주면 된다.

0	1	0	9	0
0	0	0	0	0
4	0	0	0	3
0	5	0	0	0
0	0	0	4	0

Adjacency Matrix의 특징

- 구현이 매우 매우 간단하다.
- 특정 두 노드가 인접한지를 상수 시간에 알아낼 수 있다.

- 간선과 상관없이 노드 개수^2의 메모리를 필요로 하므로 메모리 낭비가 너무 심하다. 정점이 100개이고 간선이 1개인 그래프가 있다고 하면 adjacency list에 저장하면 간선 하나만 저장하면 되지만 adjacency matrix에 저장하려면 100*100의 배열을 사용해야 한다.
- 특정 노드와 연결된 정점들을 탐색하고자 할 때 모든 노드를 살펴보아야 한다.( adjacency list는 간선의 개수 만큼만 보면 된다.)