방향없는 그래프(undirected graph)

그래프의 구성 요소

• 정점 (vertex)

• 간선 (edge)

그래프의 예시

• 경로(path)의 길이 = 경로 내 간선의 갯수

• 거리(distance) = 두 정점 사이의 최단 경로 (shortest path)

인접행렬 (adjacent matrix)

임의의 두 정점 사이의 간선 유무를 행렬로 나타낸다.

  A B C D
A 0 1 1 0
B 1 0 0 0
C 1 0 0 1
D 0 0 1 0

간선 리스트 (edge list)

두 정점 사이의 간선을 중첩 리스트로 나타낸다.

[
  (A, B),
  (A, C),
  (C, D)
]

인접 리스트 (adjacent list)

어느 한 정점과 인접한 정점을 리스트로 나타낸다.

A: [B, C]
B: [A]
C: [A, D]
D: [C]

시간복잡도

• V = 그래프 내 정점의 총 갯수

• E = 그래프 내 간선의 총 갯수

• Deg = 어느 한 정점의 차수 (어느 한 정점과 연결된 간선의 갯수 또는 가중치의 합)

	두 정점 사이에 간선 유무	그래프 내 모든 간선 탐색	한 정점과 인접한 모든 정점 탐색
인접행렬	O(1)	O(V^2)	O(V)
간선리스트	O(E)	O(E)	O(E)
인접리스트	O(Deg)	O(E)	O(Deg)

그래프의 밀도(density)

그래프를 탐색할 때 어떤 두 알고리즘의 시간복잡도가 각각 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에서 출발하여 이동가능한 경로를 모두 탐색하는 방법은 아래와 같다.

def explore(v):
    visitied[v] = True  # O(1)
    for w in adjacent_list(v):  # O(Deg)
        if not visited[w]:
            explore(w)

위 방법은 DFS(Depth First Searching)이며 어느 한 정점에서 더이상 이동할 경로가 없으면 그 전에 방문했던 정점으로 되돌아가는 백트래킹(back-tracking)을 사용한다. 인접리스트와 DFS를 이용하여 정점 v에서 이동가능한 경로를 모두 탐색할 때 시간복잡도는 O(E)다.

그래프 내의 모든 경로를 탐색하려면 아래와 같이 모든 정점의 visited를 검사하면서 방문하지 않은 정점에서 출발하는 탐색이 필요하다. 그래프 내의 모든 경로를 탐색할 경우 시간복잡도는 O(V+E)다.

for v in vertexes:  # O(V)
    if not visited[v]:
        explore(v)  #(Degree per v)

Connected component

connected component는 그래프 내에 정점들이 서로 이동가능한 경로를 가지고 있는 고립된 서브그래프라고 할 수 있다. 아래 그림에서 connected component는 총 3개다.

connected components

DFS를 활용하여 그래프 내의 connected component들을 구별할 수 있다. 아래 코드는 각 connected component에 소속된 정점들의 cc 속성에 connected component를 구별하기 위한 숫자를 저장한다.

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)

• 두 정점이 같은 connected component에 있는지 여부를 출력하는 문제풀이 coursera - reachability

• 어떤 그래프의 connected component의 갯수를 구하는 문제풀이 cousera - connected component

출처

• 코세라 알고리즘 강의