자료구조 알고리즘 그래프란??

그래프란?

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조.

 

저번에 트리를 배우면서 배웠던 "비선형 구조" 에 대해 기억 나시나요?

비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데,

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

비선형구조는 표현에 초점이 맞춰져 있습니다.

이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다.

페이스북을 예시로 들어볼게요! 제가 친구 "제니"를 알고 있고, "로제"와 친합니다.

그리고 "로제"는 트와이스 "사나"를 안다고 하면, 저는 "사나"와 2촌 관계라고 말할 수 있겠죠!

 

그래프에서 사용되는 용어들을 정리해드리면 다음과 같습니다!

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.

간선(Edge): 노드 간의 관계를 표시한 선.

인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

예시를 한 번 들어보겠습니다!

 

                                로제 - 사나

                                  ⎜

                      제니 - 르탄

 

르탄이는 연결 관계를 가진 데이터, 노드입니다!

르탄과 제니는 간선으로 연결되어 있습니다.

르탄과 로제는 인접 노드 입니다!

 

이런 그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있습니다!

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

2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현

더 쉽게 표기하기 위해서 각 노드들에 번호를 매겨보겠습니다!

제니를 0, 르탄을 1, 로제를 2, 사나를 3 라고 하겠습니다.

 

          2 - 3
          ⎜       
      0 - 1

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. 이번에는 인접 리스트로 표현해보겠습니다!
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

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(노드^2) 만큼의 공간을 사용해야 합니다.

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

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

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