In addition to creating the graph you are required to write a depth-first traver
ID: 3838445 • Letter: I
Question
In addition to creating the graph you are required to write a depth-first traversal algorithm that will visit each node and print out the city it visited. A depth first traversal of a graph is very similar to a depth first traversal of a tree. The difference is that graphs may contains cycles so you must keep track of what has been visited so that you do not consider nodes more than one time. One of the strategies for this is to use a boolean array where you mark true when a node is visited. This can also be accomplished by adding a visited field to the node definition.Explanation / Answer
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only difference here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.
import java.io.*;
import java.util.*;
class Graph
{
private int V; // No. of vertices will be represented by V
private LinkedList<Integer> adj[];
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}
void DFSUtil(int v,boolean visited[])
{
visited[v] = true;
System.out.print(v+" ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
void DFS()
{
boolean visited[] = new boolean[V];
for (int i=0; i<V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}
public static void main(String args[])
{
Graph g = new Graph(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);
System.out.println("Following elements are in Depth First Traversal");
g.DFS();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.