JAVA Given a directed graph, a source vertex ‘source’ and a destination vertex ‘

Question

JAVA

Given a directed graph, a source vertex ‘source’ and a destination vertex ‘dest’, print all paths from a
given ‘source’ to a given ‘dest’.
Consider the following directed graph. Let the source be 0 and dest be 4. There are 3 different paths
from 0 to 4. [0, 2, 4], [0, 3, 2, 4] and [0, 3, 4]

1) Write a method to do Depth First Search (DFS) of a given directed graph. Implement the following
methods:
- public void printAllPaths(int s, int d)
- private void printAllPathsUtil(Integer u, Integer d, ArrayList<Boolean> visited, List<Integer>
localPathList)

2) Run the Class TestGraph.java and see if the output is [0, 2, 4], [0, 3, 2, 4] and [0, 3, 4]. You may change
values in TestGraph.java for testing purposes.
Below is the file in which students will have to write their code wherever they find a comment: /*
YOUR CODE HERE */

Graph.java
package graphs;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
// A directed graph using adjacency list representation
public class Graph {
// No. of vertices in graph
private int vertices;
// adjacency list
private HashMap<Integer, List<Integer>> adjMap;
private ArrayList<Integer> adjList;
public Graph(int vertices){
//initialise vertex count
this.vertices = vertices;
// initialise adjacency list
adjMap = new HashMap<Integer, List<Integer>>();
}
// add edge from u to v
public void addEdge(int u, int v)
{
// Add v to u's list.
if(!adjMap.containsKey(u)){
adjMap.put(u, new ArrayList<Integer>());
}
adjMap.get(u).add(v);
}
// Prints all paths from 'source' to 'dest'
public void printAllPaths(int source, int dest) {

/* Declare an ArrayList of Boolean values
* Initialize ArrayList of Boolean values with 'false', size of list will be =
'vertices'
*/
/* YOUR CODE HERE */
/* Declare an ArrayList to store paths
* Add source to list path
*/

/* YOUR CODE HERE */
/* Call recursive utility */
printAllPathsUtil(source, dest, visited, pathList);
}
/*
* Mark the current node 'u' as true in visited list
* if current node 'u' equals destination 'd'
* Get arraylist 'verticeList' from 'adjMap' map for current node
* recursively iterate over this 'verticeList'
* check if vertice from this list is not visited already, add to 'localPathList'
* recursively call this method for values from vertice list, set to current node
* set current node as false after visiting it
*/
private void printAllPathsUtil(Integer u, Integer d, ArrayList<Boolean> visited,
List<Integer> localPathList) {
/* YOUR CODE HERE */
}
}

Java helper files (Students will need for testing Graph.java):

TestGraph.java
package graphs;
public class TestGraph {
public static void main(String[] args)
{
// Create a sample graph
Graph graph = new Graph(7);
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(0,3);
graph.addEdge(1,5);
graph.addEdge(1,6);
graph.addEdge(2,4);
graph.addEdge(2,1);
graph.addEdge(3,2);
graph.addEdge(3,4);
// source
int source = 0;
// destination
int dest = 4;
System.out.println("Following are all different paths from " + source + " to
" + dest);
graph.printAllPaths(source, dest);
}
}

SAMPLE OUTPUT:
Following are all different paths from 0 to 4
[0, 2, 4]
[0, 3, 2, 4]
[0, 3, 4]

Please note a few points:
1. Create 2 separate java files for the above code and place them in a package named graphs.
2. Write your code in Graph.java wherever you find the comment /* YOUR CODE HERE */
3. USE RECURSION for the implementation of printAllPathsUtil method.

Explanation / Answer

Solution:

Note : Please find the updated code with updated method in class file .if any query revert back me...
//////////////////////////Graph.java/////////////////////
// JAVA program to print all
// paths from a source to
// destination.
import java.util.ArrayList;
import java.util.List;
// A directed graph using
// adjacency list representation
public class Graph {
// No. of vertices in graph
private int v;
// adjacency list
private ArrayList<Integer>[] adjList;
//Constructor
public Graph(int vertices){
//initialise vertex count
this.v = vertices;
// initialise adjacency list
initAdjList();
}
// utility method to initialise
// adjacency list
@SuppressWarnings("unchecked")
private void initAdjList()
{
adjList = new ArrayList[v];
for(int i = 0; i < v; i++)
{
adjList[i] = new ArrayList<>();
}
}
// add edge from u to v
public void addEdge(int u, int v)
{
// Add v to u's list.
adjList[u].add(v);
}
// Prints all paths from
// 's' to 'd'
public void printAllPaths(int s, int d)
{
boolean[] isVisited = new boolean[v];
ArrayList<Integer> pathList = new ArrayList<>();
//add source to path[]
pathList.add(s);
//Call recursive utility
printAllPathsUtil(s, d, isVisited, pathList);
}
// A recursive function to print
// all paths from 'u' to 'd'.
// isVisited[] keeps track of
// vertices in current path.
// localPathList<> stores actual
// vertices in the current path
private void printAllPathsUtil(Integer u, Integer d,
boolean[] isVisited,
List<Integer> localPathList) {
// Mark the current node
isVisited[u] = true;
if (u.equals(d))
{
System.out.println(localPathList);
}
// Recur for all the vertices
// adjacent to current vertex
for (Integer i : adjList[u])
{
if (!isVisited[i])
{
// store current node
// in path[]
localPathList.add(i);
printAllPathsUtil(i, d, isVisited, localPathList);
// remove current node
// in path[]
localPathList.remove(i);
}
}
// Mark the current node
isVisited[u] = false;
}
// Driver program
public static void main(String[] args)
{
// Create a sample graph
Graph g = new Graph(7);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(0,3);
g.addEdge(1,5);
g.addEdge(1,6);
g.addEdge(2,4);
g.addEdge(2,1);
g.addEdge(3,2);
g.addEdge(3,4);
// arbitrary source
int s = 0;
// arbitrary destination
int d = 4;
System.out.println("Following are all different paths from "+s+" to "+d);
g.printAllPaths(s, d);
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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