🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition)

This content originally appeared on DEV Community and was authored by DevCorner2

Graphs are everywhere — social networks, routes, dependencies, airline pricing, Expedia’s bread and butter 🛫.

This blog covers the most important graph algorithms you’ll need for interviews.

🔹 Problem 1: BFS (Breadth-First Search)

📌 Use BFS to find shortest path in an unweighted graph.

import java.util.*;

public class BFS {
    public static void bfs(int V, List<List<Integer>> adj) {
        boolean[] visited = new boolean[V];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited[0] = true;

        while (!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node + " ");
            for (int nei : adj.get(node)) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    q.offer(nei);
                }
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).addAll(Arrays.asList(1,2));
        adj.get(1).add(3);
        adj.get(2).add(4);
        bfs(V, adj); // Output: 0 1 2 3 4
    }
}

✅ Use cases: Shortest path in unweighted graphs, level-order traversal.

🔹 Problem 2: DFS (Depth-First Search)

📌 Detect connected components (or cycles).

import java.util.*;

public class DFS {
    public static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int nei : adj.get(node)) {
            if (!visited[nei]) dfs(nei, adj, visited);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).addAll(Arrays.asList(1,2));
        adj.get(1).add(3);
        adj.get(2).add(4);

        boolean[] visited = new boolean[V];
        dfs(0, adj, visited); // Output: 0 1 3 2 4
    }
}

✅ Use cases: Connectivity, cycle detection, path existence.

🔹 Problem 3: Topological Sort (Kahn’s Algorithm)

📌 Order tasks based on dependencies.

import java.util.*;

public class TopoSort {
    public static List<Integer> topoSort(int V, List<List<Integer>> adj) {
        int[] indegree = new int[V];
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) indegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) if (indegree[i] == 0) q.offer(i);

        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                indegree[v]--;
                if (indegree[v] == 0) q.offer(v);
            }
        }
        return order;
    }

    public static void main(String[] args) {
        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(5).addAll(Arrays.asList(0, 2));
        adj.get(4).addAll(Arrays.asList(0, 1));
        adj.get(2).add(3);
        adj.get(3).add(1);
        System.out.println(topoSort(V, adj)); // [4, 5, 0, 2, 3, 1]
    }
}

✅ Use cases: Task scheduling, build systems, dependency resolution.

🔹 Problem 4: Dijkstra’s Algorithm

📌 Shortest path in weighted graphs (no negative edges).

import java.util.*;

class Pair {
    int node, dist;
    Pair(int n, int d) { node = n; dist = d; }
}

public class Dijkstra {
    public static int[] dijkstra(int V, List<List<Pair>> adj, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.offer(new Pair(src, 0));

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            for (Pair nei : adj.get(cur.node)) {
                if (dist[cur.node] + nei.dist < dist[nei.node]) {
                    dist[nei.node] = dist[cur.node] + nei.dist;
                    pq.offer(new Pair(nei.node, dist[nei.node]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(new Pair(1, 2));
        adj.get(0).add(new Pair(2, 4));
        adj.get(1).add(new Pair(2, 1));
        adj.get(1).add(new Pair(3, 7));
        adj.get(2).add(new Pair(4, 3));
        int[] dist = dijkstra(V, adj, 0);
        System.out.println(Arrays.toString(dist)); // [0, 2, 3, 9, 6]
    }
}

✅ Use cases: Route optimization, shortest path in road networks.

🔹 Problem 5: Bellman-Ford

📌 Shortest path with negative edges.

import java.util.*;

class Edge {
    int u, v, w;
    Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
}

public class BellmanFord {
    public static int[] bellmanFord(int V, List<Edge> edges, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int i = 1; i < V; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != Integer.MAX_VALUE && dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List<Edge> edges = Arrays.asList(
            new Edge(0,1,4), new Edge(0,2,5), new Edge(1,2,-3), new Edge(2,3,4)
        );
        System.out.println(Arrays.toString(bellmanFord(4, edges, 0))); // [0, 4, 1, 5]
    }
}

✅ Use cases: Graphs with negative weights, currency arbitrage detection.

🔹 Problem 6: Floyd-Warshall

📌 All-pairs shortest path.

public class FloydWarshall {
    static final int INF = 1000000;

    public static void floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        for (int i = 0; i < V; i++) 
            System.arraycopy(graph[i], 0, dist[i], 0, V);

        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        for (int[] row : dist) {
            for (int d : row) System.out.print((d == INF ? "INF" : d) + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int INF = FloydWarshall.INF;
        int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };
        floydWarshall(graph);
    }
}

✅ Use cases: Network routing, all-pairs distance.

🔹 Problem 7: Kruskal’s MST (Minimum Spanning Tree)

import java.util.*;

class Kruskal {
    static int find(int[] parent, int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent, parent[i]);
    }

    static void union(int[] parent, int[] rank, int x, int y) {
        int xr = find(parent, x), yr = find(parent, y);
        if (rank[xr] < rank[yr]) parent[xr] = yr;
        else if (rank[yr] < rank[xr]) parent[yr] = xr;
        else { parent[yr] = xr; rank[xr]++; }
    }

    public static int kruskal(int V, int[][] edges) {
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        int[] parent = new int[V], rank = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        int mst = 0;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (find(parent, u) != find(parent, v)) {
                mst += w;
                union(parent, rank, u, v);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
        System.out.println(kruskal(4, edges)); // 19
    }
}

✅ Use cases: Network design, cost minimization.

🔹 Problem 8: Prim’s MST

import java.util.*;

public class Prim {
    public static int prim(int V, List<List<Pair>> adj) {
        boolean[] inMST = new boolean[V];
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.offer(new Pair(0, 0));

        int mst = 0;
        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            if (inMST[cur.node]) continue;
            inMST[cur.node] = true;
            mst += cur.dist;

            for (Pair nei : adj.get(cur.node)) {
                if (!inMST[nei.node]) pq.offer(nei);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(new Pair(1, 2));
        adj.get(0).add(new Pair(3, 6));
        adj.get(1).add(new Pair(2, 3));
        adj.get(1).add(new Pair(3, 8));
        adj.get(1).add(new Pair(4, 5));
        adj.get(2).add(new Pair(4, 7));
        adj.get(3).add(new Pair(4, 9));

        System.out.println(prim(V, adj)); // 16
    }
}

✅ Use cases: Network cabling, spanning trees.

📊 Expedia Graph Key Insights

Traversal (BFS/DFS) → fundamental for most graph problems.
Topo Sort → always asked in scheduling/dependency questions.
Dijkstra & Bellman-Ford → routing & pathfinding.
MST (Kruskal/Prim) → minimize network cost.
Floyd-Warshall → niche, but demonstrates all-pairs handling.

👉 In Blog 12, we’ll move into Dynamic Programming (DP) — Expedia tests a lot of classic DP + state compression problems.

This content originally appeared on DEV Community and was authored by DevCorner2

Print Share Comment Cite Upload Translate Updates

APA

DevCorner2 | Sciencx (2025-08-26T08:48:54+00:00) 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition). Retrieved from https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/

MLA

" » 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition)." DevCorner2 | Sciencx - Tuesday August 26, 2025, https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/

HARVARD

DevCorner2 | Sciencx Tuesday August 26, 2025 » 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition)., viewed ,<https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/>

VANCOUVER

DevCorner2 | Sciencx - » 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition). [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/

CHICAGO

" » 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition)." DevCorner2 | Sciencx - Accessed . https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/

IEEE

" » 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition)." DevCorner2 | Sciencx [Online]. Available: https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/. [Accessed: ]

rf:citation

» 🚀 Blog 11: Graph Algorithms — DSA Prep (Mega Edition) | DevCorner2 | Sciencx | https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-11-graph-algorithms-dsa-prep-mega-edition/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.