Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C++로 구현하는 0-1 BFS 알고리즘: 이진 가중치 그래프의 최단 경로 찾기

노드와 간선으로 연결된 그래프가 있다고 가정해 봅시다. 각 간선은 이진 가중치를 가지며, 즉 가중치는 0 또는 1 중 하나입니다. 하나의 시작 정점(소스)이 주어졌을 때, 소스에서 다른 모든 정점까지의 최단 경로를 찾아야 합니다.

0-1 BFS란 무엇인가?

일반적인 BFS(너비 우선 탐색) 알고리즘은 모든 간선의 가중치가 동일할 때 사용됩니다. 하지만 여기서는 일부 간선의 가중치가 0이고, 일부는 1입니다. 이런 경우 다익스트라 알고리즘을 사용해도 되지만, 0-1 BFS를 활용하면 더 효율적으로 문제를 해결할 수 있습니다.

핵심 아이디어는 덱(Deque, Double Ended Queue)을 사용하는 것입니다. 탐색 과정에서 간선의 가중치를 확인한 후, 가중치가 0이면 덱의 앞쪽(front)에 정점을 삽입하고, 가중치가 1이면 덱의 뒤쪽(back)에 삽입합니다. 이렇게 하면 가중치가 낮은 경로를 우선적으로 탐색하게 되어 최단 거리를 올바르게 계산할 수 있습니다.

알고리즘 동작 원리

binaryBFS(src) 알고리즘은 다음과 같이 동작합니다:

  1. 거리 배열(dist)을 선언하고, 모든 값을 무한대(INFINITY)로 초기화합니다.
  2. 시작 정점의 거리를 0으로 설정하고, 해당 정점을 덱 Q에 삽입합니다.
  3. 덱이 빌 때까지 다음 과정을 반복합니다:
    • 덱의 앞쪽에서 정점 v를 꺼냅니다.
    • v에 연결된 모든 간선 e에 대해, 현재 저장된 거리보다 dist[v] + 간선 가중치가 더 작으면 거리를 갱신합니다.
    • 갱신 시 간선 가중치가 0이면 덱 앞쪽에, 1이면 덱 뒤쪽에 정점을 삽입합니다.
  4. 모든 정점까지의 최단 거리를 출력합니다.

C++ 구현 예제

#include<iostream>
#include<vector>
#include<deque>
#include<climits>
#define V 8
using namespace std;

struct node {
   int next, weight;
};
vector <node> edges[V];

void binaryBFS(int src) {
   int dist[V];
   for (int i=0; i<V; i++) // 초기값을 무한대로 설정
      dist[i] = INT_MAX;
   deque <int> Q;
   dist[src] = 0; // 자기 자신까지의 거리는 0
   Q.push_back(src);
   while (!Q.empty()) {
      int v = Q.front(); // 덱 앞쪽의 정점을 꺼냄
      Q.pop_front();
      for (int i=0; i<edges[v].size(); i++) {
         // 최적 거리 조건 확인
         if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) {
            dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
            if (edges[v][i].weight == 0) // 가중치 0은 앞쪽에, 그 외는 뒤쪽에 삽입
               Q.push_front(edges[v][i].next);
            else
               Q.push_back(edges[v][i].next);
         }
      }
   }
   for (int i=0; i<V; i++)
      cout << dist[i] << " ";
}

void addEdge(int u, int v, int wt) {
   edges[u].push_back({v, wt});
   edges[v].push_back({u, wt});
}

int main() {
   addEdge(0, 1, 0);
   addEdge(0, 3, 1);
   addEdge(0, 4, 0);
   addEdge(1, 2, 1);
   addEdge(1, 7, 0);
   addEdge(2, 5, 1);
   addEdge(2, 7, 0);
   addEdge(3, 4, 0);
   addEdge(3, 6, 1);
   addEdge(4, 6, 1);
   addEdge(5, 7, 1);
   addEdge(6, 7, 1);
   int src = 6;
   binaryBFS(src);
}

실행 결과

1 1 1 1 1 2 0 1

결과 해석 및 시간 복잡도

위 실행 결과는 시작 정점 6번에서 각 정점(0~7번)까지의 최단 거리를 나타냅니다. 예를 들어, 정점 6에서 정점 5까지의 최단 거리는 2이며, 정점 6 자신의 거리는 0입니다.

0-1 BFS의 시간 복잡도는 O(V+E)로, 다익스트라 알고리즘의 O((V+E)log V)보다 효율적입니다. 각 정점이 덱에 여러 번 삽입될 수 있지만, 간선 가중치가 0 또는 1로 제한되어 있기 때문에 전체 연산 횟수는 간선의 수에 비례하여 유지됩니다.