그래프 연결관계 - 인접 행렬, 인접 리스트

그래프 관련하여 문제를 풀다보면(가령 DFS, BFS 문제와 같은) 그래프에서 노드간의 연결관계를 저장해야 하는 경우가 있다. 이럴 때 그래프의 연결관계를 표현하는 방법이 대표적으로 두 가지가 있다.

• 인접 행렬
• 인접 리스트

---

인접 행렬

그래프에 N개의 노드가 있으면, N x N 이차원 행렬을 만들어서 노드와 노드 사이의 간선 가중치를 담는 방식이다. 그래프가 무방향 그래프이고, i노드와 j노드가 연결되어 있으며 둘 사이의 간선의 가중치가 w인 경우, graph[i][j] = graph[j][i] = w 로 나타낼 수 있다.

 

 

 

 

 

만약 그래프에 가중치가 주어지지 않은 경우에는 두 노드가 연결되어 있으면 1, 연결되어 있지 않으면 0 으로 나타내어 0과 1로만으로 연결관계를 표현할 수 있다. 혹은 boolean형으로도 표현이 가능하다.

 

 

위와 같이 그래프가 무방향 그래프인 경우에는 이차원 행렬은 대각선을 그었을 때 양쪽이 대칭을 이룬다.

graph[i][j] = graph[j][i] 가 동일하기 때문이다.

만약 그래프가 방향 그래프라면 이차원 행렬이 반드시 대칭을 이루는 것은 아니다.

 

[장점]

• 구현하기 쉽다. 이차원 배열을 만들어서 graph[시작정점][도착정점] = 둘 사이의 가중치(비용) 만 입력하면 되기 때문에 인접 리스트에 비해 구현하기 쉽다는 장점이 있다.
• 시간복잡도가 적다. i노드와 j노드 간의 연결관계를 확인하고 싶으면 graph[i][j]에 접근하면 되기 때문에 O(1)의 시간복잡도가 걸린다.

[단점]

• 차지하는 메모리가 많다. N개의 노드가 존재할 경우 총 N x N개의 배열이 필요하다. 특히 노드의 수에 비해 간선의 수가 적은 경우에는 연결관계를 나타내기 위해 불필요하게 많은 메모리가 사용되므로 비효율적이다. 위의 오른쪽 그림을 보면 이차원 배열에서 간선의 정보를 넣은 배열의 요소보다 0이 들어간 요소의 비중이 훨씬 많다. 즉, 넣어야 하는 간선 정보에 비해 많은 공간이 필요하므로 낭비가 된다.

 

 

인접 리스트

인접행렬은 행렬로 연결관계를 나타내는 것이라면, 인접리스트는 리스트로 그래프의 연결관계를 나타낸다.

그래프에 N개의 노드가 있으면, 크기가 N인 리스트 배열을 만든다. 각각의 N개의 배열은 해당 노드와 연결된 다른 노드의 정보를 저장한다.

Vector<Node>[] v = new Vector[N];

 

 

 

아래는 왼쪽의 그래프 연결관계를 인접 리스트로 나타냈을 때의 모습이다.

 

 

 

그래프에 간선의 가중치가 주어지지 않은 경우에는 리스트에 연결 노드의 번호만 넣어주면 된다.

 

 

[장점]

• 차지하는 메모리가 적다. 인접 행렬은 몇 개의 간선 정보를 나타내기 위해서 N x N 만큼의 불필요한 공간이 필요했었다. 하지만 인접 리스트는 간선의 정보만큼만 공간을 생성하면 되므로 인접 행렬에 비해 훨씬 메모리를 절약할 수 있다. 연결된 간선의 개수가 적은 경우에는 그만큼 차지하는 공간이 작으므로 인접 리스트가 유리하다.

[단점]

• 시간복잡도가 크다. i노드와 j노드 간의 연결관계를 알고 싶을 때, 인접 행렬의 경우에는 graph[i][j]를 확인하면 되었다. 하지만 인접 리스트를 사용하면 graph[i]에서 j가 존재하는지 일일이 확인을 해야하는 번거로움이 생긴다.