그래프(Graphs)- 인접 리스트(Adjacency List)

인접 리스트는 그래프를 표현하는 또 다른 방법으로, 각 노드에 연결된 이웃 노드들을 리스트나 다른 자료구조로 저장하는 방식이다. 이 방법은 간선의 수가 적은 희소 그래프(Sparse Graph)를 표현할 때 공간 효율적이다.

 

인접 리스트의 구조

각 노드는 자신과 연결된 노드들의 리스트를 갖고 있다. 이를 위해 파이썬에서는 딕셔너리나 리스트를 활용할 수 있다.

• 키(Key): 노드를 나타낸다.
• 값(Value): 해당 노드와 연결된 노드들의 리스트이다. 리스트의 각 항목은 이웃 노드를 나타낸다.

인접 리스트 예시

다음은 4개의 노드를 가진 무방향 그래프의 예시이다.

    0 -- 1
     \\  / \\
      2 -- 3

이 그래프의 인접 리스트 표현은 다음과 같다:

{
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}

이 예시에서:

• 0번 노드는 1번과 2번 노드와 연결되어 있으므로 0: [1, 2]로 표현된다.
• 1번 노드는 0번, 2번, 3번 노드와 연결되어 있으므로 1: [0, 2, 3]로 표현된다.

 

인접 리스트의 특징

• 공간 복잡도: 인접 리스트는 노드 수를 V, 간선 수를 E라고 할 때, O(V + E)의 공간을 사용한다. 노드와 간선의 수에 비례하여 메모리를 사용하므로, 간선이 적은 희소 그래프에 적합하다.
• 시간 복잡도:
  • 두 노드 간에 간선이 존재하는지 확인하는 데는 O(V)의 시간이 걸릴 수 있다.
  • 특정 노드에 연결된 모든 이웃 노드를 탐색하는 데는 O(E)의 시간이 소요된다.

인접 리스트 구현

class AdjacencyList:
    def __init__(self):
        # 그래프를 인접 리스트로 표현하기 위해 딕셔너리를 사용합니다.
        self.list = {}

    # 간선을 추가하는 함수 (무방향 그래프)
    def add_edge(self, u, v):
        # 노드 u에 연결된 리스트에 v를 추가
        if u not in self.list:
            self.list[u] = []
        self.list[u].append(v)

        # 무방향 그래프이므로 노드 v에 u를 추가
        if v not in self.adj_list:
            self.list[v] = []
        self.list[v].append(u)

    # 간선을 제거하는 함수
    def remove_edge(self, u, v):
        # 노드 u에서 v를 제거
        if u in self.list and v in self.list[u]:
            self.list[u].remove(v)

        # 노드 v에서 u를 제거
        if v in self.list and u in self.list[v]:
            self.list[v].remove(u)

    # 특정 노드의 인접 노드 목록을 반환하는 함수
    def get_adjacent_nodes(self, u):
        # 노드 u에 연결된 모든 노드들을 반환
        if u in self.list:
            return self.list[u]
        return []

    # 그래프를 출력하는 함수
    def display(self):
        # 현재 인접 리스트를 보기 쉽게 출력합니다.
        for key in self.list:
            print(f"{key}: {self.list[key]}")

# 그래프 생성
al = AdjacencyList()

# 간선 추가
al.add_edge(0, 1)
al.add_edge(0, 2)
al.add_edge(1, 2)
al.add_edge(1, 3)
al.add_edge(2, 3)

# 그래프 출력
al.display()
'''
0: [1, 2]
1: [0, 2, 3]
2: [0, 1, 3]
3: [1, 2]
'''
# 특정 노드의 인접 노드 출력
print("0번 노드와 인접한 노드들:", al.get_adjacent_nodes(0))
# 0번 노드와 인접한 노드들: [1, 2]
print("1번 노드와 인접한 노드들:", al.get_adjacent_nodes(1))
# 1번 노드와 인접한 노드들: [0, 2, 3]

코드 설명

1. Graph 클래스: 이 클래스는 딕셔너리(self.adj_list)를 사용하여 그래프의 인접 리스트를 저장한다. 딕셔너리의 키는 노드이고, 값은 해당 노드와 연결된 이웃 노드들의 리스트이다.
2. add_edge 메서드: 노드 u와 v 사이에 간선을 추가한다. 무방향 그래프이므로 u -> v와 v -> u를 모두 리스트에 추가한다.
3. remove_edge 메서드: 노드 u와 v 사이의 간선을 제거한다.
4. get_adjacent_nodes 메서드: 특정 노드에 연결된 노드들을 반환한다.
5. display 메서드: 현재 인접 리스트를 보기 좋게 출력한다.

 

인접 리스트의 장단점

장점:

• 공간 효율성: 간선이 적은 희소 그래프의 경우, 인접 리스트는 공간을 절약할 수 있다. 노드의 수에 비해 간선이 적은 경우 인접 행렬보다 훨씬 효율적이다.
• 이웃 노드 탐색: 특정 노드의 이웃 노드들을 빠르게 탐색할 수 있다.

단점:

• 간선 존재 여부 확인: 두 노드 사이에 간선이 있는지 확인할 때는 해당 노드의 리스트를 순차적으로 탐색해야 하므로, 최악의 경우 O(V) 시간이 걸릴 수 있다.
• 인접 리스트는 그래프의 각 노드가 이웃 노드들을 리스트로 저장하는 방식이다.
• 노드가 많고 간선이 적은 그래프(희소 그래프)에 적합한 표현 방법이다.
• 간선을 추가, 제거하거나 이웃 노드를 탐색하는 작업은 효율적으로 수행할 수 있지만, 두 노드 간의 간선이 존재하는지 확인하는 데 시간이 걸릴 수 있다.

 

인접 행렬 VS 인접 리스트

1. 그래프 표현 방식

• 인접 행렬 (Adjacency Matrix): 그래프를 2차원 배열로 나타내는 방식. 행과 열은 그래프의 노드를 나타내며, 행과 열의 교차점은 두 노드 간의 간선 존재 여부를 나타낸다.
• 인접 리스트 (Adjacency List): 각 노드가 자신과 연결된 이웃 노드를 리스트 또는 배열로 저장하는 방식. 각 노드가 연결된 노드들만 저장하여 공간을 절약할 수 있다.

2. 공간 복잡도

• 인접 행렬:
  • 크기가 V x V인 이차원 배열을 사용하므로, 공간 복잡도는 항상 O(V^2)이다.
  • 간선이 적은 희소 그래프(Sparse Graph)에서는 비효율적이다.
  • 그래프의 밀도와 상관없이 모든 노드 쌍에 대해 공간이 할당되기 때문이다.
• 인접 리스트:
  • 각 노드가 자신과 연결된 노드만을 저장하므로, 공간 복잡도는 O(V + E) (V는 노드 수, E는 간선 수)이다.
  • 노드 간 간선이 적은 희소 그래프에 적합하다.

3. 시간 복잡도

• 간선 존재 여부 확인:
  • 인접 행렬: 간선이 존재하는지 확인하는 데 O(1)의 시간이 걸린다. 행렬에서 두 노드의 교차점 값을 바로 확인할 수 있기 때문이다.
  • 인접 리스트: 노드에 연결된 리스트를 순차적으로 탐색해야 하므로, 최악의 경우 O(V) 시간이 걸린다.
• 간선 추가/제거:
  • 인접 행렬: 간선을 추가하거나 제거하는 데 O(1) 시간이 걸린다. 배열의 특정 위치에 값을 넣거나 제거하면 된다.
  • 인접 리스트: 리스트에 노드를 추가하거나 제거해야 하므로, 이 작업은 O(1) (리스트의 끝에 추가) 또는 O(V) 시간이 소요될 수 있다.
• 이웃 노드 탐색:
  • 인접 행렬: 한 노드에 연결된 모든 이웃 노드를 탐색하려면 모든 열을 확인해야 하므로 O(V) 시간이 걸린다.
  • 인접 리스트: 노드에 연결된 이웃 노드만 리스트에 저장되므로, 이 노드의 이웃을 탐색하는 데 O(E) 시간이 걸린다 (E는 해당 노드에 연결된 간선 수).

4. 적합한 그래프 유형

• 인접 행렬:
  • 노드 수에 비해 간선이 많은 밀집 그래프(Dense Graph)에 적합하다.
  • 노드 간 연결이 빈번하게 이루어지는 경우, 인접 행렬이 효과적이다.
• 인접 리스트:
  • 노드 수에 비해 간선이 적은 희소 그래프(Sparse Graph)에 적합하다.
  • 간선이 적은 경우, 인접 리스트는 메모리 효율적이다.

5. 장단점 비교

특징 인접 행렬 (Adjacency Matrix) 인접 리스트 (Adjacency List)

공간 복잡도	O(V^2)	O(V + E)
간선 존재 여부 확인	O(1) (매우 빠름)	O(V) (느림)
간선 추가/제거	O(1) (빠름)	O(1) 또는 O(V) (느림)
이웃 노드 탐색	O(V) (비효율적)	O(E) (효율적)
적합한 그래프	밀집 그래프 (Dense Graph)	희소 그래프 (Sparse Graph)
구현 복잡도	상대적으로 간단	상대적으로 복잡

• 인접 행렬은 밀집 그래프에 적합하며, 노드 간의 간선이 많을 때 빠른 접근이 가능하지만, 공간 효율성이 낮다.
• 인접 리스트는 희소 그래프에 적합하며, 공간을 효율적으로 사용하지만, 노드 간의 간선 존재 여부를 확인하는 데 시간이 더 걸릴 수 있다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms