방향없는 그래프(undirected graph)
Last updated
Last updated
정점 (vertex)
간선 (edge)
경로(path)의 길이 = 경로 내 간선의 갯수
거리(distance) = 두 정점 사이의 최단 경로 (shortest path)
임의의 두 정점 사이의 간선 유무를 행렬로 나타낸다.
두 정점 사이의 간선을 중첩 리스트로 나타낸다.
어느 한 정점과 인접한 정점을 리스트로 나타낸다.
V = 그래프 내 정점의 총 갯수
E = 그래프 내 간선의 총 갯수
Deg = 어느 한 정점의 차수 (어느 한 정점과 연결된 간선의 갯수 또는 가중치의 합)
두 정점 사이에 간선 유무
그래프 내 모든 간선 탐색
한 정점과 인접한 모든 정점 탐색
인접행렬
O(1)
O(V^2)
O(V)
간선리스트
O(E)
O(E)
O(E)
인접리스트
O(Deg)
O(E)
O(Deg)
그래프를 탐색할 때 어떤 두 알고리즘의 시간복잡도가 각각 O(V^1.5)와 O(E)라면 둘 중 어떤 알고리즘이 더 효율적일까? 답은 그래프의 밀도에 따라 다르다.
위와 같이 정점에 비해 간선이 많은 그래프를 밀도가 높은 그래프라고 한다. 위 그래프의 정점의 갯수는 7개, 간선의 갯수는 6 + 5 + 4 + 3 + 2 + 1 = 21개이므로 시간복잡도가 O(V^1.5)인 알고리즘을 쓰는 게 더 유리하다.
V ^ 1.5 = 18.52
E = 21
반면에 정점에 비해 간선이 적은 그래프를 밀도가 낮은 그래프라고 한다. 위 그래프의 정점의 갯수는 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는 총 3개다.
DFS를 활용하여 그래프 내의 connected component들을 구별할 수 있다. 아래 코드는 각 connected component에 소속된 정점들의 cc 속성에 connected component를 구별하기 위한 숫자를 저장한다.
두 정점이 같은 connected component에 있는지 여부를 출력하는 문제풀이 coursera - reachability
어떤 그래프의 connected component의 갯수를 구하는 문제풀이 cousera - connected component
출처
