使用C#代码实现拓扑排序MyZony

尊重他人的劳动成果，贴上参考的资料地址，本文仅作学习记录之用。

看了第二篇参考资料才大致了解，在此记录一下。

先来一个基本定义：

在图论中，拓扑排序（TopologicalSorting）是一个有向无环图（DAG,DirectedAcyclicGraph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

例如，有一个集合它的依赖关系如下图：

可以看到他有一个依赖关系:

这个就是一个DAG图，我们要得到它的拓扑排序，一个简单的步骤如下：

按照以上步骤，我们来进行一个排序试试。

最后的排序结果就是：

ModuleD->ModuleE->ModuleB->ModuleC->ModuleA

emmmm，其实一个有向无环图可以有一个或者多个拓扑序列的，因为有的时候会存在一种情况，即以下这种情况：

这个时候你就可能会有这两种结果

D->E->B->C->F->A

D->E->B->F->C->A

因为F与C是平级的，他们初始化顺序即便不同也没有什么影响，因为他们的依赖层级是一致的，不过细心的朋友可能会发现这个顺序好像是反的，我们还需要将其再反转一次。

上面这种方法仅适用于已知入度的时候，也就是说这些内容本身就是存在于一个有向无环图之中的，如果按照以上方法进行拓扑排序，你需要维护一个入度为0的队列，然后每次迭代移除入度为0顶点所指向的顶点入度。

例如有以下图：

按照我们之前的算法，

这样反复循环，最终队列全部清空，退出循环，得到拓扑排序的结果4,5,2,0,3,1。

在参考资料1的代码当中使用的是深度优先算法，它适用于有向无环图。

有以下有向环图G2：

对上图G2进行深度优先遍历，首先从入度为0的顶点A开始遍历：

它的步骤如下：

因此最后的访问顺序就是A->B->C->E->D->F->G，注意顺序还是不太对哦。

看起来跟之前的方法差不多，实现当中，其Sort()方法内部包含一个visited字典，用于标记已经访问过的顶点，sorted则是已经排序完成的集合列表。

在字典里Key是顶点的值，其value值用来标识是否已经访问完所有路径，为true则表示正在处理该顶点，为false则表示已经处理完成。

现在我们来写实现吧：

publicstaticIListSort(IEnumerablesource,Func>getDependencies){ varsorted=newList(); varvisited=newDictionary(); foreach(variteminsource) { Visit(item,getDependencies,sorted,visited); } returnsorted;}publicstaticvoidVisit(Titem,Func>getDependencies,Listsorted,Dictionaryvisited){ boolinProcess; varalreadyVisited=visited.TryGetValue(item,outinProcess);//如果已经访问该顶点，则直接返回 if(alreadyVisited) {//如果处理的为当前节点，则说明存在循环引用 if(inProcess) { thrownewArgumentException("Cyclicdependencyfound."); } } else {//正在处理当前顶点 visited[item]=true;//获得所有依赖项 vardependencies=getDependencies(item);//如果依赖项集合不为空，遍历访问其依赖节点 if(dependencies!=null) { foreach(vardependencyindependencies) {//递归遍历访问 Visit(dependency,getDependencies,sorted,visited); } }//处理完成置为false visited[item]=false; sorted.Add(item); }}顶点定义：

//Item定义publicclassItem{//条目名称 publicstringName{get;privateset;}//依赖项 publicItem[]Dependencies{get;set;} publicItem(stringname,paramsItem[]dependencies) { Name=name; Dependencies=dependencies; } publicoverridestringToString() { returnName; }}调用：

staticvoidMain(string[]args){ varmoduleA=newItem("ModuleA"); varmoduleC=newItem("ModuleC",moduleA); varmoduleB=newItem("ModuleB",moduleC); varmoduleE=newItem("ModuleE",moduleB); varmoduleD=newItem("ModuleD",moduleE); varunsorted=new[]{moduleE,moduleA,moduleD,moduleB,moduleC}; varsorted=Sort(unsorted,x=>x.Dependencies); foreach(variteminsorted) { Console.WriteLine(item.Name); } Console.ReadLine();}