[자료구조] 그래프와 순회(BFS, DFS)

자료구조는 크게 두 종류로 나뉜다.

선형 구조와 비선형 구조가 바로 그것이다. 비선형 구조에 속하는 그래프를 소개해 보고자 한다.

 

그래프란?

그래프는 비선형적 자료 구조로, 한정된 Node들 사이에 간선으로 연결된 형태들로 구성된 것들의 집합이다.

일반적으로 그래프를 G, node를 V, 간선을 E라고 한다.

그래프 사이의 연결은 e1(V1,V2) 이런식으로 나타낸다.

해당 그래프가 Directed(방향성) 그래프라면 "V1에서 V2로 가는 e1으로 이어져 있다"정도로 이해하면 되겠다.

만약 Undirected(무방향) 그래프 라면 "V1, V2가 e1으로 이어져 있다"로 이해하면 되겠다.

 

그래프 용어 추가 정리

그래프를 다루기 전에 알아야 하는 몇 가지 용어가 있다.

먼저 loop이다.

루프라는 이름에서 볼 수 있 듯, 하나의 정점에서 다시 자기 자신으로 되돌아오는 간선을 말한다.

수학적으로, 간선의 양 끝이 같은 정점을 가리키는 경우를 말한다.

e1은 loop에 속한다.

다음으로 Path이다.

Path는 정점들의 순서 있는 나열을 말한다.

쉽게 말해 p1, p2, p3, ... ,p10까지 있다고 할 때,

p1-> p2 -> p4 -> p10 간선들로 이어져 있다고 가정하면, 이 전체를 p1부터 p10까지의 path라고 할 수 있다.

 

다음은 다중 간선이다.

동일한 두 정점 사이에 같은 방향(방향이 없는 그래프라면 같은 쌍)에 대해 두 개 이상의 간선이 존재하는 경우를 말한다.

이것도 다중간선이라고 볼 수 있다

 

위 사진처럼 숭실대학교 정보과학관을 V1, 서울대 입구역을 V2라고 하면 보이는것만 해도 경로가 3개가 있다.

이런 경우도 V1,V2 사이의 e1,e2,e3의 간선 총 3개가 있으며, 다중 간선이라고 볼 수 있다.

 

마지막으로 단순 그래프이다.

단순 그래프란 loop도 없고, 다중 간선도 존재하지 않는 그래프로 모든 정점 쌍은 많아야 하나의 간선으로 연결되어 있다는 특징이 있다.

 

그래프의 구현

그래프는 일반적으로 2차원 배열(인접 행렬 형태)로 구현하곤 한다.

예를 들어 아래와 같은 그래프가 있다고 가정하자

이 경우 인접행렬로 표현하면 연결된 상태는 1(true), 연결되지 않은 상태는 0(false)으로 표현할 수 있다.

	1	2	3	4
1	0	1	1	0
2	1	0	0	1
3	1	0	0	1
4	0	1	1	0

 

다른 방법으로는 연결 리스트로 구현할 수도 있다.

연결 리스트로 구현한 방법

이 그래프처럼 각 정점들이 가리키는 정점들을 연결리스트로 표시하여 구현할 수도 있다.

아니면 각 정점별로 정수 집합(IntSet)을 만들어서 연결되어 있는 정점들을 관리할 수 있다. 

 

구현 방법에 따른 시간/공간복잡도 분석

그럼 어떤 경우에 인접 행렬 또는 인접 리스트를 사용해야 하는걸까?

아래 표로 정리해 보았다.

구분	인접 행렬	연결 리스트, 정수 집합
메모리 사용	O(V2)	O(V+E)
간선 존재 확인	O(1)	O(deg(V))
간선 추가 | 제거	O(1)	O(1)~O(log deg(V))
출발 간선 순회	O(V)	O(deg(V))
구현 난이도	쉽고 간단	약간 더 복잡하지만 유연

여기서 deg(V)는 차수를 나타내는 것으로 각 정점에 연결된 간선의 수를 의미한다.

간선의 추가 및 제거 방법이 연결리스트에서 차이가 나는 이유는 구현 방법에 따라 약간의 차이가 발생할 수 있기 때문이다.

 

위 표를 보고 내가 구현하고자 하는 목표에 따라 필요한 형태로 구현해서 사용하면 되겠다.

 

그래프 순회 - BFS

BFS는 너비 우선 탐색이라는 의미이다.

출발점으로부터 같은 개수의 간선으로 도달할 수 있는 정점을 다 거쳐가면서 탐색하는 느낌이다.

위와 같은 예시 그래프가 있다고 치고 A부터 BFS로 탐색한다고 하면 A -> (B -> C -> D) -> (E -> F)이런식으로 탐색할 수 있다.

괄호의 의미는 A로부터 떨어진 간선의 개수로, 괄호에 묶인 순서대로 동일한 우선순위를 갖는다고 생각하면 편하다.

 

BFS는 Queue를 이용하여 구현한다.

위 그래프를 이용해서 설명해보면

초기는 이렇게 들어갈 것이다.

이후 A를 Queue에서 빼고 인접한 정점을 모두 Queue에 집어넣는다.

A는 이미 방문했다는 표시를 남긴다.

이제 B, C, D를 Queue에서 차례대로 빼면서 탐사하고 방문했다는 표시를 남긴다.

이후 각 정점과 인접해 있으면서 방문한 적 없는 정점을 Queue에 넣는다.

B와 C가 공통적으로 F를 가리키기 때문에 F가 2번 들어갔지만,

실제 탐사할 때는 처음 F를 탐사하고 나면 F는 방문했다는 표시가 남기 때문에 다시 방문하지 않는다. 

 

BFS 의사 코드

BFS(G, start):
    // 모든 정점을 미방문 상태로 초기화
    for each vertex v in G.V:
        visited[v] ← false

    create empty queue Q
    // 시작 정점 방문 처리
    visited[start] ← true
    enqueue(Q, start)

    while Q is not empty:
        u ← dequeue(Q)
        for each v in Adj[u]:        // u에 인접한 모든 정점 순차 탐색
            if not visited[v]:
                visited[v] ← true
                enqueue(Q, v)

 

그래프 순회 - DFS

DFS는 깊이 우선 탐색이라는 의미이다.

출발점으로부터 타고 갈 수 있는 간선을 계속 타고 가다가 막히면 돌아와서 다른 간선으로 타고 가는 식으로 최대한 가고 돌아오는 식으로 순회한다.

똑같이 위 그래프를 DFS로 순회한다고 하면, A -> B -> E -> F -> C -> D처럼 순회할 수 있다.

 

DFS는 Stack을 이용해서 구현한다.

위 그래프를 이용해서 설명해보면

초기에 이 상태로 A를 방문한다. 

A의 인점 정점인 B를 스택에 넣는다

이제 B와 인접 정점인 E를 방문하고 스택에 넣는다.

E의 인접한 정점 중 방문하지 않은 정점이 없기에 스택에서 뺀다.

이후 B와 인접한 다른 정점인 F를 방문하고 스택에 넣는다.

F에 인접한 다른 정점인 C를 방문하고 스택에 넣는다.

C와 인접한 정점 중 방문하지 않은 정점이 없기에 스택에서 뺀다.

F와 B도 같은 이유로 스택에서 뺀다.

A와 인접한 정점 중 방문하지 않은 D를 방문하고 스택에 넣는다.

D, A 모두 인접한 정점 중 방문하지 않은 정점이 없기 때문에 스택에서 뺀다.

스택이 비었고 모든 정점을 방문하였기에 순회를 종료한다.

 

DFS의 의사코드

DFS-Iterative(G, start):
    for each vertex v in G.V:
        visited[v] ← false

    create empty stack S
    push(S, start)

    while S is not empty:
        u ← pop(S)
        if not visited[u]:
            visited[u] ← true
            for each v in reverse(Adj[u]):
                if not visited[v]:
                    push(S, v)