In addition to creating the graph you are required to write a depth-first traver

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 visitied. 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 visitied field to the node definition.

Explanation / Answer

Hi, usually a Depth-First traversal of a graph makes use of a stack to keep track of the visited vertices. But in this case, as hinted at in the question, we'll make use of an array to do this.

This program makes use of an array to store the vertices of the graph, and another array of linked lists to store the adjacency list that is used to represent this graph. The 'i'th elelment of the vertices array is also the 'i'th vertex in the adjacency list. Below is the code in Java for this. Please feel free to drop the input statements from the constructor if they are not required.

package graphdfs;

import java.io.*;
import java.util.*;
import java.util.Scanner;

class DGraph{ //the graph
private int NoOfVertices; //the number of vertices in the graph
private String Vertices[]; //array containing the vertices of the graph
private LinkedList<String> adjList[]; //the adjacency list; an array of linked lists
//each element of the array represents a vertex and each list in linked to that element contains all vertices adjacent to it.
  
DGraph(int num){ //constructor
NoOfVertices=num;
Vertices=new String[NoOfVertices];//create an array of vertices
System.out.println("Enter the list of vertices :-");
Scanner kbd=new Scanner(System.in);
for(int i=0;i<NoOfVertices;i++)
{
System.out.print("Enter Vertex : ");
Vertices[i]=kbd.nextLine();
}
adjList=new LinkedList[NoOfVertices];//implement the array as a linked list of length 'NoOfVertices'
//now, set up a linked list for each element of this array
for(int i=0;i<NoOfVertices;i++)
adjList[i]=new LinkedList();
}
  
void DFT(){ //method for Depth First Traversal of the graph
//create an array to keep track of visited vertices
//each element of this array must be initialized to 'false'
//this is done automatically in java when any boolean variable is declared
boolean visited[]=new boolean[NoOfVertices];
//The 'i'th element of this array will be set to true when the 'i'th vertex is visited
  
for(int i=0;i<NoOfVertices;i++)
if(visited[i]==false)
Visit(i,visited); //call recursive function Visit() for each vertex of the graph,
//passing the vertex number and the visited array to it
}
void Visit(int vertex, boolean visited[]){
int i;
visited[vertex]=true; //mark the current vertex as visited
System.out.print(Vertices[vertex]+" ");//print the current vertex
//now, recursively visit each vertex adjacent to the current vertex
Iterator<String> index =adjList[vertex].listIterator(); //use this to visit each vertex adjacent to the current vertex
while(index.hasNext())//loop while there are still unvisited vertices adjacent to the current vertex
{
String v=index.next(); //get the next adjacent vertex
//find the index number of this vertex in the vertices array
for(i=0;i<NoOfVertices;i++)
if(v==Vertices[i])
break;
//i is now the index number of the required vertex
//so if vertex i has not been visited yet, visit it
if(visited[i]==false)
Visit(i,visited);
}
}
void addEdge(String startV, String EndV){//add edge to the graph from vertex StartV to vertex EndV
int i;
//find the index number of StartV in the vertices array
for(i=0;i<NoOfVertices;i++)
if(startV==Vertices[i])
break;
adjList[i].add(EndV); //add EndV to the list of StartV
}

}

Hope this helps!

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.