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

C++로 방향 그래프에서 출발점부터 도착점까지의 모든 경로 출력하기

문제 개요

이 문제에서는 방향 그래프(Directed Graph)가 주어지며, 출발점(Source)에서 도착점(Destination)까지 이어지는 모든 경로를 찾아 출력해야 합니다.

방향 그래프란 간선(edge)에 방향성이 존재하는 그래프를 의미합니다. 즉, 정점 a에서 정점 b로 향하는 간선은 한 방향으로만 이동할 수 있습니다.

예시

다음 그림과 같은 그래프가 있다고 가정해 보겠습니다.

C++로 방향 그래프에서 출발점부터 도착점까지의 모든 경로 출력하기

  • 출발점(Source) = K
  • 도착점(Destination) = P

출력 결과:

K -> T -> Y -> A -> P
K -> T -> Y -> P
K -> A -> P

위 결과는 K에서 P까지 도달할 수 있는 세 가지 경로를 모두 찾아 출력한 것입니다. 각 경로는 서로 다른 정점들을 거쳐 최종적으로 P에 도달합니다.

접근 방법: 깊이 우선 탐색(DFS)

이 문제는 깊이 우선 탐색(Depth-First Search, DFS) 기법을 활용하면 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.

  1. 출발점에서 탐색을 시작하여 현재 정점을 경로 배열(path)에 저장하고, 해당 정점을 방문 처리합니다.
  2. 인접한 정점 중 아직 방문하지 않은 정점이 있다면 재귀적으로 계속 탐색합니다.
  3. 탐색 중 도착점에 도달하면 지금까지 저장된 경로를 출력합니다.
  4. 백트래킹(backtracking) 시에는 방문 표시를 해제하여 다른 경로에서도 같은 정점을 사용할 수 있도록 합니다.

여기서 핵심은 한 정점이 여러 경로에 포함될 수 있으므로, 한 경로의 탐색이 끝나면 반드시 방문 상태를 되돌려야 한다는 점입니다.

C++ 구현 코드

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

class Graph {
   int V;
   list<int> *adj;
   void findNewPath(int , int , bool [], int [], int &);
public:
   Graph(int V);
   void addEdge(int u, int v);
   void printPaths(int s, int d);
};

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

void Graph::addEdge(int u, int v) {
   adj[u].push_back(v);
}

void Graph::printPaths(int s, int d) {
   bool *visited = new bool[V];
   int *path = new int[V];
   int path_index = 0;
   for (int i = 0; i < V; i++)
      visited[i] = false;
   findNewPath(s, d, visited, path, path_index);
}

void Graph::findNewPath(int u, int d, bool visited[],
int path[], int &path_index) {
   visited[u] = true;
   path[path_index] = u;
   path_index++;
   if (u == d) {
      for (int i = 0; i<path_index; i++)
         cout<<path[i]<<" ";
      cout << endl;
   } else {
      list<int>::iterator i;
      for (i = adj[u].begin(); i != adj[u].end(); ++i)
         if (!visited[*i])
            findNewPath(*i, d, visited, path, path_index);
   }
   path_index--;
   visited[u] = false;
}

int main() {
   Graph g(4);
   g.addEdge(0, 1);
   g.addEdge(0, 2);
   g.addEdge(0, 3);
   g.addEdge(2, 0);
   g.addEdge(2, 1);
   g.addEdge(1, 3);
   int s = 2, d = 3;
   cout<<"출발점에서 도착점까지의 모든 경로 : \n";
   g.printPaths(s, d);
   return 0;
}

실행 결과

출발점에서 도착점까지의 모든 경로 :
2 0 1 3
2 0 3
2 1 3

코드 설명

  • Graph 클래스: 정점의 개수(V)와 인접 리스트(adj)를 멤버 변수로 가지며, 간선 추가와 경로 탐색 기능을 제공합니다.
  • addEdge 함수: 정점 u에서 v로 향하는 방향 간선을 인접 리스트에 추가합니다.
  • printPaths 함수: 방문 여부 배열(visited)과 경로 배열(path)을 초기화한 뒤, 재귀 탐색을 시작합니다.
  • findNewPath 함수: DFS의 핵심 로직입니다. 현재 정점을 경로에 추가하고, 도착점에 도달하면 경로 전체를 출력합니다. 탐색이 끝나면 백트래킹을 통해 방문 표시와 경로 인덱스를 원상복구합니다.

위 예제에서는 정점 2에서 정점 3까지 가는 모든 경로가 총 3개 존재하며, 프로그램은 이를 성공적으로 모두 출력합니다. 이 알고리즘의 시간 복잡도는 그래프의 구조에 따라 달라지며, 최악의 경우 지수적으로 증가할 수 있습니다. 왜냐하면 두 정점 사이의 모든 단순 경로(simple path)를 열거해야 하기 때문입니다.