Given the following adjacency list representation of an undirected graph, give the visited node order forDepth-First Search, starting with v1. The format of the solution: add number of node space node e.g. 1 2 3 4 5678 Adj[1]->4->6->7 Adj[2]->3->4->7 Adj[3]-> 2->5->6
![**Depth-First Search (DFS) on an Undirected Graph**
Given the following adjacency list representation of an undirected graph, derive the order in which nodes are visited using Depth-First Search (DFS), starting with node `v1`.
### Adjacency List Representation:
- `Adj[1]`: 4 -> 6 -> 7
- `Adj[2]`: 3 -> 4 -> 7
- `Adj[3]`: 2 -> 5 -> 6
- `Adj[4]`: 1 -> 2 -> 5 -> 6
- `Adj[5]`: 3 -> 4
- `Adj[6]`: 1 -> 3 -> 4 -> 7
- `Adj[7]`: 1 -> 2 -> 6
### Solution Format:
Nodes are listed by the order in which they are visited, separated by spaces. Example format: `1 2 3 4 5 6 7 8`
### Depth-First Search Result:
Starting from node `v1`, the DFS visits nodes in the following order:
`4 6 7 3 2 1`
This sequence represents the path followed during the DFS traversal, where each step explores as far along a branch as possible before backtracking.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F346b36e0-a4d8-47d7-8bd1-1ad776cb1cf3%2F97d6b716-69d9-4a16-893e-f03ddd967b08%2F49s829_processed.png&w=3840&q=75)
Solution-
Above is the code that helps to print the traversal DFS of adjacent vertex starting from v1.
Code-
//Print DFS traversal from a given vertex in a given graph using this C++ programme.
#include <bits/stdc++.h>
using namespace std;
//A directed graph is represented by the graph class using an adjacency list.
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;
// graphing function to add edges
void addEdge(int v, int w);
// DFS traversal of the vertices
// reachable from v
void DFS(int v);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
// Add w to v’s list.
}
void Graph::DFS(int v)
{
//Indicate that the current node has been visited and
//print it
visited[v] = true;
cout << v << " ";
// Repeat for all the vertices close to this vertex
//in the equation
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}
// Driver's code
int main()
{
//Make the graph shown in the illustration above.
Graph g;
g.addEdge(1, 4);
g.addEdge(1, 6);
g.addEdge(1, 7);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(2, 7);
g.addEdge(3, 2);
g.addEdge(3, 5);
g.addEdge(3, 6);
g.addEdge(4, 1);
g.addEdge(4, 2);
g.addEdge(4, 5);
g.addEdge(4, 6);
g.addEdge(5, 3);
g.addEdge(5, 4);
g.addEdge(6, 1);
g.addEdge(6, 3);
g.addEdge(6, 4);
g.addEdge(6, 7);
g.addEdge(7, 1);
g.addEdge(7, 2);
g.addEdge(7, 6);
cout << "Following is Depth First Traversal"
" (starting from vertex 1) \n";
// Function call
g.DFS(1);
return 0;
}
Step by step
Solved in 3 steps with 5 images
