[Swift] 스터디 7주차 - 그래프 알고리즘

6/1 진행했던 스위프트 데이터 구조와 알고리즘 책의 5장 '트리 구조 기반의 알고리즘' 스터디 정리입니다!

---

1. 그래프의 개념, 그래프의 종류

2. 그래프의 표현 방식 (코드적으로)

3. 그래프 탐색 - DFS(깊이우선탐색), BFS(너비우선탐색)

---

💡 그래프(Graph)

그래프는 노드(Vertex; 꼭지점)와 노드를 연결하는 간선(Edge; 모서리)의 집합으로 이루어진 데이터 구조입니다.

 

그래프를 통해 연결되어 있는 객체들의 관계를 표현할 수 있습니다. 

그래프의 활용 예시 : SNS 에서 연결된 사람들, 지도, 지하철 노선도의 최단 경로, 선수 과목 등 ..

 

✔︎ 그래프(Graph)의 종류

1) 무방향 그래프(Undirected Graph)

노드를 연결하는 간선이 양방향성인 그래프입니다. 방향이 없다는 것은 양쪽의 방향 모두 이동할 수 있다는 의미입니다.

ex) 친구 관계 A <- - -> B

 

2) 방향 그래프(Directed Graph)

노드를 연결하는 간선에 방향성이 존재하는 그래프입니다. 간선의 끝에 방향성을 나타내는 화살표를 추가해 표시합니다.

ex) 도시를 왕복 여행할 때의 경로 A -> B -> C -> A

 

3) 가중치 그래프(Weighted Graph)

간선에 가중치나 비용 등 추가적인 정보가 매겨진 그래프입니다. 네트워크(Network) 라고도 부릅니다.

ex) 도시를 왕복 여행할 때의 경로에서, 각 경로마다 비용이 있을 때 최종 비용을 구하는 등.

---

✔︎ 연결 그래프 vs 비 연결 그래프

1) 연결 그래프(Connected Graph)

무방향 그래프에 있는 모든 노드쌍에 대해서 항상 경로가 존재하는 경우, 모든 노드가 연결된 그래프입니다.

ex) 트리는 사이클을 가지지 않는 연결 그래프

 

2) 비연결 그래프(Disconnected Graph)

무방향 그래프에서 특정 노드쌍 사이에 경로가 존재하지 않는 경우, 그래프가 전부 연결되어 있지 않는 경우입니다. 그래프가 여러 개의 부분 그래프로 구성될 수 있습니다.

 

✔︎ 사이클 vs 비순환 그래프

1) 사이클(Cycle) 

단순 경로의 시작 노드와 종료 노드가 동일한 경우, 사이클이 있다고 표현합니다.

단순 경로는 반복되는 정점이 없는 경로를 의미합니다.

 

2) 비순환 그래프(Acyclic Graph)

사이클이 없는 그래프를 비순환 그래프라고 합니다. 특정 경로에서 같은 노드를 반복할 수 없습니다.

ex) 트리는 사이클을 가지지 않는 연결 그래프

 

✔︎ 완전 그래프(Complete Graph)

완전 그래프는 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프입니다.

무방향 완전 그래프의 노드 수가 n 개라면, 간선의 수는 n * (n-1) / 2 개 입니다.

---

💡 그래프의 표현 방식

1) 구조체 / 클래스 활용

노드는 식별자, 가중치 등을 속성으로 갖는 구조체 또는 클래스로, 간선은 연결된 노드에 대한 참조값을 갖는 구조체 또는 클래스로 표현할 수 있습니다. 노드가 n개, 간선이 m개라면, O(n+m) 공간복잡도를 갖습니다.

 

2) 이웃 목록 (Adjacency list)

모든 노드는 이웃 목록을 가지고 있고, 각각의 이웃 목록에는 노드와 연결된 노드들이 포함됩니다.

@이웃 목록 A: [C], B: [C, D], C: [A, B], D: [B]

 

3) 이웃 매트릭스 (Adjacency matrix)

노드가 n개일 때, n x n 의 이차원 배열을 만들어, 두 노드를 연결하는 모서리가 있으면 1, 없으면 0 으로 표시합니다.

특정 간선의 존재 여부를 확인할 때 유용하다. 이웃 목록에 비해 더 많은 공간을 필요로 합니다.

   A B C D
A 0 0 1 0
B 0 0 1 1
C 1 1 0 0
D 0 1 0 0

 

4) 근접 매트릭스 (Incidence matrix)

행(row)은 노드로, 열(column)은 간선으로 표시하여 노드가 연결된 간선에 1을, 연결되지 않은 곳에는 0을 표시합니다.

각 행을 읽어보면, 특정 노드에 어느 간선이 연결되어 있는지 알 수 있습니다.

   1 2 3
A 1 0 0
B 0 1 1
C 1 1 0
D 0 0 1

 

💡그래프 탐색 - 깊이 우선 탐색(DFS, Depth-First Search)

특정 노드에서 시작해, 다음 분기(branch)로 넘어가기 전, 해당 분기를 완벽하게 탐색하는 방법입니다. 일반적으로 모든 노드를 방문하고자 할 때, DFS 를 사용합니다.

 

트리의 경우, 루트 노드에서 시작해 아래로 내려가 깊게 탐색하는 것입니다.

"좌측 노드 방문 -> 중앙 노드 방문 -> 우측 노드 방문" 순서로 탐색하며, 이진검색트리의 In-order tree walk 와 동일합니다.

 

 

💡그래프 탐색 - 너비 우선 탐색(BFS, Breadth-First Search )

그래프 탐색 시, 특정 노드에서 시작해 인접한 노드를 먼저 탐색합니다. 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때 BFS 를 사용합니다. BFS 는 각각의 노드를 단 한번만 방문한다는 특징이 있습니다.

 

트리의 경우, 루트 노드에서 시작해 다음 레벨의 노드를 전부 탐색한 후, 아래로 내려가는 것입니다. 

 

👩‍💻 그래프 탐색 (DFS / BFS) - 알고리즘 문제풀이

[알고리즘/Swift] 그래프탐색(DFS/BFS) - 타겟넘버, 네트워크, 단어변환, 여행경로

 

참고 링크

• https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html