방향없는 그래프(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)라면 둘 중 어떤 알고리즘이 더 효율적일까? 답은 그래프의 밀도에 따라 다르다.

위와 같이 정점에 비해 간선이 많은 그래프를 밀도가 높은 그래프라고 한다. 위 그래프의 정점의 갯수는 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에서 출발하여 이동가능한 경로를 모두 탐색하는 방법은 아래와 같다. 

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개다.

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)

출처

Previous이미지를 dockerhub repo에 push하기Next방향있는 그래프(directed graph)

Last updated