그래프(Graph)

그래프란?

연결되어있는 원소간의 관계를 표현한 자료구조

비선형 구조는 표현에 초점이 맞춰져있고

선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있는 반면, 

그래프 자료구조는 연결 관계에 초점이 맞춰져 있다. 

 

그래프 용어

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

 

그래프의 종류

1. 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 
   간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.
2. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다.

 

무방향 그래프의 표현방법

1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

          2 - 3
          ⎜       
      0 - 1

이를 인접 행렬, 2차원 배열로 나타내면 다음과 같다.
  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. 인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결 관계를 표현

인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장한다.
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같다.
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

 

두 방식의 비교

두 방식의 차이는 시간 vs 공간 이다.

 

인접 행렬로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다.

그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(Node²) 만큼의 공간을 사용해야 한다.

 

인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다.

따라서 연결되었는지 여부를 알기 위해서 최대 O(Edge) 만큼의 시간을 사용해야 한다.

대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(Node+Edge) 만큼의 공간을 사용하면 된다.