cs126 reachability

Define reachability.

The existence of a path between two vertices.

Define strong connectivity.

Each vertex can reach all other vertices.

Describe how a DFS can be used to check if a graph is strongly connected.

1. Pick a vertex v in G

   1. Perform a DFS from v in G

   2. If there’s a node w that is not visited, then print “no”

2. Let G’ be G with edges reversed

   1. Perform a DFS from v in G’

   2. If there’s a node w that is not visited, then print “no”

   3. Else, print “yes”

What is the worst-case time cost of using a DFS to confirm strong connectivity?

O(n+m)

Define strongly connected components (SCC).

Maximal subgraphs, where each vertex can reach all other vertices.

Describe Kosoraju’s algorithm.

1. Run DFS on G and mark the finish times for all vertices

2. Compute G’ by reversing the edges of G

3. Run DFS on G’ in the order of decreasing finish times

4. Each tree from the previous step represents a SCC

What strategy does Tarjan’s algorithm employ?

It uses a stack.

Define transitive closure.

• Transitive closure of G is the digraph G^* such that:

  • G^* has the same vertices as G

  • If G has the a path from u to v, G^* has a directed edge (u,v)

• It provides reachability information about a graph

What is the cost of computing the transitive

closure of a graph using DFS?

O(n x (n+m))