Initialize queue
Mark source as visited
Enqueue source

While queue not empty:
    node = dequeue

    For each neighbor of node:
        If not visited:
            mark visited
            enqueue neighbor

When to use

• Shortest path (unweighted graph)
• Level order traversal
• Multi-source BFS

Time: O(V + E)

public void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Function dfs(node):
    mark node visited

    For each neighbor:
        If not visited:
            dfs(neighbor)

When to use

• Connected components
• Cycle detection
• Backtracking
• Topological sort (DFS version)

Time: O(V + E)

public void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

Compute indegree for all nodes
Add nodes with indegree 0 to queue

While queue not empty:
    node = dequeue
    add to result

    For each neighbor:
        decrease indegree
        If indegree becomes 0:
            enqueue neighbor

When to use

• Task scheduling
• Dependency ordering
• DAG problems

Cycle check: If result size != V → cycle exists

public List<Integer> topoSort(int V, List<List<Integer>> graph) {
    int[] indegree = new int[V];

    for (int i = 0; i < V; i++) {
        for (int neighbor : graph.get(i)) {
            indegree[neighbor]++;
        }
    }

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

    List<Integer> result = new ArrayList<>();

    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);

        for (int neighbor : graph.get(node)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }

    return result;
}

Initialize distance array with ∞
distance[source] = 0

Min-heap with (distance, node)

While heap not empty:
    pop node with smallest distance

    For each neighbor:
        If new distance < recorded distance:
            update distance
            push into heap

When to use

• Weighted shortest path
• Non-negative edges only

Time: O((V + E) log V)

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

public int[] dijkstra(int V, List<List<Pair>> graph, 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 current = pq.poll();

        for (Pair neighbor : graph.get(current.node)) {
            int newDist = current.dist + neighbor.dist;

            if (newDist < dist[neighbor.node]) {
                dist[neighbor.node] = newDist;
                pq.offer(new Pair(neighbor.node, newDist));
            }
        }
    }
    return dist;
}

Do NOT use if negative edges exist.

Initialize parent[i] = i
Initialize rank[i] = 0

Find(x):
    If parent[x] != x:
        parent[x] = Find(parent[x])
    Return parent[x]

Union(x, y):
    rootX = Find(x)
    rootY = Find(y)

    If roots differ:
        attach smaller rank tree under larger

When to use

• Cycle detection
• Kruskal MST
• Connected components

Amortized: ~O(α(n))

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[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 x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

Sort edges by weight
Initialize Union-Find

For each edge:
    If endpoints not connected:
        add edge to MST
        union endpoints

When to use

• Minimum cost to connect all nodes

Time: O(E log E)

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

public int kruskal(int V, List<Edge> edges) {
    Collections.sort(edges, (a, b) -> a.weight - b.weight);

    UnionFind uf = new UnionFind(V);
    int mstWeight = 0;

    for (Edge e : edges) {
        if (uf.find(e.u) != uf.find(e.v)) {
            mstWeight += e.weight;
            uf.union(e.u, e.v);
        }
    }
    return mstWeight;
}

Count vertices with odd degree

If 0 odd → Eulerian Circuit
If 2 odd → Eulerian Path
Else → Not possible

Directed graph condition

• In-degree == Out-degree (circuit)
• Exactly one node with out = in + 1 (path start)

public boolean hasEulerianCircuit(int V, List<List<Integer>> graph) {
    for (int i = 0; i < V; i++) {
        if (graph.get(i).size() % 2 != 0)
            return false;
    }
    return true;
}

Perform DFS/BFS
Maintain xor_value along path

For neighbor:
    new_xor = current_xor XOR edge_weight

When to use

• XOR path queries
• Bitwise constraints in graph
• Tree XOR prefix trick

public void dfsXor(int node, int parent,
                   List<List<int[]>> graph,
                   int currentXor,
                   int[] xorValue) {

    xorValue[node] = currentXor;

    for (int[] edge : graph.get(node)) {
        int neighbor = edge[0];
        int weight = edge[1];

        if (neighbor != parent) {
            dfsXor(neighbor, node, graph,
                   currentXor ^ weight, xorValue);
        }
    }
}