[자료구조] 그래프의 표현(인접행렬, 인접리스트)

인접 행렬은 모든 노드를 표현하고 각 노드의 연결 상태를 나타낸다.

• 2차원 배열을 활용하여 그래프를 표현하는 방식

인접 리스트는 실제로 연결된 노드들만 저장하기 때문에 간선의 개수와 비례하는 만큼만 메모리를 차지한다.

• 인접 리스트를 활용하여 표현하는 방식

인접 행렬 (Adjacency Matrix)

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

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

 

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

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

---

1. 방향성 그래프 (Directed Graph)

각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장합니다.

---

2. 무방향성 그래프 (Undirected Graph)

각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장한다.

정점 u와 v사이의 간선은 arr[u][v], arr[v][u] 모두 1로 표현하기 때문에 대칭 행렬이 된다는 특징이 있다.

이 특징을 이용하여 시간을 절약하기 위해 대칭행렬의 절반만 처리하도록 할 수도 있음

---

3. 가중치 그래프(Weighted Graph)

각 정점이 인접하다면 간선의 가중치를 저장하고 그렇지 않다면 0을 저장합니다.

가중치가 0인 경우와 대비하기 위해 ∞로 표시하기도 함.

---

인접 행렬 (방향 그래프) 구현

V, E = 6, 8
edge = [0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4]

adj_matrix = [[0]*(V+1) for _ in range(V+1)]

for i in range(E):
        # 2*i와 2*i+1은 edge 리스트에서 간선 정보를 가져오기 위한 인덱스
        num1, num2 = edge[2*i], edge[2*i+1]

        # num1 정점에서 num2 정점으로의 방향성을 가진 간선이 존재함을 나타냄 
        adj_matrix[num1][num2] = 1

---

인접 행렬 (무방향 그래프) 구현

V, E = 6, 8
edge = [0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4]

adj_matrix = [[0]*(V+1) for _ in range(V+1)]

for i in range(E):
        # 2*i와 2*i+1은 edge 리스트에서 간선 정보를 가져오기 위한 인덱스
        num1, num2 = edge[2*i], edge[2*i+1]

        # 각 인덱스에 1을 할당하여 num1과 num2 사이에 간선의 존재 여부를 나타냄
        adj_matrix[num1][num2] = 1
        adj_matrix[num2][num1] = 1

---

인접 행렬의 장점

• 구현이 쉽다
• 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, indexing으로 접근하기 때문에 O(1)의 시간 복잡도를 가진다.

인접 행렬의 단점

• 전체 노드의 개수를 v개, 간선의 개수를 E개라고 하면, 노드 i에 연결된 모든 노드들에 방문하고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해봐야 하기 때문에 총 O(V)의 시간이 걸린다.
• 노드의 수에 비해 간선의 개수가 훨씬 적은 그래프면 적절하지 않다.

시간 복잡도

• 어느 두 정점(i, j)에 부속된 간선이 있는지 체크하는 연산
  • O(1)
  • 인접행렬 i행 j열을 참조하면 되기 때문
• 임의의 한 정점(i)에 인접한 정점을 찾는 연산
  • O(|V|)
  • 인접행렬에서 i행 전체에 대해 조사하면 되기 때문

공간 복잡도

• O(|V^2|)
• 노드수 x 노드수 만큼의 행렬이 필요하기 때문

---

인접 리스트 (Adjacency List)

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

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

 

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

• 인접 리스트는 그래프의 전체 노드 목록을 저장한다.
• Python에서는 하나의 노드가 키(key)가 되고, 그 노드에 인접한 노드가 값(value)이 되는 딕셔너리로 구현할 수 있다.

---

1. 방향성 그래프 (Directed Graph)

인접 목록의 길이의 합은 그래프에 있는 간선의 수와 같다.

---

2. 무방향성 그래프 (Undirected Graph)

인접 목록의 길이의 합은 그래프에 있는 간선의 수의 두배와 같다.

---

3. 가중치 그래프(Weighted Graph)

가중치 그래프에서는 가중치를 저장하기 위한 추가 필드가 필요하다.

---

인접 리스트 (방향 그래프) 구현

V, E = 6, 8
edge = [0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4]

# 인접 리스트를 생성하여 각 정점에 연결된 간선 정보를 저장할 배열
adj_list = [[] for _ in range(V+1)]

for i in range(E):
        # 현재 간선을 구성하는 시작 정점과 끝 정점을 num1, num2 변수에 할당
        # 2*i와 2*i+1은 edge 리스트에서 간선 정보를 가져오기 위한 인덱스
        num1, num2 = edge[2*i], edge[2*i+1]

        # num1 정점에 연결된 간선의 끝 정점 num2를 adj_list 리스트에 추가
        # num1 정점과 num2 정점이 방향성을 가진 간선으로 연결되어 있다는 정보를 인접 리스트에 저장
        adj_list[num1].append(num2)

---

인접 리스트 (무방향 그래프) 구현

V, E = 6, 8
edge = [0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4]

# 인접 리스트를 생성하여 각 정점에 연결된 간선 정보를 저장할 배열
adj_list = [[] for _ in range(V+1)]

for i in range(E):
        # 현재 간선을 구성하는 시작 정점과 끝 정점을 num1, num2 변수에 할당
        # 이때 2*i와 2*i+1은 edge 리스트에서 간선 정보를 가져오기 위한 인덱스
        num1, num2 = edge[2*i], edge[2*i+1]

        # num1 정점에 연결된 간선의 끝 정점 num2를 adj_list에 추가
        # 이것은 num1 정점과 num2 정점이 연결되어 있다는 정보를 인접 리스트에 저장하는 것을 의미
        adj_list[num1].append(num2)

        # 무방향 그래프이기 때문에 num2 정점에도 num1 정점을 연결된 간선의 끝 정점으로 추가
        # 이것은 num2 정점과 num1 정점이 연결되어 있다는 정보를 인접 리스트에 저장하는 것을 의미
        adj_list[num2].append(num1)

---

인접 리스트의 장점

• 실제 연결된 노드에 대한 정보만 저장하기 때문에, 모든 원소의 개수의 합이 간선의 개수와 동일하다.
• 즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다.
• 각 노드에 연결된 모든 노드들을 방문해 보아야 하는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다.

인접 리스트의 단점

• 노드 i와 j의 연결 여부를 알고 싶을 때, adj[i] 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다 → 시간 복잡도 O(V)
• 인접 행렬은 adj[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1)로 확인 가능하다.

시간 복잡도

• 어느 두 정점(i, j)에 부속된 간선이 있는지 체크하는 연산
  • O(d) (d=degree(i))
  • 정점 i에 있는 연결리스트를 순회하면서 j를 찾으면 되기 때문
• 임의의 한 정점(i)에 인접한 정점을 찾는 연산
  • O(d) (d= degree(i))
  • 정점 i에 있는 연결리스트를 순회하면 되기 때문

공간 복잡도

• O(|V|+|E|)
• 정점의 수만큼 공간이 필요하고 인접한 정점을 저장하기 위해 간선 수만큼의 추가 공간이 필요하기 때문