<자료구조 알고리즘> 그래프 표현 1. adjacency List (인접 리스트)

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

그래프의 표현 방식

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

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

1. Adjacency List

adjacency list는 각 노드에 연결된 노드를 리스트로 저장한다.
위의 그래프를 adjacnecy list로 표현해 보자면 다음과 같을 것이다.
0: [ 1, 3 ]
1: [ ]
2: [ 0, 4 ]
3: [ 1 ]
4: [ 3 ]

구현

이는 2차원 벡터를 이용해서 구현할 수 있다. (여기서는 보기 좋으라고 각 리스트를 오름차순으로 썼지만 순서는 상관없다.)

vector<vector<int>> adj(n);
adj[0].push_back(1);
adj[0].push_back(3); //0:[1,3]
adj[2].push_back(0);
adj[2].push_back(4); //2:[0,4]
adj[3].push_back(1); //3:[1]
adj[4].push_back(3); //4:[3]

무방향 그래프

그래프가 무방향 그래프라면 양쪽 모두로 방향이 있다고 생각하고 양쪽 노드의 인접 리스트에 모두 추가해 주면 된다.

가중 그래프

그래프가 가중 그래프라면 도착 노드와 함께 가중치도 저장해 주어야 하므로 각 노드의 인접 리스트의 자료형을 pair<int,int>로 설정하여 first 값에 도착 노드, second 값에 간선의 가중치를 저장한다.

vector<vector<piar<int,int>>> adj(n);
adj[0].push_back(make_pair(1,1));
adj[0].push_back(make_pair(3,9));
adj[2].push_back(make_pair(0,4));
adj[2].push_back(make_pair(4,3));
adj[3].push_back(make_pair(1,5));
adj[4].push_back(make_pair(3,4));

 

Adjacency List의 특징

- 뒤에서 알아볼 인접 행렬 보다 공간 복잡도가 적다.
- 한 노드에서 연결된 간선을 모두 탐색하는데 유리하며 개수를 바로 알 수 있다.

for(auto node: adj[x]){ //이와 같은 코드로 x노드에서 연결된 모든 노드들을 탐색할 수 있다. }

- 두 노드가 서로 연결 되어 있는지 확인하기 위해서는 선형 시간이 필요하다. (두 노드의 인접리스트를 모두 탐색해 보아야 하기 때문)