Graphs

Definition

---

Graph Representations

---

Big O Complexity

---

When to Use

---

Pros and Cons

---

Implementation

Adjacency List Graph

public class Graph {
    private Map<Integer, List<Integer>> adjList;
    private boolean directed;

    public Graph(boolean directed) {
        this.adjList = new HashMap<>();
        this.directed = directed;
    }

    public void addVertex(int v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }

    public void addEdge(int src, int dest) {
        addVertex(src);
        addVertex(dest);
        adjList.get(src).add(dest);
        if (!directed) {
            adjList.get(dest).add(src);
        }
    }

    public void removeEdge(int src, int dest) {
        adjList.get(src).remove(Integer.valueOf(dest));
        if (!directed) {
            adjList.get(dest).remove(Integer.valueOf(src));
        }
    }

    public List<Integer> getNeighbors(int v) {
        return adjList.getOrDefault(v, Collections.emptyList());
    }

    public boolean hasEdge(int src, int dest) {
        return adjList.containsKey(src) && adjList.get(src).contains(dest);
    }

    public int getVertexCount() {
        return adjList.size();
    }

    public Set<Integer> getVertices() {
        return adjList.keySet();
    }
}

Weighted Graph

public class WeightedGraph {
    private Map<Integer, List<int[]>> adjList;  // int[] = {neighbor, weight}

    public WeightedGraph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int src, int dest, int weight) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.putIfAbsent(dest, new ArrayList<>());
        adjList.get(src).add(new int[]{dest, weight});
        adjList.get(dest).add(new int[]{src, weight});  // Undirected
    }

    public List<int[]> getNeighbors(int v) {
        return adjList.getOrDefault(v, Collections.emptyList());
    }
}

---

Graph Traversals

BFS (Breadth-First Search)

// Level-by-level traversal using queue
public List<Integer> bfs(int start) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(start);
    visited.add(start);

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

        for (int neighbor : adjList.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

// BFS with levels
public List<List<Integer>> bfsWithLevels(int start) {
    List<List<Integer>> levels = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            int node = queue.poll();
            currentLevel.add(node);

            for (int neighbor : adjList.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        levels.add(currentLevel);
    }
    return levels;
}

DFS (Depth-First Search)

// Recursive DFS
public List<Integer> dfsRecursive(int start) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    dfsHelper(start, visited, result);
    return result;
}

private void dfsHelper(int node, Set<Integer> visited, List<Integer> result) {
    visited.add(node);
    result.add(node);

    for (int neighbor : adjList.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            dfsHelper(neighbor, visited, result);
        }
    }
}

// Iterative DFS using stack
public List<Integer> dfsIterative(int start) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) continue;

        visited.add(node);
        result.add(node);

        for (int neighbor : adjList.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
    return result;
}

---

Common Graph Algorithms

Detect Cycle

// Undirected graph - using DFS
public boolean hasCycleUndirected() {
    Set<Integer> visited = new HashSet<>();
    for (int node : adjList.keySet()) {
        if (!visited.contains(node)) {
            if (hasCycleHelper(node, -1, visited)) {
                return true;
            }
        }
    }
    return false;
}

private boolean hasCycleHelper(int node, int parent, Set<Integer> visited) {
    visited.add(node);
    for (int neighbor : adjList.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            if (hasCycleHelper(neighbor, node, visited)) return true;
        } else if (neighbor != parent) {
            return true;  // Back edge found
        }
    }
    return false;
}

// Directed graph - using colors (White/Gray/Black)
public boolean hasCycleDirected() {
    Set<Integer> white = new HashSet<>(adjList.keySet());
    Set<Integer> gray = new HashSet<>();
    Set<Integer> black = new HashSet<>();

    while (!white.isEmpty()) {
        int node = white.iterator().next();
        if (hasCycleDirectedHelper(node, white, gray, black)) {
            return true;
        }
    }
    return false;
}

private boolean hasCycleDirectedHelper(int node, Set<Integer> white,
                                        Set<Integer> gray, Set<Integer> black) {
    white.remove(node);
    gray.add(node);

    for (int neighbor : adjList.getOrDefault(node, List.of())) {
        if (black.contains(neighbor)) continue;
        if (gray.contains(neighbor)) return true;  // Back edge
        if (hasCycleDirectedHelper(neighbor, white, gray, black)) return true;
    }

    gray.remove(node);
    black.add(node);
    return false;
}

Topological Sort (DAG only)

// Using DFS
public List<Integer> topologicalSort() {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();

    for (int node : adjList.keySet()) {
        if (!visited.contains(node)) {
            topSortHelper(node, visited, stack);
        }
    }

    return new ArrayList<>(stack);
}

private void topSortHelper(int node, Set<Integer> visited, Deque<Integer> stack) {
    visited.add(node);
    for (int neighbor : adjList.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) {
            topSortHelper(neighbor, visited, stack);
        }
    }
    stack.push(node);
}

// Using Kahn's Algorithm (BFS)
public List<Integer> topologicalSortKahn() {
    Map<Integer, Integer> inDegree = new HashMap<>();
    for (int node : adjList.keySet()) {
        inDegree.putIfAbsent(node, 0);
        for (int neighbor : adjList.get(node)) {
            inDegree.merge(neighbor, 1, Integer::sum);
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int node : inDegree.keySet()) {
        if (inDegree.get(node) == 0) {
            queue.offer(node);
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : adjList.getOrDefault(node, List.of())) {
            inDegree.merge(neighbor, -1, Integer::sum);
            if (inDegree.get(neighbor) == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return result.size() == adjList.size() ? result : Collections.emptyList();
}

Shortest Path - Dijkstra

public Map<Integer, Integer> dijkstra(int start) {
    Map<Integer, Integer> distances = new HashMap<>();
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    for (int node : adjList.keySet()) {
        distances.put(node, Integer.MAX_VALUE);
    }
    distances.put(start, 0);
    pq.offer(new int[]{start, 0});

    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int node = current[0];
        int dist = current[1];

        if (dist > distances.get(node)) continue;

        for (int[] edge : getWeightedNeighbors(node)) {
            int neighbor = edge[0];
            int weight = edge[1];
            int newDist = dist + weight;

            if (newDist < distances.get(neighbor)) {
                distances.put(neighbor, newDist);
                pq.offer(new int[]{neighbor, newDist});
            }
        }
    }
    return distances;
}

Number of Connected Components

public int countComponents(int n, int[][] edges) {
    // Build graph
    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<>());
    }
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // Count components using DFS
    Set<Integer> visited = new HashSet<>();
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited.contains(i)) {
            dfs(i, graph, visited);
            count++;
        }
    }
    return count;
}

private void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
    visited.add(node);
    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, graph, visited);
        }
    }
}

Clone Graph

public Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> visited = new HashMap<>();
    return cloneHelper(node, visited);
}

private Node cloneHelper(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }

    Node clone = new Node(node.val);
    visited.put(node, clone);

    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(cloneHelper(neighbor, visited));
    }
    return clone;
}

---

Common Graph Problems

---