Graph Algorithms — Part 2

PREVIOUS: Graph Algorithms — Part 1

Table of Contents

• Depth-first Traversal
• Breadth-first Traversal
• Topological Sorting
• Cycle Detection

In tree traversals, we always start from the root node. In fact, the tree is a kind of graph, so tree traversal algorithms can also apply to graph traversals. However, every tree has a unique root node, and every other node is reachable from the root node. In a graph, some nodes might not be reached from our start node.

Depth-first Traversal

Main idea: select a node to start, and recursively find neighbors.

We start from node A and find the neighbors of A, which are B and E. Let’s assume we select B next. Then we find the neighbors of B and continue with find neighbors of C. Finally, when we reach node D, it does not have any neighbors, our recursion return.

After that, we go back to C and find other neighbors of C, but C does not have any other neighbors. Then go back to B, B has another neighbor D, but we have already traversed D. Finally we go back to A and go to E.

What if we start from B？We cannot reach A & E.

Implementation (Recursion)

public void traverseDFT(String root) {
    var node = nodes.get(root);
    if (node == null) return;
    traverseDFT(node, new HashSet<>());

}

private void traverseDFT(Node root, Set<Node> visitedNodes) {
    // visit the root node
    System.out.println(root);
    visitedNodes.add(root);
    
    // find all neighbors of this node
    for (var node : adjacencyList.get(root)) {
        if (!visitedNodes.contains(node)) traverseDFT(node,visitedNodes);
    }

Implementation (Iteration)

public void traverseDFTIter(String root) {
    var node = nodes.get(root);
    if (node == null) return;
    Stack<Node> nodeStack = new Stack<>();
    Set<Node> nodeVisited = new HashSet<>();
    nodeStack.push(node);
    while (!nodeStack.isEmpty()) {
        var current = nodeStack.pop();
        if (nodeVisited.contains(current)) continue;
        System.out.println(current);
        nodeVisited.add(current);
        for (var nei : adjacencyList.get(current)) {
            if (!nodeVisited.contains(nei)) nodeStack.push(nei);
        }
    }
}

Breadth-first Traversal

Main idea: visit a node and all its neighbors before going to the next node.

Implementation (Iteration)

public void travarseBFTIter(String root) {
    var node = nodes.get(root);
    if (node == null) return;
    Queue<Node> nodeQueue = new ArrayDeque<>();
    Set<Node> nodeVisited = new HashSet<>();
    nodeQueue.add(node);
    while (!nodeQueue.isEmpty()) {
        var current = nodeQueue.remove();
        if (nodeVisited.contains(current)) continue;
        System.out.println(current);
        nodeVisited.add(current);
        
        for (var nei : adjacencyList.get(current)) {
            if (!nodeVisited.contains(nei)) nodeQueue.add(nei);
        }
    }
}

Topology Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Regarding the DAG below, let’s image each node as a process of a project. We need to complete each process in order. The result of topology sorting is not unique, we might get 1–2–3–4–5, or 1–3–2–5–4, etc.

Directed Acyclic Graph

First, we need to find the deepest node (4, 5, or 3) and add it into a stack, which does not have any edges. How to find the deepest node? DFT! After that, go to the previous node, if the node does not have an edge, add it into the stack; otherwise, go to the node that our current node connects to. Finally, we just need to pop all of the items in the stack.

public List<String> topologySort() {
    Stack<Node> nodeStack = new Stack<>();
    Set<Node> nodeSet = new HashSet<>();
    for (var node : nodes.values()) {
        topologySort(node, nodeStack, nodeSet);
    }
    List<String> sorted = new ArrayList<>();
    while (!nodeStack.isEmpty()) {
        sorted.add(nodeStack.pop().label);
    }
    return sorted;
}

private void topologySort(Node node, Stack<Node> nodeStack, Set<Node> visitedNodes) {
    if (visitedNodes.contains(node)) return;

    visitedNodes.add(node);

    for (var nei : adjacencyList.get(node)) {
        topologySort(nei, nodeStack, visitedNodes);
    }

    nodeStack.push(node);
}

hint: when our node is already in the bottom of the hierarchy, our program will skip the loop below and add this node to our stack.

for (var nei : adjacencyList.get(node)) {
        topologySort(nei, nodeStack, visitedNodes);
    }

Cycle Detection

To detect a cycle in a directed graph, we need three sets of nodes — all, visiting, and visited.

All: all the nodes in our graph.

Visited: we have already visited a node and all of its children.

Visiting: we haven’t visited all of the children of a node.

We start by adding all nodes in the “all” set. Then pick a node from this set and start DFT. So we remove it from the “all” set and put it into the “visiting” set.

Then we visit the children of A, which are B and C. Let’s go with B first. We should remove B from the “all” set and put it into the “visiting” set.

The children of B is C, but C does not have any children. So we can put C in the “visited” set. After that, we have visited all of the children of B. Therefore, we can put B in the “visited” set.

It is worth noting that when we visit the children of A, we select to go with B. Now after we visited B and children of B. We need to go with C. However, C has already in the “visited” set. Therefore, we can put A in the “visited” set.

Finally, we can directly put D in the visited set because children of D have already been visited.

All of the nodes are in the “visited” set, so there is no cycle in our graph.

What if we change the direction of the edge between A and C?

After repeating some above steps, we are looking for the children of C. Here is the interesting part, because the children of C, which is A, is in our “visiting” set. Therefore, there must be an edge from a child node to its parent node, which means this graph contains a cycle.

In order to tell where the cycle is, we need a HashMap to store each parent-children pair.

public boolean hasCycle() {
    Set<Node> all = new HashSet<>();
    all.addAll(nodes.values());
    Set<Node> visiting = new HashSet<>();
    Set<Node> visited = new HashSet<>();

    while (!all.isEmpty()) {
        // pick the first node in all set
        var current = all.iterator().next();
        if (hasCycle(current, all, visiting,visited)) return true;
    }
    
    return false;
}

private boolean hasCycle(Node node, Set<Node> all,Set<Node> visiting, Set<Node> visited){
    all.remove(node);
    visiting.add(node);

    for (var nei : adjacencyList.get(node)) {
        if (visited.contains(nei)) continue;
        if (visiting.contains(nei)) return true;
        // if this child node have a cycle, return true. 
        if (hasCycle(nei,all,visiting,visited)) return true;
    }
    visiting.remove(node);
    visited.add(node);
    return false;
}

You can find all of the code below. Thanks for your reading.

PREVIOUS: Graph Algorithms — Part 1

NEXT: Graph Algorithms — Part 3