This is a simple implementation of a directed Graph and searching whether there is a path between node u and node v
package vvirlan.graph.simplegraph;
import java.util.LinkedList;
import java.util.List;
public class Graph {
// Number of vertices
private final int v;
// Adjacency List
private final List<Integer>[] adj;
Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
}
}
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
int u = 1;
int v = 3;
if (graph.isReachable(u, v)) {
System.out.printf("There is a path from %s to %s%n\n", u, v);
} else {
System.out.printf("There is no path from %s to %s%n\n", u, v);
}
}
void addEdge(int from, int to) {
adj[from].add(to);
}
/**
* BFS traversal. Is reachable from source to dest
*
* @param source
* @param dest
* @return
*/
boolean isReachable(int source, int dest) {
boolean[] visited = new boolean[this.v];
LinkedList<Integer> queue = new LinkedList<>();
visited[source] = true;
queue.add(source);
while (queue.size() > 0) {
int current = queue.poll();
List<Integer> outgoingVertices = adj[current];
for (Integer vertex : outgoingVertices) {
if (vertex == dest) {
return true;
}
if (!visited[vertex]) {
visited[vertex] = true;
queue.add(vertex);
}
}
}
//If BFS is complete without visited d
return false;
}
}