5 graph problems you should know in Java
A Graph is a collection of nodes and edges. Graphs are really useful to explain relationships between things, for instance we can represent a map of cities with a graph.
We have directed and undirected graphs. The first type of graphs in order to navigate from node A to node B there must be an edge with a direction from A to B. In undirected graphs if there’s an edge between A and B we can navigate from A to B and from B to A.
How can we implement graph data structure
There are 2 ways of representing a Graph, one is with a adjacency matrix and another way is with an adjacency list. The second one is normaly the way to go and is the most common way to represent a Graph.
In Java it can be implemented with a Map with keys as nodes and as value the list of nodes that are adjacent to that key. Another way to represent a graph is with LinkedList where each value of this data structure is also a LinkedList with all the nodes adjacent to that node in that position. Even that a node has no neighbours it should appear in the map but with empty value.
Breath first search (BFS)
In this algorithm we traverse the Graph using a Queue. In the course of the traversal every node of the Graph changes it’s state from unvisited to visited. Only when we have visited all the adjacent nodes from the current node we move to the next node.
public class Graph {
private final int V;
private final LinkedList<Integer> adj[];
private final Queue<Integer> queue;
public Graph(int v){
this.V = v;
this.adj = new LinkedList[v];
for (int i=0; i<v; i++){
adj[i] = new LinkedList<>();
}
this.queue = new LinkedList<Integer>();
}
public void addEdge(int v,int w){
this.adj[v].add(w);
}
public void BFS(int n){
boolean visited[] = new boolean[V];
visited[n]=true;
queue.add(n);
while (queue.size() != 0){
n = queue.poll();
System.out.print(n + " ");
for (int a: adj[n]){
if (!visited[a]){
visited[a] = true;
queue.add(a);
}
}
}
}
}
Depth first search (DFS)
In this case we start in a node and we pick a direction and continue in the same direction until we cannot continue. You are exploring one direction as far as you can before switching directions.
This algorithm uses an stack in his iterative version. We have to see as a vertical data structure.
public void DFS(int n){
boolean visited[] = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(n);
while(!stack.empty()) {
n = stack.peek();
stack.pop();
if(visited[n] == false) {
System.out.print(n + " ");
visited[n] = true;
}
for (int a:adj[n]) {
if (!visited[a]){
stack.push(a);
}
}
}
}
Problem 1 - Find if there’s a path between 2 nodes
public boolean hasPath(int src, int dest, boolean []visited){
if(visited[node]){
return false;
}
if(src==dst) return true;
visited[node]=true;
for (int neighbor: adj[src]){
if(hasPath(neighbor, dst, visited)){
return true;
}
}
return false;
}
Problem 2 - Count the number of connected components
public int connectedComponentsCount(){
boolean visited[] = new boolean[V];
int count = 0;
for (int i = 0; i < V; i++){
if (explore(i, visited)){
count++;
}
}
return count;
}
public boolean explore(int node, boolean visited[]){
if(visited[node]){
return false;
}
visited[node]=true;
for(int neighbor: adj[node]){
explore(graph, neighbor, visited);
}
return true;
}
Problem 3 - Find the largest component
public int largestComponent() {
boolean []visited = new boolean[V];
int largest = 0;
for (int i = 0; i < V; i++) {
int result = exploreSize(i, visited);
if (result > largest) {
largest = result;
}
}
return largest;
}
public int exploreSize(int node, boolean[] visited) {
if (visited[node]) {
return 0;
}
visited[node] = true;
int size = 1;
for (int neighbor : adj[node]) {
size += exploreSize(neighbor, visited);
}
return size;
}
Problem 4 - Find the shortest path between 2 nodes
class Node{
int value;
int distance;
}
Queue<Node> queue = new ArrayDeque<>();
public int shortestPath(int src, int dest) {
boolean[] visited = new boolean[V];
visited[src] = true;
queue.add(new Node(src, 0));
while (queue.size() != 0) {
Node node = queue.poll();
if (node.value == dest) {
return node.distance;
}
System.out.print(node.value + " ");
for (int a : adj[node.value]) {
if (!visited[a]) {
visited[a] = true;
queue.add(new Node(a, node.distance + 1));
}
}
}
return -1;
}
public static void main(String args[]) {
Graph g = new Graph(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 1);
g.addEdge(2, 0);
g.addEdge(3, 2);
g.addEdge(3, 1);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(5, 6);
g.addEdge(6, 5);
System.out.println("Shortest path: " + g.shortestPath(4, 0));
}
Problem 5 - Count the number of islands
public class IslandCounter {
public int countIslands(char[][] grid) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
int islands = 0;
for (int row = 0; row < grid.length; row++) {
for (int column = 0; column < grid[0].length; column++) {
if (explore(grid, row, column, visited)) {
islands++;
}
}
}
return islands;
}
public boolean explore(char[][] grid, int row, int column, boolean[][] visited) {
boolean rowInbounds = 0 <= row && row < grid.length;
boolean columnInbounds = 0 <= column && column < grid[0].length;
if (!rowInbounds || !columnInbounds) return false;
if (visited[row][column]) return false;
if (grid[row][column] == 'W') return false;
visited[row][column] = true;
explore(grid, row - 1, column, visited);
explore(grid, row + 1, column, visited);
explore(grid, row, column - 1, visited);
explore(grid, row, column + 1, visited);
return true;
}
public static void main(String[] args) {
IslandCounter islandCounter = new IslandCounter();
char [][] grid = { {'L','L', 'W','W', 'L'}
,{'L','L', 'W','W', 'W'}
,{'W','W', 'W','W', 'W'}
,{'W','W', 'W','L', 'L'}
,{'L','W', 'W','L', 'L'}};
System.out.println("Number of islands in this grid :" +islandCounter.countIslands(grid));
}
}
Conclusion
In this post we have seen how to define a graph data structure in Java. We have seen 5 problems related with graphs and how to implement them using Java. We have seen 2 key algorithms that help us solve this kind of problems, DFS and BFS.
Comments