[AL] 4. 자료구조 (Graph)

4. 자료구조 (Graph)

1. 그래프 (Graph)
2. 그래프 탐색

 

1. 그래프 (Graph)

1.1. 그래프란?

비선형 자료구조로서, 정점의 모음 과 이 정점을 잇는 간선의 모음 간의 결합을 나타낸다.

오일러 경로 (Eulerian Tour)

• 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로를 말함
• 그래프의 모든 정점에 연결된 간선의 수가 짝수일 때만 오일러 경로가 존재함

 

1.2. 그래프 관련 용어

• 정점 (Vertex) : 위치라는 개념 (= node)
• 간선 (Edge) : 위치 간의 관계, 즉 노드를 연결하는 선
• 인접 정점 (Adjacent Vertex) : 간선으로 연결되어 있는 두 정점
• 경로 (Path) : 한 정점에서 다른 정점까지 이르는 경로
• 방향 그래프 (Directed Graph) : 간선이 방향성을 가지는 그래프
• 무방향 그래프 (Undirected Graph) : 간선에 방향성이 없는 그래프
• 차수 (Degree) : Undirected Graph 에서 각 정점에 연결된 Edge 의 개수
• 가중치 그래프 (Weight Graph) : 간선이 가중치 정보를 가지고 있는 그래프
• 부분 그래프 (Sub Graph) : 본래의 그래프 일부 정점 및 간선으로 이뤄진 그래프
• 사이클 (Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

1.3. 그래프를 구현하는 방법

인접 행렬 (Adjacent Matrix) : 정방 행렬을 사용하는 방법

해당하는 위치의 value 값을 통해서 Vertex 간의 연결 관계를 O(1) 로 파악할 수 있다. Edge 개수와는 무관하게 O(V^2) 의 공간복잡도를 갖는다.

---

• 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우 유리함

• 두 정점을 연결하는 간선의 존재 여부를 O(1) 안에 즉시 알 수 있다
• 하지만, 그래프에 존재하는 모든 간선의 수는 O(V^2) 안에 알 수 있다

 

인접 리스트 (Adjacent List) : 연결 리스트를 사용하는 방법

Vertex 의 인접 리스트를 확인해봐야 하므로 Vertex 간 연결되어있는지를 각각 확인해야한다. 공간복잡도는 O(V+E) 를 갖는다.

---

• 그래프 내에 간선의 숫자가 적은 희소 그래프(Sparse Graph) 의 경우 유리함
• 그래프에 존재하는 모든 간선의 수는 O(V+E) 안에 알 수 있다
• 하지만, 두 정점 사이에 간선의 존재 여부는 해당 정점의 차수만큼의 시간이 필요하다

 

 

2. 그래프 탐색

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 아래의 두가지 알고리즘을 기반으로 한다.

 

2.1. 깊이 우선 탐색 (DFS, Depth First Search)

'그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다' 라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 계속 탐색하여 더이상 연결되지 않은 정점이 없다면 바로 그 전 단계의 정점으로 돌아가 다른 정점으로 탐색한다. Stack 또는 재귀 를 사용하여 구현할 수 있다. 시간 복잡도는 O(V+E) 를 갖는다.

 

2.2. 너비 우선 탐색 (BFS, Breadth First Search)

'그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다' 라는 방법을 통해 탐색한다. Queue 를 사용하여 구현할 수 있다. 우선, 탐색을 시작하는 정점을 큐에 넣는다. 그리고 큐의 값을 꺼내며 해당 정점에 연결되어있는 모든 정점을 다시 큐에 넣으며 탐색을 진행한다. 시간 복잡도는 O(V+E) 를 갖는다.