Write a java Program for Depth-first search (DFS) in JAVA is a classic method fo

Question

Write a java Program for

Depth-first search (DFS) in JAVA is a classic method for systematically examining each of the vertices
and edges in a graph. The aim of DFS algorithm is to traverse by going through the depth of
the graph from the starting node.
1. Given a graph, create a function called List<V> dfs(Graph G) that performs the
deep first search (DFS) algorithm for visiting the graph G. This function must return
the list of vertices in the order of their first encounter. In case of choice, the vertex
with the smallest identifier will be chosen.
2. One important application of the depth first search algorithm is to find the connected
components of a graph. Write a function int cc(Graph G) that takes as input a simple
graph and determines the number of connected components. The function int
cc(Graph G) must use the DFS algorithm. Write a function called isConnected()
that returns true if the graph is connected, false otherwise.
3. Test the dfs(.) and cc(.) functions with the graph is the graph-DFS-BFS.txt file.
Consider as starting node the node 5. What is the order of the first encounter of the
nodes? How many components does the graph have? Is it connected?

Explanation / Answer

//if you have any doubt then feel free to ask ...write your doubt in comment section....

//i have give this program with some input...

// Java program to print DFS traversal from a given given graph
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices

// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];

// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}

//Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v,boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v+" ");

// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}

// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS(int v)
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];

// Call the recursive helper function to print DFS traversal
DFSUtil(v, 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 is Depth First Traversal "+
"(starting from vertex 2)");

g.DFS(2);
}
}

//This is a java program to check the connectivity of a graph using DFS

import java.util.Scanner;
import java.util.Stack;

public class Connectivity_DFS
{
private final int vertices;
private int[][] adjacency_matrix;
private Stack<Integer> stack;

public Connectivity_DFS(int v)
{
vertices = v;
adjacency_matrix = new int[vertices + 1][vertices + 1];
stack = new Stack<Integer>();
}

public void makeEdge(int to, int from, int edge)
{
try
{
adjacency_matrix[to][from] = edge;
adjacency_matrix[from][to] = edge;
} catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
}

public int getEdge(int to, int from)
{
try
{
return adjacency_matrix[to][from];
} catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
return -1;
}

public void dfs(int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.pop();
i = 1;// element;
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
}
i++;
}
}

System.out.print("The source node " + source + " is connected to: ");
int count = 0;
for (int v = 1; v <= number_of_nodes; v++)
if (visited[v] == 1)
{
System.out.print(v + " ");
count++;
}

if (count == number_of_nodes)
System.out.print(" The Graph is Connected ");
else
System.out.print(" The Graph is Disconnected ");
}

public static void main(String args[])
{
int v, e, count = 1, to = 0, from = 0;
Scanner sc = new Scanner(System.in);
Connectivity_DFS graph;
System.out.println("The Undirected Graph Connectivity Test");
try
{
System.out.println("Enter the number of vertices: ");
v = sc.nextInt();
System.out.println("Enter the number of edges: ");
e = sc.nextInt();

graph = new Connectivity_DFS(v);

System.out.println("Enter the edges: <to> <from>");
while (count <= e)
{
to = sc.nextInt();
from = sc.nextInt();

graph.makeEdge(to, from, 1);
count++;
}

System.out.println("The adjacency matrix for the given graph is: ");
System.out.print(" ");
for (int i = 1; i <= v; i++)
System.out.print(i + " ");
System.out.println();

for (int i = 1; i <= v; i++)
{
System.out.print(i + " ");
for (int j = 1; j <= v; j++)
System.out.print(graph.getEdge(i, j) + " ");
System.out.println();
}

System.out.println("Enter the Source Node: ");
int sourceNode = sc.nextInt();
graph.dfs(sourceNode);

} catch (Exception E)
{
System.out.println("Somthing went wrong");
}

sc.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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