[Algorithm] 그래프

권오흠 교수님의 '영리한 알고리즘' 강좌 참고

- 그래프

G = (v, m) 으로 나타낸다.

v = 정점 수 / m = 간선 수

- 그래프 표시 방식

1. 인접행렬

v 개의 정점이 있는 그래프라고 할 때 인접행렬을 통해 나타내는 그래프는 n X n 행렬로 나타낸다. 두 정점이 연결되어있는 경우 1로 나타내고 연결되어있지 않은 경우 0 으로 표시한다.

- 시간복잡도

1. 노드 v의 모든 인접 노드 찾기 : O(n) 

    행렬에서 n 번 만큼 순회해야 모두 찾을 수 있다.

2. 노드 v1가 v2와 인접행렬인지 찾기 : O(1)

    행렬 g[v1][v2] 가 1인지 0인지만 확인하면 된다.

2. 인접리스트

정점의 집합 배열과, 인접 정점들을 연결 리스트로 나타내는 방식이다.

이 때 A 정점이 정점 B와 연결된 상태가 A 연결 리스트와 B 연결리스트에 순서만 바뀐상태로 2번 입력된다. 따라서 연결 리스트의 수는 전체 간선 m 수의 두 배가 된다.

- 시간복잡도

1. 노드 v의 인접 노드 찾기 : O(degree(v))

    degree는 정점 v의 인접리스트의 개수이다. 그 개수만큼만 순회하면 모두 찾을 수 있다.

2. 노드 v1과 v2가 인접해있는지 찾기 : O(degree(u))

 

인접 행렬과 인접리스트로 나타낼 경우의 장단점이 있으므로 상황에 맞게 사용하는 것이 좋겠다. 하지만 복잡한 알고리즘 계산이 필요할 경우 인접리스트를 사용하는게 더 효율적이 경우가 많다고 한다.

- 그래프의 순회

1. BFS ( 너비우선탐색 )

인접행렬 : O(N^2)

인접리스트 : O(N+M)

가까운 레벨에 있는 노드들 부터 탐색하는 순회 방법이다. Queue를 사용해서 구현할 수 있다. 방식은,

1. 출발점 노드를 큐에 넣는다.

2. 큐에 노드가 없어질 때 까지 반복을 시작한다.

3. 큐에서 노드를 pop 하고 해당 노드의 인접 노드들이 방문된 적이 없다면 큐에 push 한다. ( 방문했는지 확인하기 위해 visited 리스트를 사용한다.)

4. 반복이 종료되고 visited 리스트를 출력하면 방문한 노드의 순서를 확인할 수 있다.

파이썬 코드

#그래프 전체 순회 (BFS) def BFS_graph(graph, start):     q = deque([start])     visited = [start]     while q:         node = q.popleft()         for i in graph[node]:             if i not in visited:                 q.append(i)                 visited.append(i)     print(visited)   BFS_graph(graph, 1)

cs

- BFS를 이용한 최단거리 탐색

BFS는 같은 레벨에 있는 노드를 우선적으로 방문하기 때문에 이를 활용해 두 노드 사이의 최단 거리를 구할 수 있다.

- BFS 이진트리

BFS트리에서 s에서 v 까지의 경로는 s에서 v까지 가는 최단경로이다. 어떤 edge도 2개의 layer를 건너가지 않는다.  

파이썬 코드

# s에서 v 까지의 경로 출력하기 # s에서 모든 노드로의 pi를 구해뒀다는 전제 하에 def BFS_print_path(graph, s, v):     if v == s:         print(s)     elif pi[v]==-1:         print('no path from s to v exists')     else:         BFS_print_path(graph, s, pi[v])         print(v) BFS_print_path(graph, 1,8)

cs

2. DFS(깊이우선탐색)

인접한 노드의 아래 layer로 타고 들어가서 더이상 인접한 노드가 없을 때까지 깊이 들어가는 방식으로 탐색하는 순회 방식이다.

파이썬 코드

# DFS visited = [0]*(len(graph)+1) dfs_s = [] def DFS_search(G,v):     dfs_s.append(v)     visited[v] = 1     for node in G[v]:         if visited[node]==0:             DFS_search(G,node) DFS_search(graph,1) print(dfs_s)

cs