Kosaraju

Questions 1 to 5 of 7

1. 1. Put the three main stages of Kosaraju's algorithm in the order they must run.

   Use the arrows to put the steps in order.

   1. 1.Walk the reversed graph from the last recorded vertex, skipping vertices already placed↑↓
   2. 2.Run a DFS on the original graph and record each vertex when it finishes↑↓
   3. 3.Build the condensed graph from the arrows that join different components↑↓
2. 2. A DFS starts at vertex 0 and follows the arrows 0 -> 1, 1 -> 2, 2 -> 0 and 2 -> 3. Put the vertices in the order they finish.

   Use the arrows to put the steps in order.

   1. 1.2↑↓
   2. 2.1↑↓
   3. 3.0↑↓
   4. 4.3↑↓
3. 3. Why does pass 2 of Kosaraju's algorithm walk the reversed graph?

   Because the reversed graph has fewer arrows, so the walks run fasterBecause the original graph can contain cycles that the walks cannot handleBecause reversing the arrows turns the condensed graph into a DAGSo that a walk from the last-finished vertex cannot leave its own component
4. 4. Why can the condensed graph of a directed graph never contain a cycle?

   Because the algorithm deletes every arrow that points backwardsBecause two boxes that reach each other would be one strongly connected componentBecause each box has at most one outgoing arrowBecause pass 1 always finishes vertices in topological order of the original graph
5. 5. What does this program print? It runs Kosaraju's two passes on a graph with four vertices and the arrows 0 -> 1, 1 -> 0, 1 -> 2, 2 -> 3 and 3 -> 2, then prints the component number of each vertex. ``cpp #include <cstddef> #include <iostream> #include <utility> #include <vector> using Vertex = std::size_t; using Graph = std::vector<std::vector<Vertex>>; Graph reversed(const Graph& g) { Graph r(g.size()); for (Vertex u = 0; u < g.size(); ++u) { for (Vertex v : g[u]) { r[v].push_back(u); } } return r; } void first_pass(const Graph& g, Vertex v, std::vector<bool>& seen, std::vector<Vertex>& finish_order) { seen[v] = true; for (Vertex next : g[v]) { if (!seen[next]) { first_pass(g, next, seen, finish_order); } } finish_order.push_back(v); } void second_pass(const Graph& r, Vertex v, std::vector<int>& component, int id) { component[v] = id; for (Vertex next : r[v]) { if (component[next] == -1) { second_pass(r, next, component, id); } } } int main() { const Vertex n = 4; const std::vector<std::pair<Vertex, Vertex>> edges = {{0, 1}, {1, 0}, {1, 2}, {2, 3}, {3, 2}}; Graph g(n); for (auto [u, v] : edges) { g[u].push_back(v); } std::vector<bool> seen(n, false); std::vector<Vertex> finish_order; for (Vertex v = 0; v < n; ++v) { if (!seen[v]) { first_pass(g, v, seen, finish_order); } } const Graph r = reversed(g); std::vector<int> component(n, -1); int count = 0; for (auto it = finish_order.rbegin(); it != finish_order.rend(); ++it) { if (component[*it] == -1) { second_pass(r, *it, component, count); ++count; } } for (Vertex v = 0; v < n; ++v) { if (v > 0) std::cout << ' '; std::cout << component[v]; } std::cout << '\n'; } ``

   1 1 0 00 1 1 00 0 0 10 0 1 1