알고리즘 4주차 - 그래프

그래프

• DFS, BFS에 대해 활용하기 전에 배우는 사전 개념

• 그래프란? 연결되어 있는 정점과 정점간의 관계를 표시한 자료 구조

💡

비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다. # 출처: 스파르타코딩클럽

• 예를 들면 SNS의 관계 같은 경우가 그래프 구조일 것

💡

노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) # 출처: 스파르타코딩클럽

• 그래프는 원래 무방향 그래프 와 유방향 그래프 가 있지만 이번 수업에서는 무방향만 다룸.

💡

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

그래프의 표현 방법

• 그래프를 컴퓨터에서 표현하는 방법 두 가지
  1. 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
  2. 인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결 관계를 표현

          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(노드 + 간선)$ 만큼의 공간을 사용하면 됩니다. # 출처: 스파르타 코딩클럽