Skip to content

Instantly share code, notes, and snippets.

@RehmanaliMomin
Last active March 26, 2018 17:45
Show Gist options
  • Save RehmanaliMomin/fa44fd404b478ba9761924fc3b5a3dc5 to your computer and use it in GitHub Desktop.
Save RehmanaliMomin/fa44fd404b478ba9761924fc3b5a3dc5 to your computer and use it in GitHub Desktop.
Print all possible paths from source to destination in a graph
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class GraphPrintAllPaths {
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
graph.addEdge(2, 3);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(4, 5);
GraphPrintAllPaths p = new GraphPrintAllPaths();
p.printAllPaths(graph,0 , 5);
}
void printAllPaths(Graph g,int s, int d){
boolean[] visited = new boolean[g.vertices];
visited[s]=true;
ArrayList<Integer> p=new ArrayList<>();
print(g,s,d,p,visited);
}
void print(Graph g, int s, int d, ArrayList<Integer> p, boolean[] visited){
p.add(s); // Adding here (1)
visited[s]=true;
Iterator<Node> it = g.adj[s].iterator();
while (it.hasNext()){
Node temp = it.next();
if(temp.dest!=d&&!visited[temp.dest]){
print(g,temp.dest,d,p,visited);
}else if(temp.dest==d){
p.add(d); // Adding here (2)
System.out.println(p);
p.remove(p.size()-1); // Removin here (1)
}
}
// when we recurse back we return the visited boolean value to false, so that it can be ready to see the next path.
p.remove(p.size()-1); // Removing here (2)
visited[s]=false;
}
}
class Graph{
int vertices;
LinkedList<Node> [] adj;
Graph(int vertices){
this.vertices=vertices;
adj= new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adj[i]=new LinkedList<>();
}
}
void addEdge(int a,int b){
Node s = new Node(a,b);
adj[a].addLast(s);
}
}
class Node{
int source;
int dest;
Node(int source,int dest){
this.dest=dest;
this.source=source;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment