[알고리즘/Python] 그래프 구현 - 인접 행렬과 인접 리스트

알고리즘 문제를 보다가 보면 Graph와 관련된 문제들을 매우 많이 접할 수 있다.

보통 이런 그래프와 관련된 문제를 풀때는 현재 그래프의 모습을 모델링하고 난 뒤에 문제를 푼다.

이때, 모델링한 그래프의 연결관계를 나타내는 방법에는 크게 두가지가 있다.

 

  1. 인접 행렬

  2. 인접 리스트

---

1. 인접 행렬 

그래프에서 두 노드(vertex) 사이의 연결 관계를 이차원 배열로 나타내는 방식이다.

보통 adj[][]형태로 많이 사용한다.

 adj[i][j] : 노드 i에서 j로 가는 edge가 존재할 경우 1, 아니면 0

만약 구현하고자 하는 그래프가 Undirected Graph 일때는 adj[i][j] == adj[j][i] 일것이다.

이 경우에서 인접 행렬을 구현하면 대각선을 기준으로 대칭인 성질을 가질 것이다.

 

장점 

우선 구현이 매우 간단하다.

그리고 노드끼리의 연결상태를 확인할때 adj[i][j]의 값만 확인하면 되므로 O(1)의 선형시간에 확인이 가능하다.

단점 

노드의 개수를 v개라고 할때 노드 i에 연결된 모든 노드들을 확인하고자 할때는 

adj[i][1] ~ adj[i][v]까지 모두 확인해봐야 하므로 노드 갯수만큼인 O(v)의 시간이 소요된다.

 

---

2. 인접 리스트

각각의 노드에 연결된 노드들을 원소로 갖는 리스트들의 배열을 뜻한다.

adj[i] : i번째 노드에 연결된 노드들을 원소로 가지는 리스트

 

장점

실제로 연결된 노드에 대한 정보만 저장하므로 모든 원소의 개수의 합이 edge의 개수와 동일하다

한마디로 불필요한 메모리를 사용할 필요가 없이 간선의 개수에 비례하는 메모리만 차지한다는 뜻이다.

또한 각 노드에 연결된 모든 노드들을 방문하는 경우에, 인접 리스트로 연결 관계를 구현하는 것이 시간상으로 가장 큰 이점을 가진다. 

따라서 앞으로 배울 DFS나 BFS에서는 인접 리스트로 그래프를 구현하는 것이 더 효율적이다.

 

단점

노드 i와 노드 j의 연결여부를 확인하고 싶을때, adj[i] 리스트를 모두 다 순회해서 j 원소가 존재하는지 확인해야 한다.

단지 연결여부만 확인할 뿐인데도 O(v)의 시간이 소요된다.

 

구현

인접 리스트로 그래프를 구현할때는 딕셔너리 자료형을 활용할것이다.

 

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['C', 'E'],
    'E': ['D', 'F'],
    'F': ['E'],
}

딕셔너리 자료형의 key값에는 immutable한 자료형만 올 수 있고,

                         value값에는 mutable한 자료형과, immutable한 자료형 모두 올 수 있다.

이에 기반하여 위 코드처럼 딕셔너리 자료형을 활용해서 그래프를 구현할 수 있다.