Graph algorithms at a glance
Want to revise graph algorithms for coding interview? You've come to the right place!
Introduction
For developers preparing for coding interviews, this article offers a concise compilation of essential graph algorithm implementations. It's designed for quick revision, assuming you're already familiar with these algorithms.
DFS
Traversal in depth first manner. Traverse deep until nothing is left, then recursively go back and keep on diving.
// Recursive function for DFS traversal
static void DFSRec(List<List<Integer> > adj,
boolean[] visited, int s){
// Mark the current vertex as visited
visited[s] = true;
// Print the current vertex
System.out.print(s + " ");
// Recursively visit all adjacent vertices that are
// not visited yet
for (int i : adj.get(s)) {
if (!visited[i]) {
DFSRec(adj, visited, i);
}
}
}Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V + E), since an extra visited array of size V is required, And stack size for recursive calls to DFSRec function.
BFS
Traverse layer by layer. source node first, then all nodes which are at distance 1 from source, then which are distance 2 from it and so on. A queue data structure should be used to keep the order of nodes based on distance from source node.
// BFS from given source s
static void bfs(List<List<Integer>> adj, int s) {
// Create a queue for BFS
Queue<Integer> q = new LinkedList<>();
// Initially mark all the vertices as not visited
// When we push a vertex into the q, we mark it as
// visited
boolean[] visited = new boolean[adj.size()];
// Mark the source node as visited and enqueue it
visited[s] = true;
q.add(s);
// Iterate over the queue
while (!q.isEmpty()) {
// Dequeue a vertex and print it
int curr = q.poll();
System.out.print(curr + " ");
// Get all adjacent vertices of the dequeued vertex
// If an adjacent has not been visited, mark it
// visited and enqueue it
for (int x : adj.get(curr)) {
if (!visited[x]) {
visited[x] = true;
q.add(x);
}
}
}
}Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.
Auxiliary Space: O(V)
Topological sort
There are two ways to perform topological sorting on a graph.
Via BFS
// Function to return array containing vertices in
// Topological order.
public static int[] topologicalSort(
List<List<Integer> > adj, int V) {
// Array to store indegree of each vertex
int[] indegree = new int[V];
for (int i = 0; i < V; i++) {
for (int it : adj.get(i)) {
indegree[it]++;
}
}
// Queue to store vertices with indegree 0
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
int[] result = new int[V];
int index = 0;
while (!q.isEmpty()) {
int node = q.poll();
result[index++] = node;
// Decrease indegree of adjacent vertices as the
// current node is in topological order
for (int it : adj.get(node)) {
indegree[it]--;
// If indegree becomes 0, push it to the
// queue
if (indegree[it] == 0) {
q.offer(it);
}
}
}
// Check for cycle
if (index != V) {
System.out.println("Graph contains cycle!");
return new int[0];
}
return result;
}Via DFS
// Function to perform DFS and topological sorting
static void topologicalSortUtil(int v,
ArrayList<ArrayList<Integer>> adj,
boolean[] visited, Stack<Integer> st) {
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj.get(v)) {
if (!visited[i]) {
topologicalSortUtil(i, adj, visited, st);
}
}
// Push current vertex to stack
// which stores the result
st.push(v);
}
// Function to perform Topological Sort
static ArrayList<Integer> topologicalSort(
ArrayList<ArrayList<Integer>> adj) {
int V = adj.size();
// Stack to store the result
Stack<Integer> st = new Stack<>();
boolean[] visited = new boolean[V];
// Call the recursive helper function to store
// Topological Sort starting from all vertices one by one
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topologicalSortUtil(i, adj, visited, st);
}
}
ArrayList<Integer> ans = new ArrayList<>();
// Append contents of stack
while (!st.isEmpty()) {
ans.add(st.pop());
}
return ans;
}Time Complexity: O(V+E).
Auxiliary space: O(V). The extra space is needed for the stack/queue
Dijkstra
Find the shortest distance of all nodes from source node in a directed graph with positive weights.
The problem with negative weights arises from the fact that Dijkstra’s algorithm assumes that once a node is added to the set of visited nodes, its distance is finalized and will not change. However, in the presence of negative weights, this assumption can lead to incorrect results. Ref
void shortestPath(int src) {
PriorityQueue<iPair> pq = new PriorityQueue<>(V, Comparator.comparingInt(o -> o.first));
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.add(new iPair(0, src)); // class iPair {int first, second;}
dist[src] = 0;
while (!pq.isEmpty()) {
int u = pq.poll().second;
for (iPair v : adj.get(u)) {
if (dist[v.first] > dist[u] + v.second) {
dist[v.first] = dist[u] + v.second;
pq.add(new iPair(dist[v.first], v.first));
}
}
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++) {
System.out.println(i + "\t\t" + dist[i]);
}
}Time complexity: O((V + E) log V), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V), where V is the number of vertices and E is the number of edges in the graph.
Bellman ford
Bellman-Ford is a single source shortest path algorithm. It effectively works in the cases of negative edges and is able to detect negative cycles as well. It works on the principle of relaxation of the edges.
static int[] bellmanFord(int V, int[][] edges, int src) {
// Initially distance from source to all other vertices
// is not known(Infinite).
int[] dist = new int[V];
Arrays.fill(dist, (int)1e8);
dist[src] = 0;
// Relaxation of all the edges V times, not (V - 1) as we
// need one additional relaxation to detect negative cycle
for (int i = 0; i < V; i++) {
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int wt = edge[2];
if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {
// If this is the Vth relaxation, then there is
// a negative cycle
if (i == V - 1)
return new int[]{-1};
// Update shortest distance to node v
dist[v] = dist[u] + wt;
}
}
}
return dist;
}Time Complexity: O(V*E)
Floyd Warshall
It’s all pair shortest path finding algorithm whereas bellman and dijkstra were single source shortest path finidng algos. It is DP based.
void floydWarshall(int dist[][])
{
int i, j, k;
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
// If vertex k is on the shortest path
// from i to j, then update the value of
// dist[i][j]
if (dist[i][k] + dist[k][j]
< dist[i][j])
dist[i][j]
= dist[i][k] + dist[k][j];
}
}
}
}Time Complexity: O(V3), where V is the number of vertices in the graph and we run three nested loops each of size V
Auxiliary Space: O(V2), to create a 2-D matrix in order to store the shortest distance for each pair of nodes.
DSU
class DisjointUnionSets {
int[] rank, parent;
int n;
public DisjointUnionSets(int n)
{
rank = new int[n];
parent = new int[n];
this.n = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Returns top level parent of x
int find(int x)
{
return (parent[x] != x)
? parent[x] = find(parent[x]);
: parent[x];
}
// Unites the set that includes x and the set
// that includes y
void union(int x, int y)
{
// Find representatives of two sets
int xRoot = find(x), yRoot = find(y);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[yRoot] < rank[xRoot])
parent[yRoot] = xRoot;
else {
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
}
}[Ref]Time complexity: O(n) for creating n single item sets . The two techniques -path compression with the union by rank/size, the time complexity will reach nearly constant time. It turns out, that the final amortized time complexity is O(α(n)), where α(n) is the inverse Ackermann function, which grows very steadily (it does not even exceed for n<10600 approximately).
Space complexity: O(n) because we need to store n elements in the Disjoint Set Data Structure.
Minimum spanning tree
There are two main algorithms to generate minimum spanning tree.
Krushkal’s Algorithm
It sorts the edges which takes ElogE time and create a DSU on vertices of the graph and takes logV time per edge to check if vertices of the edges are part of the same parent and if not then union them in constant time.
public static int kruskalsMST(int V, int[][] edges) {
// Sort all edges based on weight
Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
// Traverse edges in sorted order
DSU dsu = new DSU(V);
int cost = 0, count = 0;
for (int[] e : edges) {
int x = e[0], y = e[1], w = e[2];
// Make sure that there is no cycle
if (dsu.find(x) != dsu.find(y)) {
dsu.union(x, y);
cost += w;
if (++count == V - 1) break;
}
}
return cost;
}Time Complexity: O(E * log E) or O(E * log V)
Auxiliary Space: O(E+V), where V is the number of vertices and E is the number of edges in the graph.
Prim’s Algorithm
static int spanningTree(int V, int E, int edges[][]) {
ArrayList<ArrayList<Pair>> adj=new ArrayList<>();
for(int i=0;i<V;i++) {
adj.add(new ArrayList<Pair>());
}
for(int i=0;i<edges.length;i++) {
int u=edges[i][0];
int v=edges[i][1];
int wt=edges[i][2];
adj.get(u).add(new Pair(v,wt));
adj.get(v).add(new Pair(u,wt));
}
PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
pq.add(new Pair(0,0));
int[] vis=new int[V];
int s = 0;
while(!pq.isEmpty()) {
Pair node = pq.poll();
int v = node.v;
int wt = node.wt;
if (vis[v] == 1)
continue;
s+=wt;
vis[v]=1;
for(Pair it:adj.get(v))
{
if(vis[it.v]==0)
{
pq.add(new Pair(it.v,it.wt));
}
}
}
return s;
}Time Complexity: O((E+V)*log(V)) where V is the number of vertex and E is the number of edges
Auxiliary Space: O(E+V) where V is the number of vertex and E is the number of edges