[ 그래프(Graph) ]

그래프(Graph)는 특정 개체들이 연결된 관계를 표현하기 위해 노드(Node)와 연결(Edge)로 만들어진 자료구조이다. 지하철역들이 연결된 노선 모습이나, 게임 내의 스테이지의 연결 상태 등을 나타내는데 사용할 수 있다.

※ Nostale이라는 게임 일부의 지도를 그래프로 표현한 것이다.

[ 구성 요소 ]

그래프는 노드(Node)와 연결(Edge)로 구성되어 있다.

• 노드(Node)
  위에서 언급한 지하철역, 스테이지 등의 개체를 의미한다. Node는 독립된 개체로서 여러 가지 정보를 담을 수 있다. (위 그림의 경우 각 Node는 Clear 여부를 나타내고 있다.)
• 연결(Edge)
  노드(Node)들을 연결하는 선이다. 연결/비연결 상태만을 표시할 수도 있고, 연결 상태를 구분하기 위해 값을 가질 수도 있다. (위 그림의 경우 각 Edge는 이동 통로의 상태를 경로, 잠금, 잠금 해제, 경로 없음 등으로 구분하고 있다.)

Node는 독립되어 있기 때문에 정의한 개체의 배열을 통해 간단하게 구현하지만, Node들의 관계를 나타내는 Edge를 어떻게 구성하냐에 따라 동작 방식과 효율이 달라진다.

[ 2차 배열을 이용한 연결(Edge) 표현 ]

N개의 Node를 가지는 그래프는 N x N의 행렬로 표현할 수 있다. 행렬을 보면 행을 출발 Node, 열을 목적 Node로 두고 바로 갈 수 있는지 표시하였다. (색칸은 True, 빈칸은 False)

※ 위 행렬의 경우 0에서는 1, 2로 갈 수 있다.

[ 그래프 양상 ]

• 방향성이 없을 때
  경우에 따라서 화살표가 필요 없는 그래프도 있다. 갔던 길로 돌아올 수 있는 좀 더 직관적인 형태이다.
  
  방향성이 없다면 그래프 행렬은 대각선으로 대칭 모양을 띌 것이다. 이는 A에서 B로 갈 수 있다면, B에서도 A로 갈 수 있기 때문이다.
• 경로의 가중치가 다를 때
  경로마다 필요한 비용(cost) 또는 가중치(weight)가 다른 경우도 있다.
  
  이때는 bool 값 대신 가중치 값을 저장하여 구현한다.

[ List를 배열을 이용한 연결(Edge) 표현 ]

Node마다 연결된 Node들의 번호를 리스트로 저장하는 방식이다. 이 방법은 연결되지 않은 부분은 무시하고 연결된 Edge만 저장한다.

각 Node마다 연결된 Node의 인덱스를 담은 리스트를 가지고 있다. 이는 list 대신 vector(동적 배열)을 사용할 수도 있다. Edge의 개수에 맞춰 저장할 수 있다는 것이 핵심이다.

※ 헷갈리지 말아야 할 것이 가장 위에 있는 리스트의 경우 1번 Node에서 2번 Node로 연결되어 있다는 것이 아니다. 0번 Node에서 1번 Node와 2번 Node로 연결되어 있다는 의미이다.

[ 장단점 비교 ]

그럼 이제 Graph의 Edge를 2차원 배열을 이용해 구현할 때와 List 배열을 이용해 구현할 때의 장단점을 비교해보자.
Node의 개수를 N이라 하자.

• 연결 확인
  단순히 특정 두 Node가 연결되어 있는지 확인하는 작업이다.

  • 2차원 배열
    x번 Node에서 y번 Node로 연결되어 있는지 확인하려면 Edge[x][y]만 확인해 보면 되므로 시간 복잡도는 O(1)이다.
  • List 배열
    x번 Node에서 y번 Node로 연결되어 있는지 확인하려면 y이 나올 때까지 Edge[x]의 리스트 멤버를 순회해야 한다. 따라서 시간 복잡도는 O(N)이 된다.

• 순회
  특정 Node에 연결된 모든 Node를 찾는 작업이다.

  • 2차원 배열
    Node X에 연결된 Node를 모두 확인하려면 Edge[x][0] ~ Edge[x][n - 1]을 모두 확인해야 하므로 N번의 확인이 필요하다. O(N)
  • List 배열
    Edge[x]의 모든 멤버를 순회하면 된다. 모두 연결되어 있을 경우 N번 확인해야 하므로 O(N)이지만, Edge가 적을 경우 훨씬 효율적이다.
• 메모리
  2차원 배열로 Edge를 표현할 경우 연결된 부분과 연결되지 않은 부분 모두 표현하기 때문에 항상 (N*N) * Size의 메모리가 필요하다. Node가 많고 Edge가 적은 경우에 낭비가 심하다. 이 경우에는 List 배열을 이용하면 메모리 비용이 훨씬 줄어든다.