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

C++로 두 노드 간 경로 존재 여부 확인하기: BFS 알고리즘 구현

이 글에서는 그래프 이론의 기본 문제 중 하나인 두 노드 사이에 경로가 존재하는지 판별하는 C++ 프로그램을 소개합니다. 경로 탐색은 네비게이션, 소셜 네트워크 분석, 네트워크 라우팅 등 다양한 분야에서 활용되는 핵심 개념입니다.

알고리즘 개요

이 프로그램은 너비 우선 탐색(BFS, Breadth-First Search)을 기반으로 동작합니다. 시작 노드 s에서 목적지 노드 d에 도달할 수 있는지 재귀적으로 확인하는 방식입니다.

동작 순서

  1. 방문 초기화: 모든 정점을 '미방문' 상태로 표시합니다.
  2. 시작 노드 처리: 현재 노드를 방문 처리하고 큐(queue)에 삽입합니다. 큐는 인접 정점들을 탐색하는 데 사용됩니다.
  3. 정점 꺼내기: 큐에서 정점을 하나 꺼냅니다(dequeue).
  4. 인접 정점 탐색: 꺼낸 정점 s에 인접한 모든 정점을 확인합니다.
  5. 방문 여부 검사: 아직 방문하지 않은 인접 정점이라면 방문 처리 후 큐에 삽입합니다.
  6. 목적지 도달 확인: 해당 인접 노드가 목적지 노드라면 true를 반환하고, 아니라면 BFS를 계속 진행합니다.

C++ 구현 코드

#include <iostream>
#include <list>
using namespace std;

class G {
    int n;
    list<int> *adj;
public:
    G(int n);
    void addEd(int x, int w);
    bool isReach(int s, int d);
};

G::G(int n) { // 생성자
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int x, int w) { // 그래프에 간선 추가
    adj[x].push_back(w); // x의 리스트에 w 추가
}

bool G::isReach(int s, int d) {
    if (s == d)
        return true;

    bool *visited = new bool[n];
    // 모든 정점을 미방문 상태로 초기화
    for (int i = 0; i < n; i++)
        visited[i] = false;

    list<int> queue;
    // 현재 노드를 방문 처리하고 큐에 삽입
    visited[s] = true;
    queue.push_back(s);

    list<int>::iterator i;
    while (!queue.empty()) {
        s = queue.front();
        queue.pop_front(); // 큐에서 정점을 꺼냄

        // 방문하지 않은 인접 정점 확인
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (*i == d)
                return true;
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    return false;
}

int main() {
    G g(4);
    g.addEd(1, 3);
    g.addEd(0, 1);
    g.addEd(2, 3);
    g.addEd(1, 0);
    g.addEd(2, 1);
    g.addEd(3, 1);

    cout << "Enter the source and destination vertices: (0-3)";
    int a, b;
    cin >> a >> b;

    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;

    // 시작점과 목적지를 서로 바꿔서 반대 방향도 확인
    int t;
    t = a;
    a = b;
    b = t;

    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;

    return 0;
}

코드 설명

클래스 구조

  • G 클래스는 정점의 개수 n과 각 정점의 인접 리스트를 저장하는 adj 배열을 멤버 변수로 가집니다.
  • addEd() 함수는 방향 그래프에 간선을 추가합니다.
  • isReach() 함수가 핵심 로직으로, BFS를 통해 두 정점 간 연결 여부를 판별합니다.

핵심 포인트

  • 시작 노드와 목적지 노드가 같으면 즉시 true를 반환하여 불필요한 탐색을 줄입니다.
  • visited 배열로 무한 루프(사이클)를 방지합니다.
  • main() 함수에서는 입력받은 두 정점에 대해 양방향 모두 경로가 있는지 확인합니다.

실행 결과

Enter the source and destination vertices: (0-3)
There is a path from 3 to 1
There is a path from 1 to 3

위 실행 결과에서 볼 수 있듯이, 정점 3에서 정점 1로 가는 경로와 그 반대 방향인 정점 1에서 정점 3으로 가는 경로 모두 존재함을 확인할 수 있습니다.

마무리

BFS를 활용한 경로 탐색은 시간 복잡도 O(V+E)로 효율적으로 동작하며, 가중치가 없는 그래프에서 최단 거리(간선 수 기준)를 찾는 데에도 응용할 수 있습니다. DFS(깊이 우선 탐색)를 사용해도 동일한 결과를 얻을 수 있으니, 두 방식을 비교해 보며 학습하시길 추천합니다.