Queue & Graph Traversal

Table of contents

• Problem
• Implementation
• Extension

Problem

가중치가 없는 그래프에서 시작점부터 각 정점까지의 최단 edge 수를 BFS로 계산한다. 가중치가 있으면 같은 BFS가 일반적으로 성립하지 않는다.

Implementation

예제는 작은 고정 크기 adjacency matrix다. O(V²)이며 큰 sparse graph에서는 adjacency list로 O(V+E)를 목표로 한다. queue에 넣을 때 방문 표시하여 중복 삽입을 방지한다.

#include <assert.h>
#include <stddef.h>
#define N 5
static void bfs(const unsigned char graph[N][N], size_t start, int dist[N]) {
    size_t q[N], head=0, tail=0;
    for (size_t i=0;i<N;++i) dist[i]=-1;
    assert(start<N);
    dist[start]=0; q[tail++]=start;
    while (head<tail) {
        size_t u=q[head++];
        for (size_t v=0;v<N;++v) {
            if (graph[u][v] && dist[v]<0) {
                dist[v]=dist[u]+1;
                assert(tail<N);
                q[tail++]=v;
            }
        }
    }
}
int main(void) {
    const unsigned char g[N][N]={
        {0,1,1,0,0},{1,0,0,1,0},{1,0,0,1,0},{0,1,1,0,0},{0}
    };
    int d[N]; bfs(g,0,d);
    assert(d[0]==0 && d[3]==2 && d[4]==-1);
    return 0;
}

Extension

DFS는 연결 요소·cycle·topological 문제에 활용한다. directed/undirected cycle 판정은 다르다. 큰 입력의 recursion depth를 확인하고 필요한 경우 명시적 stack을 사용한다.

---

Previous

Binary Search

Next

Dynamic Programming