Common Graph Problems - rFronteddu/general_wiki GitHub Wiki

Graph Traversal

  • DFS (Go deep before wide): start → go to neighbor → neighbor of neighbor → …
    • Time: O(n + links)
    • Space: O(n)
  • BFS (Go deep before wide): start → go to neighbor → neighbor of neighbor → …
  • Time: O(V + E)

Count Connected Components in Network

Given n computers labeled 0 to n-1 and a list of bidirectional communication links, find the number of connected components

DFS Approach

static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    for(var neigh : graph.get(node)) {
        if (visited[neigh ]) continue;
        dfs(neigh, graph, visited);
    }
}

public static int countIsolatedCommunicationGroups(List<List<Integer>> links, int n) {
    // Build adjacency list
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    for (List<Integer> link : links) {
        int a = link.get(0);
        int b = link.get(1);
        graph.get(a).add(b);
        graph.get(b).add(a);   // bidirectional
    }

    boolean[] visited = new boolean[n];
    int components = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            dfs(i, graph, visited);
        }
    }

    return components;
}

private static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    for (int nei : graph.get(node)) {
        if (!visited[nei]) dfs(nei, graph, visited);
    }
}

BFS Approach

Note: you only need another nested for if you perform level-order traversal or compute distance (depth)

private static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
    Queue<Integer> q = new LinkedList<>();
    q.add(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int node = q.poll();
        for (int nei : graph.get(node)) {
            if (!visited[nei]) {
                visited[nei] = true;
                q.add(nei);
            }
        }
    }
}

Union Find Approach

public static int countIsolatedCommunicationGroups(List<List<Integer>> links, int n) {
    UnionFind uf = new UnionFind(n);

    for (List<Integer> link : links) {
        uf.union(link.get(0), link.get(1));
    }

    return uf.count();
}

static class UnionFind {
    int[] parent;
    int[] rank;
    int count;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return;

        if (rank[pa] < rank[pb]) parent[pa] = pb;
        else if (rank[pb] < rank[pa]) parent[pb] = pa;
        else {
            parent[pb] = pa;
            rank[pa]++;
        }
        count--;
    }

    int count() { return count; }
}
⚠️ **GitHub.com Fallback** ⚠️