그래프를 탐색할 때 어떤 두 알고리즘의 시간복잡도가 각각 O(V^1.5)와 O(E)라면 둘 중 어떤 알고리즘이 더 효율적일까? 답은 그래프의 밀도에 따라 다르다.
densed graph
위와 같이 정점에 비해 간선이 많은 그래프를 밀도가 높은 그래프라고 한다. 위 그래프의 정점의 갯수는 7개, 간선의 갯수는 6 + 5 + 4 + 3 + 2 + 1 = 21개이므로 시간복잡도가 O(V^1.5)인 알고리즘을 쓰는 게 더 유리하다.
V ^ 1.5 = 18.52
E = 21
sparsed graph
반면에 정점에 비해 간선이 적은 그래프를 밀도가 낮은 그래프라고 한다. 위 그래프의 정점의 갯수는 8개, 간선의 갯수는 9개이므로 시간복잡도가 O(E)인 알고리즘을 쓰는 게 더 유리하다.
V^1.5 = 22.62
E = 9
그래프의 경로탐색
어느 한 정점에서 1개 이상의 간선을 통해 다른 정점으로 이동하는 것을 경로탐색이라 한다. 어느 한 정점의 인접리스트를 구하는 함수가 adjacent_list()일 때 정점 v에서 출발하여 이동가능한 경로를 모두 탐색하는 방법은 아래와 같다.
위 방법은 DFS(Depth First Searching)이며 어느 한 정점에서 더이상 이동할 경로가 없으면 그 전에 방문했던 정점으로 되돌아가는 백트래킹(back-tracking)을 사용한다. 인접리스트와 DFS를 이용하여 정점 v에서 이동가능한 경로를 모두 탐색할 때 시간복잡도는 O(E)다.
그래프 내의 모든 경로를 탐색하려면 아래와 같이 모든 정점의 visited를 검사하면서 방문하지 않은 정점에서 출발하는 탐색이 필요하다. 그래프 내의 모든 경로를 탐색할 경우 시간복잡도는 O(V+E)다.
Connected component
connected component는 그래프 내에 정점들이 서로 이동가능한 경로를 가지고 있는 고립된 서브그래프라고 할 수 있다. 아래 그림에서 connected component는 총 3개다.
connected components
DFS를 활용하여 그래프 내의 connected component들을 구별할 수 있다. 아래 코드는 각 connected component에 소속된 정점들의 cc 속성에 connected component를 구별하기 위한 숫자를 저장한다.
def explore(v):
visitied[v] = True # O(1)
for w in adjacent_list(v): # O(Deg)
if not visited[w]:
explore(w)
for v in vertexes: # O(V)
if not visited[v]:
explore(v) #(Degree per v)
cc = 1
for v in vertexs:
if not visited[v]:
explore(v, cc)
cc += 1
def explore(v, cc):
visited[v] = True
cc[v] = cc
for w in adjacent_list(v):
explore(w, cc)
