[Python] 인접 행렬과 인접 리스트

인접 행렬 & 인접 리스트

그래프에 대한 이해가 부족하다고 느껴 다시 공부를 진행하고 있다,
본 문서에서는 그래프를 코드로 구현하는 방법에 대하여 기재한다

알고리즘 문제를 접하다보면 Graph 문제를 심심치 않게 접할 수 있다.
이러한 문제들을 풀때는 현재 그래프의 모습을 모델링한 이후 푸는것이 일반적이다. 이 때 , 모델링한 그래프의 연결관계를 나타내는 방법은 크게 두가지로 나뉜다.

1. 인접 행렬

2. 인접 리스트

위 두가지 방법에 대해 순차적으로 살펴보도록 한다.

1. 인접 행렬

---

인접 행렬이란, 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다.

인접 행렬 adj[i][j] 을 아래와 같이 정의할 수 있다.

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

만일 표현하고자 하는 그래프가 방향이 없는 무향 그래프의 경우에는 노드 i에서 노드 j로 가는 길이 존재하면 노드 j에서 노드 i로 가는 길 또한 존재한다.

이러한 특성으로 인접행렬을 구현할 경우, 대각 성분을 기준으로 대칭인 성질을 갖게 된다.

장단점

---

인접 행렬의 장점은 구현이 매우 간단하다는 것이다.

또한, 노드 끼리의 연결여부를 확인하고 싶을 때는, adj[i][j]의 값이 1인지 0이지만 확인하면 되기 때문에 O(N)이라는 시간 복잡도에 확인이 가능하다는 장점이 있다.

그러나, 만일 전체 노드의 개수가 V개, 간선의 개수가 E개라고 가정해보았을때, 노드 i에 연겨된 모든 노드들에 방문을 하고자 할 경우, adj[i][1] ~ adj[i][v]까지 모두 확인해봐야 하기 때문에 노드의 갯수에 비례하는 O(V) 복잡도를 갖는다.

위 단점으로 인해 노드의 개수에 비해 간선의 개수가 훨씬 작은 그래프라면 효율은 비례하여 낮아질 것 이다.

만일 노드가 약 10000개 존재하고 각각의 노드에 연결된 간선이 많아야 23개인 그래프가 존재한다면, 특정 노드 i와 연결된 노드가 무엇인지 확인하기 위해서는 adj[i][1] ~ adj[i][10000]까지 약 10000만 번을 확인해야 한다는 문제가 발생한다.
즉, 연결된 노드 23개를 찾기 위해서 우리는 10000번의 탐색을 해야 한다는 것이다.

구현

대부분의 그래프 문제에서는 그래프를 구성하는 노드의 개수, 간선의 개수, 연결 정보가 아래와 같은 형식으로 주어진다.

4 5
1 2
1 3
1 4
2 3
3 4

이를 인접 행렬로 구현하기 위해서는 코드를 아래와 같이 작성한다.

노드의 개수와 간선의 개수를 입력받은 이후, 입력받을 간선의 개수만큼 루프를 진행하며 src, dest 노드값을 입력받는다.

from sys import stdin

node, edge = map(int, stdin.readline().split())

adj = [[0 for _ in range(node) for _ in range(node)]

for _ in range(edge):
    src, dest = map(int, stdin.readline().split())
    adj[src][dest] = 1
    adj[dest][src] = 1

무향 그래프기 때문에 노드 src에서 노드 dest로 가는 간선이 존재한다면, 역방향 또한 존재한다고 볼 수 있다.

우리는 앞서 그래프를 인접 행렬로 구현할 경우, 노드의 개수가 간선의 개수보다 많으면 많을수록 탐색을 위해 소요되는 시간이 비효율적으로 증가한다는 단점을 확인하였다.

이러한 단점을 해결하고자 하는 관점에서 착안한 방법이 인접 리스트이다.

인접 리스트

인접 리스트란, 각각의 노드에 연결된 노드들을 원소로 갖는 리스트들의 배열을 의미한다.

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

인접 리스트 또한 무향 그래프의 경우에는 본인 노드 인덱스의 리스트 내에 서로를 원소로 갖게 된다.

장단점

인접 리스트를 활용하여 그래프의 연결 관계를 저장할 경우, 인접 리스트는 인접 행렬과 달리 실제로 연결된 노드에 대한 정보만 저장하기 때문에, 모든 벡터들의 원소의 개수의 합이 간선의 개수와 동일한다는 점이 있다.

즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다.

따라서 인접 행렬이 갖는 탐색의 비효율성을 인접 리스트를 통해 극복이 가능하다.

하지만 인접 리스트 또한 단점이 존재한다.

만일 노드 i와 노드 j의 연결 여부를 알고 싶을 경우에는 어떻게 해야 할까?

adj[i] 의 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다. 이러한 경우 O(V)의 시간 복잡도를 갖게 된다. 인접 행렬은 adj[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1) 시간복잡도를 통해 확인이 가능했었다.

이러한 단점이 있기 때문에, 문제의 상황에 따라 적절한 표현 방식을 이용하여 연결 관계를 저장하는 것이 매우 중요하다고 할 수 있다.

구현

간선에 가중치가 없는 무향 그래프를 인접 리스트로 구현하는 코드는 아래와 같다.

from sys import stdin

node, edge = map(int, stdin.readline().split())

adj = = [ [] for _ in range(node)]

for _ in range(edge):
    src, dest = map(int, stdin.readline().split())
    adj[src].append(dest)
    adj[dest].append(src)

요약

• 그래프를 코드로 구현하는 방법은 크게 인접 행렬과 인접 리스트로 나뉜다.

• 인접 행렬은 구현이 쉽다는 장점이 존재하지만, 간선의 개수에 비하여 노드의 개수가 많을 경우 탐색이 비효율적이다.

• 인접 리스트는 각 노드에 연결된 노드값만을 원소로 갖는 리스트들의 집합이다.

• 인접 행렬이 갖는 단점은 인접 리스트를 통해 극복이 가능하다.

• 인접 리스트는 노드 i와 노드 v의 연결 여부를 확인하기 위해 노드 i에 연결된 노드들을 하나하나 모두 순회하며 확인해야 한다.

• 각각의 표현 방식은 장단점이 명확하기에 문제의 상황에 따라 적절한 방식을 채택하여 사용하는 것이 중요하다.