Blog Details

Graph Implementation

1. A graph

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links.

It can be divided into three categories:

  • Undirected graph
  • Directed graph
  • Weighted graph

2. Implementation

To store the graph, you can use either adjacency metrix or adjacency list. For weighted graph, the value stored in the metrix or list is the weight.

2.1 Graph Adjacent List

package com.frank.graph;

import java.util.LinkedList;

public class GraphAdjList {
	private int v; // vertex number
	private LinkedList<Integer> adj[]; 
	
	@SuppressWarnings("unchecked")
	public GraphAdjList(int v) {
		this.setV(v);
		adj = new LinkedList[v];
		for(int i = 0; i < v; i ++) {
			adj[i] = new LinkedList<Integer>();
		}
	}
	
	public void addEdge(int s, int t) {
		adj[s].add(t);
		adj[t].add(s);
	}

	public int getV() {
		return v;
	}

	public void setV(int v) {
		this.v = v;
	}
	
	public LinkedList<Integer>[] getAdj() {
		return adj;
	}

	public void setAdj(LinkedList<Integer>[] adj) {
		this.adj = adj;
	}
}

2.2 Adjacency Metrix

package com.frank.graph;

public class GraphAdjMetrix {
	private int v; // Vertex in the graph
	private int[][] adj;
			
	public GraphAdjMetrix(int v) {
		this.setV(v); 
		adj = new int[v][v];
	}
	
	public void addEdge(int i, int j) {
		adj[i][j] = 1;
		adj[j][i] = 1; // If the graph is directed, remove this line. 
	}

	public int getV() {
		return v;
	}

	public void setV(int v) {
		this.v = v;
	}
}

2.3 Weighted Metrix – how close is your friendship with one firend?

package com.frank.graph;

public class GraphWeightedAdjMetrix {
	private int v; // vertex in graph
	private int[][] adj;
	
	public GraphWeightedAdjMetrix(int v) {
		this.setV(v); 
		adj = new int[v][v];
	}
	
	public void addEdge(int i, int j, int weigth) {
		adj[i][j] = weigth;
		adj[j][i] = weigth; // If it is directed, remove this line
	}

	public int getV() {
		return v;
	}

	public void setV(int v) {
		this.v = v;
	}
}

3. Breadth-First Search and Depth-First Search

package com.frank.graph.search;

import java.util.LinkedList;
import java.util.Queue;

import com.frank.graph.GraphAdjList;


public class GraphSearchUtil {
	
	/**
	 * Breadth-First Search
	 * @param graph: graph
	 * @param s: starting vertex
	 * @param t: ending vertex
	 */
	public static void bfs(GraphAdjList graph, int s, int t) {
		if (s == t) {
			return;
		}
		
		int v= graph.getV();
		boolean[] visited = new boolean[v];
		
		visited[s] = true;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(s);
		
		int[] prev = new int[v];
		for (int i = 0; i < v; i++) {
			prev[i] = -1;
		}
		
		while(queue.size() != 0) {
			int w = queue.poll();
			LinkedList<Integer>[] adj = graph.getAdj();
			for (int i = 0; i < adj[w].size(); i++) {
				int q = adj[w].get(i);
				if (!visited[q]) {
					prev[q] = w;
					if (q == t) {
						print(prev, s, t);
						return;
					}
					visited[q] = true;
					queue.add(q);
				}
			}
		}
	}
	
	private static void print(int[] prev, int s, int t) {
		if (prev[t] != -1 && t != s) {
			print(prev, s, prev[t]);
		}
		System.out.println(t + " ");
	}
	
	private static boolean found = false;
	
	public static void dfs(GraphAdjList graph, int s, int t) {
		found = false;
		int v = graph.getV();
		boolean[] visited = new boolean[v];
		int[] prev = new int[v];
		for(int i = 0; i < v; i ++) {
			prev[i] = -1;
		}
		
		recurDfs(graph, s, t, visited, prev);
		print(prev, s, t);
	}
	
	private static void recurDfs(GraphAdjList graph, int w, int t, boolean[] visited, int[] prev) {
		if (found == true) {
			return;
		}
		visited[w] = true;
		if (w == t) {
			found = true;
			return;
		}
		LinkedList<Integer>[] adj = graph.getAdj();
		for(int i = 0; i < adj[w].size(); i ++) {
			int q = adj[w].get(i);
			if (!visited[q]) {
				prev[q] = w;
				recurDfs(graph, q, t, visited, prev);
			}
		}
	}
}

4. Test

package junit.test;


import org.junit.jupiter.api.Test;

import com.frank.graph.GraphAdjList;
import com.frank.graph.search.GraphSearchUtil;

class GraphSearchUtilTest {

	@Test
	void testBfs() {
		GraphAdjList graph = new GraphAdjList(5);
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(1, 3);
		graph.addEdge(0, 3);
		graph.addEdge(3, 4);
		graph.addEdge(2, 4);
		graph.addEdge(1, 4);
		GraphSearchUtil.bfs(graph, 0, 4);
	}

	@Test
	void testBfs1() {
		GraphAdjList graph = new GraphAdjList(8);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(2, 5);
		graph.addEdge(3, 4);
		graph.addEdge(4, 5);
		graph.addEdge(4, 6);
		graph.addEdge(5, 7);
		graph.addEdge(6, 7);
		GraphSearchUtil.dfs(graph, 0, 7);
	}
}

5. Time and Space Complexity

Both BFS and DFS, time and space complexity are:

Time: O(E) // E: edges

Space: O(V) // V: vertex