C#，寻找图强连通分量（SCC，Strongly Connected Components）的Kosaraju算法与源代码

S. Rao Kosaraju

Strongly Connected Components
In this tutorial, you will learn how strongly connected components are formed. Also, you will find working examples of Kosaraju's algorithm in C, C++, Java and Python.

A strongly connected component is the portion of a directed graph in which there is a path from each vertex to another vertex. It is applicable only on a directed graph.
 

在计算机科学中，Kosaraju的算法（也称为Kosaraju-Sharir算法）
是线性时间的算法来找到一个有向图的强连通分量。
Aho, Hopcroft 和Ullman相信这个算法是
由S. Rao Kosaraju在1978在一个未发表的论文上提出的。
相同的算法还从Micha Sharir 1981年自己出版的书上被单独的发现，
这个算法利用了一个事实，即转置图（同图中的每边的方向相反）
具有和原图完全一样的强连通分量。

无向图中的连通性意味着每个顶点都可以通过任何路径到达其他顶点。如果图形未连接，则可以将图形分解为连接的组件。

强连通性仅适用于有向图。有向图是强连通的，如果有一条从任何顶点到其他顶点的有向路径。这与无向图中的连通性相同，唯一的区别是强连通性适用于有向图，并且应该存在有向路径，而不仅仅是路径。与连通分量类似，有向图可以分解为强连通分量。

图中显示了2个强连接部件

查找强连接组件的基本/蛮力方法：

强连通分量可以逐个找到，即首先找到包含节点的强连通分量。然后，如果节点未包含在节点的强连接组件中，则可以对节点使用下面概述的类似过程，否则该过程将移动到节点，以此类推。

如果所有顶点对之间都有一条路径，则有向图是强连通的。有向图的强连通分量是最大强连通子图。

我们可以使用Kosaraju算法在O（V+E）时间内找到所有强连通分量。下面是Kosaraju的详细算法。

1） 创建空堆栈“S”，并对图进行DFS遍历。在DFS遍历中，为顶点的相邻顶点调用递归DFS后，将顶点推到堆栈。在上图中，如果我们从顶点0开始DFS，则堆栈中的顶点为1、2、4、3、0。

2） 反转所有弧的方向以获得转置图。

3） 当S不为空时，逐个从S弹出顶点。让弹出的顶点为“v”。将v作为源并执行DFS（调用DFSUtil（v））。从v开始的DFS打印v的强连接组件。在上面的示例中，我们按照0、3、4、2、1的顺序处理顶点（从堆栈中逐个弹出）。

这是如何工作的？

上述算法基于DFS。它执行DFS两次。如果从DFS起点可以到达所有顶点，则图的DFS将生成一棵树。否则DFS将生成一个林。因此，只有一个SCC的图的DFS总是生成一棵树。需要注意的重要一点是，根据选择的起点，当存在多个SCC时，DFS可能会生成树或林。例如，在上图中，如果我们从顶点0、1或2开始DFS，我们将得到一棵树作为输出。如果我们从3或4开始，我们会得到一片森林。要查找和打印所有SCC，我们需要从顶点4（这是一个汇聚顶点）开始DFS，然后移动到3（这是剩余集合中的汇聚顶点）（集合不包括4），最后是任何剩余顶点（0、1、2）。那么，我们如何找到这个拾取顶点的序列作为DFS的起点呢？不幸的是，没有直接的方法可以获得这个序列。但是，如果我们对图进行DFS并根据顶点的完成时间存储顶点，我们可以确保连接到其他SCC（其自身SCC除外）的顶点的完成时间始终大于其他SCC中顶点的完成时间（请参见此以获取证明）。例如，在上述示例图的DFS中，0的完成时间始终大于3和4（与DFS考虑的顶点序列无关）。完成时间3总是大于4。DFS不保证其他顶点，例如，根据DFS考虑的顶点序列，1和2的完成时间可能小于或大于3和4。所以，为了使用这个属性，我们对完整图进行DFS遍历，并将每个完成的顶点推到一个堆栈中。在堆栈中，3始终显示在4之后，0显示在3和4之后。

在下一步中，我们反转图形。考虑SCCs图。在反转图中，连接两个组件的边反转。因此，SCC{0，1，2}成为汇，SCC{4}成为源。如上所述，在堆栈中，3和4之前总是有0。所以，如果我们使用堆栈中的顶点序列对反转图进行DFS，我们将顶点从汇点处理到源点（在反转图中）。这就是我们想要实现的目标，也是逐个打印SCC所需的全部内容。

参考：

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711?spm=1001.2014.3001.5501

源程序（POWER BY 315SOFT.COM 多可文档管理系统）

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		private void DFS_Kosaraju_Utility(int s, bool[] visitedVertices)
		{
			visitedVertices[s] = true;
 
			Traversal.Add(s);
 
			foreach (int n in Adjacency[s])
			{
				if (!visitedVertices[n])
				{
					DFS_Kosaraju_Utility(n, visitedVertices);
				}
			}
		}
 
		public Graph Transpose()
		{
			Graph g = new Graph(Node_Number);
			for (int s = 0; s < Node_Number; s++)
			{
				foreach (int i in Adjacency[s])
				{
					g.Adjacency[i].Add(s);
				}
			}
 
			return g;
		}
 
		private void Fill_Order(int s, bool[] visitedVertices, Stack<int> stack)
		{
			visitedVertices[s] = true;
 
			foreach (int n in Adjacency[s])
			{
				if (!visitedVertices[n])
				{
					Fill_Order(n, visitedVertices, stack);
				}
			}
			stack.Push(s);
		}
 
		public void Print_Strongly_Connected_Component()
		{
			Stack<int> stack = new Stack<int>();
 
			bool[] visitedVertices = new bool[Node_Number];
			for (int i = 0; i < Node_Number; i++)
			{
				visitedVertices[i] = false;
			}
			for (int i = 0; i < Node_Number; i++)
			{
				if (visitedVertices[i] == false)
				{
					Fill_Order(i, visitedVertices, stack);
				}
			}
			Graph gr = Transpose();
 
			for (int i = 0; i < Node_Number; i++)
			{
				visitedVertices[i] = false;
			}
			while (stack.Count > 0)
			{
				int s = (int)stack.Pop();
				if (visitedVertices[s] == false)
				{
					gr.DFS_Kosaraju_Utility(s, visitedVertices);
				}
			}
		}
	}
 
	public static partial class GraphDrives
	{
		public static string SCC()
		{
			Graph g = new Graph(8);
			g.AddEdge(0, 1);
			g.AddEdge(1, 2);
			g.AddEdge(2, 3);
			g.AddEdge(2, 4);
			g.AddEdge(3, 0);
			g.AddEdge(4, 5);
			g.AddEdge(5, 6);
			g.AddEdge(6, 4);
			g.AddEdge(6, 7);
 
			g.Print_Strongly_Connected_Component();
 
			return String.Format(",", g.Traversal.ToArray());
		}
	}
}