Recap on BFS, DFS and Strongly Connected Components

graph

DFS

topological sort

considering the dependencies between tasks, we can use topological sort to find the order of tasks.

def topological_sort(graph):
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited, stack)
    return stack[::-1]

def dfs(graph, node, visited, stack):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, stack)
    stack.append(node)

if A -> B then B.finishtime < A.finishtime, that's why we need to reverse the stack.

Topological Sorting on a DAG

• do DFS on the graph
• when a node is finished, insert it into the front of a linked list

Another use of DFS is in-order traversal of a binary tree .

BFS

BFS is used to find the shortest path in an unweighted graph.

we can find the shortest path between u and v in time O(m), where m is the number of edges.

Another application of BFS: testing bipartiteness of a graph.

• color the levels of the BFS tree in alternating colors

• if there is an edge between two nodes of the same color, then the graph is not bipartite

• if there is no such edge, then the graph is bipartite

If BFS colors two neighbors of a node with the same color, then it's found an cycle of odd length.

Finding Strongly Connected Components

when using you cannot reach everything using DFS, run DFS repeatedly to get a depth-first forest.

if v is a descendent of w in the same tree:

• w.start < v.start < v.finish < w.finish

if neither v nor w is a descendent of the other:

• v.start < w.start < w.finish < v.finish

or the other way around.

A directed graph $G = (V,E)$ is strongly connected if:

for all v, w in V:

- there is a path from v to w

- there is a path from w to v

We can decompose a graph into strongly connected components (SCCs).

Definition by definition: The SCCs are the equivalence classes under the "are mutually reachable" equivalence relation.

Why do we care about SCCs?

• SCCs are the "building blocks" of a directed graph

• SCCs are the "maximal" subgraphs that are "mutually reachable"

• Strongly connected components tell you about communities.

• Lots of graph algorithms only work on SCCs.

Kosaraju's Algorithm

• run DFS on $G$, keeping track of the finish times

• run DFS on $G^T$, in the order of decreasing finish times

• each tree in the second DFS is a SCC

properties of SCCs

• The SCCs of a graph form a DAG

  • if not, then there is a cycle in the graph, and two nodes in the cycle are mutually reachable

Starting and finishing times in a SCC

• The finishing time of a SCC is the largest finishing time of any element of that SCC.

• The starting time of a SCC is the smallest starting time of any element of that SCC.

Finishing times allowed us to topologically sort of the vertices, it works out for SCCs as well.

For SCCs A and B if we have A -> B, then we have B.finishtime < A.finishtime.

if there is an edge A <- B in the reversed graph, then B.finishtime < A.finishtime.

C++ inplementation of Kosaraju's Algorithm (copilot auto generated):

#include <bits/stdc++.h>
using namespace std;

class Graph {
    int V;
    list<int> *adj;
    void fillOrder(int s, bool visited[], stack<int> &Stack);
    void DFSUtil(int s, bool visited[]);

    public:
        Graph(int V);
        void addEdge(int v, int w);
        void printSCCs();
        Graph getTranspose();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::DFSUtil(int s, bool visitedV[]{
    visited[s] = true;
    cout << s << " ";
    list<int>::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i) {
        if (!visited[*i]) {
            DFSUtil(*i, visited);
        }
    }
})

Graph Graph::getTranspose(){
    Graph g(V);
    for (int s = 0; s < V; s++) {
        list<int>::iterator i;
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            g.adj[*i].push_back(s);
        }
    }
    return g;
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::fillOrder(int s, bool visited[], stack<int> &Stack) {
    visited[s] = true;
    list<int>::iterator i;
    for (i = adj[s].begin(); i != adj[s].end(); ++i) {
        if (!visited[*i]) {
            fillOrder(*i, visited, Stack);
        }
    }
    Stack.push(s);
}

void Graph::printSCCs() {
    stack<int> Stack;
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            fillOrder(i, visited, Stack);
        }
    }
    Graph gr = getTranspose();
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    while (!Stack.empty()) {
        int s = Stack.top();
        Stack.pop();
        if (!visited[s]) {
            gr.DFSUtil(s, visited);
            cout << endl;
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);
    cout << "SCCs in the graph are: " << endl;
    g.printSCCs();
    return 0;
}