[DS] Graph 개념과 탐색방법

1. Graph

 

그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다.

 

1) 용어

• Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프
• Directed Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하는 그래프
• Weighted Graph: 가중치 그래프. 정점을 연결하는 간선에 가중치가 존재하는 그래프
• Sub Graph: 기존 그래프의 일부 정점 및 간선으로 이루어진 부분 그래프
• Degree: undirected graph 에서 각 정점에 연결된 간선의 개수. directed graph는 간선의 방향성에 따라 두가지 종류로 나뉜다.
  • outdegree: 정점에서 다른 정점으로 향하는 간선의 수
  • indegree: 다른 정점에서 해당 정점으로 향하는 간선의 수

 

2) 그래프의 구현

그래프는 주로 adjacent matrix와 adjacent list 두가지 방법으로 구현된다.

• adjacent matrix: 인접 행렬
  • 정점의 개수가 N일때, N x N 크기를 가지는 2d 배열을 통해서 그래프를 구현한다.
  • 배열의 각 element들은 edge를 의미하는데, arr[u][v] 는 u와 v 사이의 간선을 의미한다.
  • 배열의 값으로 0과 1을 주어서 간선의 유무를 표현하거나 특정 값을 주어서 간선의 가중치를 의미한다.
  • 각 정점의 연결관계를 O(1)의 시간복잡도로 파악할 수 있다.
  • 그래프 구현에 필요한 공간복잡도는 O(V^2) 이다.
• adjacent list: 인접 리스트
  • 정점의 개수가 N일때, N 크기를 가지는 linkedlist 배열을 만들어서 각 정점의 리스트를 할당하여 그래프를 구현한다.
  • 각 배열에 할당 된 linkedlist 에 해당 정점과 연결된 정점을들 추가하여서 연결관계를 구현한다.
  • 각 정점의 연결관계를 파악하기 위해서는 list를 확인해야하기 때문에 worst case의 경우 O(V)의 시간복잡도가 걸린다.
  • 공간복잡도의 경우 정점 크기의 배열과 각 정점의 간선의 수에 따른 리스트로 구현되기 떄문에 O(V + E)를 가진다.

 

2. 그래프 탐색 방법

 

그래프를 탐색하는 방법으로는 주로 dfs와 bfs를 사용한다. 두 방법은 어떤 노드를 먼저 탐색할 것인지에 따라서 구분된다.

 

1) DFS (Depth First Search)

그래프 탐색 방법 중에서 깊이를 우선적으로 탐색하는 방법이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점으로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다.

 

Stack 기반의 알고리즘으로 방문한 정점을 스택에 저장한다. 탐색을 진행하다가 인접한 정점 중 더이상 탐색하지 않은 정점이 없는 경우 스택에서 방문했던 정점을 pop 하여 해당 정점을 기준으로 다시 탐색을 진행한다. 더이상 스택에 남아있는 정점이 없는 경우 탐색을 종료한다.

 

모든 정점을 방문하기 때문에 시간복잡도는 O(V + E)가 걸린다.

 

2) BFS (Breadth First Search)

그래프의 탐색 방법 중에서 너비를 우선적으로 탐색하는 방법이다. 트리에서의 level order 와 같은 방식으로 진행된다. 그래프의 임의의 한 정점으로부터 인접한 모든 정점들을 우선으로 탐색한다.  그 다음 이전 탐색에서 탐색되었던 정점들의 인접한 정점들을 탐색하는 순서로 탐색을 진행한다.

 

Queue 기반의 알고리즘으로 인접한 정점들을 탐색하면서 큐에 정점들을 저장한다. 인접한 정점들의 탐색이 모두 완료되면 큐에서 이전 턴에 저장된 정점들을 꺼내서 각 정점의 인접한 정점들을 탐색하고 큐에 저장한다. 큐에 남아있는 정점이 없는 경우 탐색을 종료한다.

 

모든 정점을 방문하기 때문에 시간복잡도는 O(V + E)가 걸린다. 주로 최단 경로를 찾기위해서 많이 사용한다.

 

 

[reference]

- https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/?ref=ghm 

Graph Data Structure And Algorithms - GeeksforGeeks