Problem Description: Given a directed graph, a source vertex ‘source’ and a dest

Question

Problem Description: 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 visited, List 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]

Explanation / Answer

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 P
• Subjects

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