[자료 구조] 그래프 (Graph)

그래프란?

• 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열
  • 자료를 저장하고 꺼내는 것에 초점
• 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성
  • 표현에 초점
• 그래프 : 연결 관계에 초점

Graph

• 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex)
• 간선(Edge): 노드 간의 관계를 표시한 선
• 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

유방향 그래프 (Directed Graph)

• 방향이 있는 간선
• 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능

무방향 그래프 (Undirected Graph)

• 방향이 없는 간선

그래프의 표현 방법

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
• 인접 리스트(Adjacnecy List): 연결리스트 (Linked List) 로 그래프의 연결 관계를 표현

그래프를 인접 행렬, 2차원 배열로 나타내기

          2 - 3
          ⎜       
      0 - 1

      0  1  2  3
    0 X  O  X  X
    1 O  X  O  X
    2 X  O  X  O
    3 X  X  O  X

이를 배열로 표현하면

    graph = [
        [False, True, False, False],
        [True, False, True, False],
        [False, True, False, True],
        [False, False, True, False]
    ]

인접 리스트로 표현

• 인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장

        2 - 3
        ⎜       
    0 - 1

    0 -> 1  
    1 -> 0 -> 2  
    2 -> 1 -> 3  
    3 -> 2

• 이를 딕셔너리로 표현하면

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

이 두 방식의 차이?

👉 시간 VS 공간

• 인접 행렬으로 표현 : 연결 여부를 즉각적으로 알 수 있다.
  • 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간 사용
• 인접 리스트로 표현 : 연결 여부를 알기 위해선 각 리스트를 돌아야 함
  • 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간 사용
  • 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드 + 간선) 만큼의 공간만 사용