C++로 그래프의 두 노드 사이 경로 존재 여부 확인하기

이 글에서는 C++를 사용하여 주어진 그래프 위에서 두 노드(정점) 사이에 경로가 존재하는지 확인하는 방법을 다룹니다. 그래프 탐색 기법을 활용하면 시작 정점에서 목적지 정점으로 도달할 수 있는지, 즉 도달 가능성(reachability) 여부를 손쉽게 판별할 수 있습니다.

알고리즘

아래 알고리즘은 큐(queue)를 이용한 그래프 순회 방식으로, 시작 정점 s에서 목적지 정점 d까지 도달 가능한지 검사하는 isReach() 함수의 동작 과정입니다.

Begin
    function isReach() : d가 s로부터 도달 가능한지 확인하는 함수
    A) 모든 정점을 '방문하지 않음' 상태로 초기화한다.
    B) 현재 노드를 '방문함'으로 표시하고 큐에 삽입한다.
       (큐는 한 정점의 모든 인접 정점을 얻는 데 사용된다)
    C) 큐에서 정점 하나를 꺼낸다(dequeue).
    D) 꺼낸 정점 s의 모든 인접 정점을 조사한다.
    E) 인접 정점 중 아직 방문하지 않은 정점은 '방문함'으로 표시하고 큐에 삽입한다.
    F) 이 인접 노드가 목적지 노드라면 true를 반환하고,
       그렇지 않으면 탐색(BFS)을 계속 진행한다.
End

예제 코드

아래 예제는 인접 리스트 기반으로 그래프를 구현하고, 사용자로부터 출발 정점과 도착 정점을 입력받아 두 방향 각각에 대해 경로 존재 여부를 출력합니다.

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

class G {
    int n;
    list<int> *adj;
    public:
       // 함수 선언
       G(int n);
       void addEd(int v, int u);
       bool isReach(int s, int d);
};

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

void G::addEd(int v, int u) { // 그래프에 간선 추가
    adj[v].push_back(u);
}

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;
          // 인접 노드가 목적지 노드라면 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;
}

코드 설명

1. 그래프 클래스(G)

생성자에서 정점 개수 n을 받아 인접 리스트 배열을 동적으로 할당하고, addEd() 함수로 간선 정보를 추가합니다.

2. 경로 탐색 함수(isReach)

출발 정점과 도착 정점이 같으면 즉시 true를 반환합니다. 그렇지 않으면 방문 여부 배열을 초기화한 뒤, 큐에 출발 정점을 넣고 탐색을 시작합니다. 큐에서 정점을 하나씩 꺼내며 인접 정점을 조사하고, 그중 목적지가 발견되면 true를 반환하며, 모든 정점을 탐색해도 목적지에 도달하지 못하면 false를 반환합니다.

3. main() 함수

4개의 정점을 가진 그래프를 만들고 간선을 추가한 후, 사용자 입력값 a, b에 대해 a→b 경로를 먼저 검사합니다. 이후 두 변수를 서로 교환하여 반대 방향인 b→a 경로도 함께 검사합니다.

실행 결과

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) 각각에 대해 경로가 존재하는지 여부를 화면에 출력합니다.

참고: 시간 복잡도

이 방식의 시간 복잡도는 O(V + E)입니다. V는 정점의 수, E는 간선의 수로, 모든 정점과 간선을 최대 한 번씩만 방문하기 때문입니다. 공간 복잡도 역시 방문 배열과 큐에 저장되는 데이터 때문에 O(V) 수준입니다.