그래프 이론(DFS & BFS)

이번 주 알고리즘 스터디 주제는 dfs && bfs였다. 워낙 방대하고 나에게는 어려운 부분이라 그래프부터 정리를 해보려 한다.

그래프

그래프는 어떤 자료나 개념을 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다. 이 때, 정점의 위치나 간선의 순서는 그래프의 정의에 포함되지 않는다. 따라서 다른 모양임에도 같은 그래프를 표현할 수도 있다.

그래프의 종류

그래프의 정의는 위처럼 간단하지만, 표현하고자 하는 대상에 따라 여러가지 변형된 형태를 가질 수 있다. 정점이나 간선에 추가적인 속성을 부여할 수도 있고, 제약을 둘 수도 있다.

대표적으로는 방향 그래프가 있으며, 각 간선이 방향이라는 새로운 속성을 가진다.

반대로 무향 그래프는 각 간선에 방향이 없는 그래프를 뜻한다.

또한, 가중치 그래프는 각 간선마다 가중치 속성을 부여해서 각 정점사이의 거리, 비율 등의 정보를 표현하는 데 사용된다.

그림 중, 다중 그래프는 두 정점 사이에 두개 이상의 간선이 포함될 때 사용된다.

루트 없는 트리는 부모 자식의 관계가 없을 뿐 트리의 구조를 띄고 있는 무향 그래프를 말한다.

이분 그래프는 정점들을 겹치지 않는 두개의 그룹으로 나누어 서로 다른 그룹에 속한 경우에만 간선을 연결하도록 만든 것이다.

마지막으로 DAG는 사이클 없는 방향 그래프(Directed Acyclic Graph)를 줄여 말한 것이며, 한 점에서 출발해서 자기 자신으로 돌아오는 경로가 존재하지 않을 경우를 말한다.

그래프의 경로

그래프에서 경로는 가장 중요한 개념 중 하나로, 서로 연결된 간선들을 순서대로 나열한 것이다. 경로는 거쳐 가는 정점의 번호만을 사용해서 간단히 표기할 수 있다.

그래프 표현 방법

• 인접 리스트 표현
• 인접 리스트 표현은 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프로 표현한다. 리스트를 사용해서 표현하기 때문에 계산 속도가 좋지 않을 수 있다. 그러나 간선의 수에 따라 복잡도가 결정이 되므로, 간선의 수가 적다면 사용하기 좋은 방법일 수 있다. 정점의 수를 N, 간선의 수를 E라고 했을 경우, 인접 리스트의 시간 복잡도는 O(N + E)가 된다.
• 인접 행렬 표현
• 인접 행렬 표현은 2차원 배열을 이용해서 그래프의 간선 정보를 저장한다. 정점의 번호 (u, v)가 주어졌을 때, 두 정점을 잇는 간선이 있는지 한번의 접근만으로 확인할 수 있다는 장점이 있다. 그러나, 간선의 갯수와 관계없이 항상 N X N 크기의 공간을 사용하기 때문에, 정점의 갯수에 비해 간선이 적다면 복잡도 면에서 좋지 않은 결과가 나올 수 있다.
• 암시적 그래프 표현
• 그래프를 통해 문제를 풀더라도, 항상 그래프 전체를 메모리에 저장해 둘 필요는 없다. 그래프의 크기는 매우 크지만, 실제로는 일부만 사용하는 경우, 각 정점이 인접해 있는지만 확인하면 된다. 주어진 입력을 그래프로 변환하는 과정을 거칠 필요가 없다.

그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘을 그래프 탐색 알고리즘이라고 한다. 탐색 알고리즘에는 가장 널리 사용되는 방법이 '깊이 우선 탐색'과 '너비 우선 탐색'이 있다. 우선, 깊이 우선 탐색에 대해 알아보고자 한다.

깊이 우선 탐색

깊이 우선 탐색(depth-first search, DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라가는 방법이다. 이 과정을 반복하다 더이상 갈 곳이 없는 정점에 도달하게 된다면, 마지막으로 따라왔던 간선을 따라 되돌아가게 된다.

graph   # 그래프 표현
def dfs(here) : # 깊이 우선 탐색
  print("DFS visits")
  visited[here] = True
  for there in graph[here] :    # 모든 정점 순회
    if (!visited[there]) :    # 아직 방문한 적이 없다면 방문
      dfs(there)
  # 더이상 방문할 정점이 없다면, 재귀 호출을 종료하고 이전 정점으로 돌아간다.

def dfsAll() :  # 모든 정점 방문
  visited = [False] * len(graph)
  for i in range(len(graph)) :  # 모든 정점을 순회하면서 아직 방문한 적이 없다면 방문한다.
    if (!visited[i]) :
      dfs(i)

dfsAll()

깊이 우선 탐색의 시간 복잡도

깊이 우선 탐색의 시간 복잡도는 어떤 그래프를 사용하느냐의 따라 달라진다.

인접 리스트를 사용하는 경우, 한 정점마다 한 번씩 호출되므로 정확히 N번 호출이 된다. 모든 정점에 대해 dfs를 수행하고 나면 모든 간선을 정확히 한번 혹은 두번 확인함을 알 수 있다. 따라서 인접 리스트를 사용했을 때 깊이 우선 탐색의 시간 복잡도는 정점의 갯수가 N, 간선의 갯수가 E일 경우 O(N + E)의 시간 복잡도를 가진다.

인접 행렬을 사용하는 경우에도 N번 호출이 된다. 하지만 인접 행렬의 경우, dfs 내부에서 다른 모든 정점을 순회하며 두 정점 사이에 간선이 있는지 확인해야하기 때문에 한 번의 실행에 O(N)의 시간이 소요된다. 따라서 전체 시간복잡도는 O(N^2)가 된다.

오일러 서킷

오일러 서킷

[Eulerian path - Wikipedia

From Wikipedia, the free encyclopedia Trail in a graph that visits each edge once Every vertex of this graph has an even degree. Therefore, this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle. In graph theor

en.wikipedia.org](https://en.wikipedia.org/wiki/Eulerian_path)

dfs를 이용해 풀 수 있는 문제 중 유명한 문제인 오일러 서킷이다. 흔히 '한붓 그리기' 라는 이름으로도 알려져 있다. 시작점으로 되돌아오기 때문에 오일러서킷은 사이클이라고도 할 수 있다. 여기서, 모든 간선들이 전부 한번씩만 사용되지만 시작점과 도착점이 다른 경우는 오일러 경로라고 한다.

너비 우선 탐색

너비 우선 탐색은 자료구조 큐(Queue)를 이용해 어디를 방문할 것인지 기록한다. 현재 정점에서 인접한 간선들을 모두 큐에 넣어준다. 이 때, 큐에 들어갔다는 것은 방문했음을 의미한다. 현재 정점에 인접한 모든 간선을 큐에 입력했다면, 간선들 중 큐의 맨 처음 요소를 빼준 뒤, 그 요소를 정점으로 모든 인접 간선들을 큐에 넣는다. 이 동작을 반복하여 모든 정점이 방문처리 되고 큐에 요소가 존재하지 않는다면 탐색을 종료한다.

from collections import deque
graph   # 그래프 표현
q = deque    # 양방향 큐 사용
def bfs(here) : # 너비 우선 탐색
  print("DFS visits")
  visited[here] = True
  q.append(here)
  while q :    # 큐가 존재하지 않을때까지 반복
      next = q.popleft()
    for there in graph[next] :
        if (!visited[there]) :
            visited[there] = True
            q.append(there)

def bfsAll() :  # 모든 정점 방문
  visited = [False] * len(graph)
  for i in range(len(graph)) :  # 모든 정점을 순회하면서 아직 방문한 적이 없다면 방문한다.
    if (!visited[i]) :
      bfs(i)

bfsAll()

너비 우선 탐색의 시간 복잡도

너비 우선 탐색은 깊이 우선 탐색과 시간 복잡도가 동일하다. 따라서 문제의 특징에 따라 깊이 우선 탐색과 너비 우선 탐색을 적절히 사용하는것이 좋다.

출처

알고리즘 문제 해결 전략