이 문제에서는 방향 그래프가 주어지고 그래프의 소스에서 목적지까지의 모든 경로를 인쇄해야 합니다.
방향 그래프 정점 a에서 b로 향하는 간선이 있는 그래프입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
소스 =K 대상 =P
출력:
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
여기에서 K에서 P로 가는 경로를 찾았습니다. 경로를 가로질러 K에서 P로 향하는 모든 경로를 인쇄했습니다.
이 문제를 해결하기 위해 깊이 우선 검색을 사용하여 그래프를 탐색합니다. 순회 기술. 소스에서 시작 우리는 경로 배열의 각 정점 저장소를 순회하고 방문한 것으로 표시합니다(동일한 정점을 여러 번 방문하는 것을 피하기 위해). 목적지 일 때 이 경로를 인쇄하십시오. 정점에 도달했습니다.
로직을 구현하는 프로그램을 보자 -
예시
#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<<"Following are all different paths from source to destination : \n";
g.printPaths(s, d);
return 0;
} 출력
Following are all different paths from source to destination : 2 0 1 3 2 0 3 2 1 3