A. Perform a depth-first search (DFS) on the following graph. Start the traversa
ID: 3828425 • Letter: A
Question
A. Perform a depth-first search (DFS) on the following graph. Start the traversal at
vertex A and whenever there’s a choice of vertices, pick the one that is alphabetically first. Construct the traversal stack (the first subscript number indicates the order in which a vertex was visit, i.e., pushed onto the stack; the second one indicates the order in which it became a dead-end, i.e., popped off the stack). Construct the corresponding depth-first search forest. Classify each edge as a tree edges shown with solid lines or back edges shown with dashed lines, and give the pre and post number of each vertex.
B. Traverse the following graph by breadth-first search. Start the traversal at vertex A and resolve ties by the vertex alphabetical order. Construct the traversal’s queue, with the numbers indicated the order in which the vertices were visited, i.e., added to (or removed from) the queue. Construct the corresponding breadth-first forest with the tree edges shown with solid lines, and cross edges shown with dotted lines. Start the traversal at vertex A and resolve ties by the vertex alphabetical order.
C. Illustrating by a DFS or BFS search tree, what is the minimum-edge path from vertex A to vertex K?
D. Illustrating by a DFS or BFS search tree, identify the connected components of the given graph.
H R E D GExplanation / Answer
// C++ program to print DFS traversal from a given vertex in a given graph
#include<iostream>
#include<list>
using namespace std;
// Graph class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
void DFSUtil(int v, bool visited[]); // A function used by DFS
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void DFS(int v); // DFS traversal of the vertices reachable from v
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal (starting from vertex 2) ";
g.DFS(2);
return 0;
}