2

In Kosaraju algorithm I came across two possible implementations:

1) Search for strongly connected components in the reversed graph in the topological order of vertices in the original graph.

2) Search for strongly connected components in the original graph in the topological order of vertices in the reversed graph.

I wanted to that is it wrong to search for strongly connected components in the original graph using vertices in its reversed topological order. This will be better in terms of memory also as there is no need for a new adjacency list.

sources :1) E-Maxx , 2) CLRS book

4

2 回答 2

1

Terminology issues:

You are talking about topological ordering, but topological order exist if and only if the graph is DAG (directed acyclic). In case you want to work only with DAGs then you already have SCC (strongly connected components) as each vertex is component for itself. If you want to find SCC on directed graphs then you need to change topological ordering to DFS finishing times. CLRS book mentions only finishing times f[u]:

  1. Call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing f[u]...

Reformulation of your question:

Is it wrong to search for strongly connected components in the original graph consider vertices in order of increasing finishing times f[u]?

Answer:

Yes, it is wrong.

Counterexample: Consider the following graph:

enter image description here

which contains two components C and C'. If you run first DFS (starting from the node u) you will end up with one of the two following lists in ascending order by finishing time:

DFS list 1: {v,w',w,u}

DFS list 2: {w',v,w,u}

What you actually ask is whether you can process these lists from the beginning on the original graph. If you choose the first list you will extract component C' via DFS search starting from node v, and then component C via DFS search starting from node w'. But if you choose the second list and start DFS from node w' on original graph you will get only one component (whole graph), which is wrong.

Note that Kosaraju's algorithm works in both cases, as it starts from the end of a list (node u in both cases) and extract component C via DFS search on reversed graph. Component C' will be extracted later when we reach node v in the list.

于 2018-12-24T18:03:28.443 回答
1

Kosaraju algorithm is a linear time algorithm to find a strongly connected component that will work for both directed and undirected graphs. To make it easier we can say in a graph if any group of nodes makes a cycle is a Strongly connected component(SCC). If we talk about the Brute force approach to solve this problem, we can follow the steps:

  1. Find all the pairs shortest path using Floyd Warshall Algorithm.
  2. Check if between any two pairs the distance is infinity i.e. unreachable then it is not SCC else it is SCC.

If we talk about the complexity for this approach it will take cubic time i.e. O(v^3). So, we can optimize this approach using the Kosaraju algorithm that can run our algorithm in O(n+m) time. Steps to solve the problem of Strongly Connected Components using Kosaraju algorithm are:

  1. Perform Depth First Search (DFS) on graph and push nodes to the stack.
  2. Find the transpose of graph by reversing edges of the graph.
  3. Pop the nodes one by one from the stack and again do DFS on modified graph.

Each successful DFS will five 1-SCC Strongly connected component.This is how Kosaraju algorithm works in O(n+m) time where n is number of nodes in a graph and m is number of edges.

于 2021-04-10T05:05:09.493 回答