Given a directed graph. The task is to find a shortest path from vertex 0 to a target vertex v. You may adapt Breadth First Traversal of this graph starting from 0 to achieve this goal.Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
C++
Given a directed graph. The task is to find a shortest path from vertex 0
to a target vertex v. You may adapt Breadth First Traversal of this
graph starting from 0 to achieve this goal.Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
Example
Input:
6 8 2
0 1
0 4
1 2
0 3
3 5
4 5
5 2
3 1
Output:
0 1 2
Use the driver code typed out below.
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution {
public:
// Function to return a path
vector shortestPath(int V, vector adj[], int target) {
// Enter code here!
}
};
// { Driver Code Starts.
int main() {
int tc;
cin >> tc;
while (tc--) {
int V, E, target;
cin >> V >> E >> target;
vector adj[V];
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
// adj[v].push_back(u);
}
// string s1;
// cin>>s1;
Solution obj;
vector ans = obj. shortestPath(V, adj, target);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
} // } Driver Code Ends
Step by step
Solved in 5 steps with 1 images
