Graph Theory

Definition

Graph node for an undirected graph

class GraphNode {
    int label;
    List<GraphNode> neighbors;    
    GraphNode(int val, List<GraphNode> nodes) {
        label = val;
        neighbors = nodes;
    }
}

Alternatively, we can add the neighbors later. This simplifies creating the node.

class GraphNode {
    int label;
    List<GraphNode> neighbors;    
    GraphNode(int val) {
        label = val;
        neighbors = new ArrayList<>();
    }
}

We can use the same graph node for a directed graph. But just keep in mind when adding an edge it is bidirectional.

Cycle Detection

Cycle detection is naturally associated with DFS. Using BFS is just unnatural since it doesn't keep track of visited but unfinished nodes on stack and is hard to keep a parent pointer.

Detect Cycle in Directed Graph
For directed graph, a cycle exists when there's a back edge in the DFS tree.

// return true if cycle is detected, false if the graph acyclic
boolean cycleDFS(Map<Integer, List<Integer>> graph, Integer visit, 
                 Set<Integer> visited, Set<Integer> onStack) {
    // previsit
    visited.add(visit);
    onStack.add(visit);
    // visit each neighbor
    for (Integer neighbor : graph.get(visit)) {
        if (!visited.contains(neighbor) && 
            cycleDFS(graph, neighbor, visited, onStack)) {
            return true;
        } else if (onStack.contains(neighbor)) {
            // back edge
            return true;
        } else {
            // cross or forward
            // do nothing
        }
    }
    // postvisit
    onStack.remove(visit);
    return false;
}

Why we can't just return cycleDFS(graph, neighbor, visited, onStack)? We have to keep in mind what happens when the program backtracks. It will return false when it reaches the end of a path, we don't want to return false just yet. We want to return false at the root level. Therefore we have to "use" the boolean return value somewhere.

Detect Cycle in Undirected Graph
For undirected graph, a cycle exists when a node's neighbor is already visited and is not its parent.

boolean cycleDFS2(Map<Integer, List<Integer>> graph, Integer visit, 
                  Integer parent, Set<Integer> visited) {
    visited.add(visit);
    for (Integer neighbor : graph.get(visit)) { 
        if (visited.contains(neighbor) && !neighbor.equals(parent)) {
            return true;
        }
        if (!visited.contains(neighbor) && 
            cycleDFS2(graph, neighbor, visit, visited)) {
            return true;
        }
    }
    return false;
}

Note: neighbor != parent won't work here because they are two references to the Integer object. We want to compare the value not the reference ◟ʕ´∀`ʔ◞

Topological Sort

Connected Components

Reference

MIT 6.006 - Recitation 14 DFS Edge Classification