[c언어] 그래프 탐색 알고리즘

26 Dec 2023

c언어

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 탐색 문제에 많이 활용됩니다. 그래프를 탐색하는 데에는 다양한 알고리즘이 사용됩니다. 이번 글에서는 대표적인 그래프 탐색 알고리즘으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 살펴보겠습니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 그래프의 정점을 가능한 깊이까지 탐색한 후, 다시 돌아와서 다른 정점을 탐색하는 알고리즘입니다. 스택(Stack) 또는 재귀 함수를 이용하여 구현할 수 있습니다.

void dfs(int v) {
    visited[v] = true;  // 정점 v를 방문했음을 표시
    // 정점 v에 대한 처리
    for (int i = 0; i < adj[v].size(); i++) {
        int next = adj[v][i];  // 정점 v와 연결된 다음 정점
        if (!visited[next]) {
            dfs(next);  // 다음 정점을 방문
        }
    }
}

너비 우선 탐색(BFS)

너비 우선 탐색은 시작 정점으로부터 거리에 따라 단계별로 탐색을 진행하는 알고리즘입니다. 큐(Queue)를 이용하여 구현할 수 있습니다.

void bfs(int start) {
    queue<int> q;
    q.push(start);  // 시작 정점을 큐에 삽입
    visited[start] = true;  // 시작 정점을 방문했음을 표시
    while (!q.empty()) {
        int v = q.front();
        q.pop();  // 큐에서 정점을 꺼내서
        // 정점 v에 대한 처리
        for (int i = 0; i < adj[v].size(); i++) {
            int next = adj[v][i];  // 정점 v와 연결된 다음 정점
            if (!visited[next]) {
                visited[next] = true;  // 다음 정점을 방문했음을 표시
                q.push(next);  // 다음 정점을 큐에 삽입
            }
        }
    }
}

DFS와 BFS는 각각 스택과 큐를 이용하여 그래프를 탐색하는 방식의 차이가 있습니다. 알고리즘이 선택되는 경우에는 그래프의 구조나 문제의 성격에 따라 달라질 수 있습니다.

결론

그래프 탐색 알고리즘은 다양한 분야에서 활용되고 있으며, 실제 문제에 적용할 때는 구체적인 상황에 맞게 알고리즘을 선택해야 합니다. 이를 통해 보다 효율적인 문제 해결이 가능해질 것입니다.

참고 문헌:

Skiena, S. S. (2008). The Algorithm Design Manual. Springer.