wordpress改地址,泉州seo网站推广,京东seo搜索优化,建设网站用什么语言比较好有向图的拓扑排序
拓扑排序介绍
什么是拓扑排序#xff1f;
一个有向图的拓扑排序#xff08;Topological sort 或 Topological ordering#xff09;是根据其有向边从顶点U到顶点V对其所有顶点的一个线性排序举个例子#xff1a;让一个拓扑排序的图中的所有顶点代表某项…有向图的拓扑排序
拓扑排序介绍
什么是拓扑排序
一个有向图的拓扑排序Topological sort 或 Topological ordering是根据其有向边从顶点U到顶点V对其所有顶点的一个线性排序举个例子让一个拓扑排序的图中的所有顶点代表某项要执行的任务组合那么它的边就可以代表要执行要执行其中某一项任务必须要先先于另外一项任务的限制条件在这个例子中拓扑排序就是这项任务组合的有效排序
有向图中的环
知道了拓扑排序可以用来解决优先级问题后还要确保要解决排序问题的图中没有环
如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了, 我们就没有办法学习了,因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环:
如何检测有向图中的环
借助一个列表ontrack其索引代表图中的顶点
在如果当前顶点正在搜索,则把对应的ontrack数组中的值改为True;如果当前顶点搜索完毕,则把对应的ontrack数组中的值改为False;如果即将要搜索某个顶点,但该顶点在当前搜索时标识为True,则图中有环;
基于DFS使用Python代码实现拓扑排序
检测图中的环
检测的目标对应的实现了这张图的类方法点击回到上一节查看代码
主要属性和方法
构造方法__init__()中 graph为需要进行拓扑排序的图marked标记当前节点是否已经搜索完毕has_cycle用于标记当前图中是否存在环ontrack标记当次所处搜索中顶点是否已经遍历过dfs() 使用DFS算法对图进行遍历判断图中是否存在环
Python代码实现
class DirectedCycle:def __init__(self, graph):self.graph graphself.marked [False for _ in range(self.graph.num_vertices)]self.has_cycle Falseself.ontrack [False for _ in range(self.graph.num_vertices)]def dfs(self):We need to search every vertex of this graphdef dfs(index):self.marked[index] Trueself.ontrack[index] Truefor vertex in self.graph.adj_list[index]:if not self.ontrack[vertex]:dfs(vertex)if self.ontrack[vertex]:self.has_cycle Truereturnself.ontrack[index] Falsefor i in range(self.graph.num_vertices):if not self.marked[i]:dfs(i)if __name__ __main__:graph Digraph(5)graph.point_edge(3, 0)graph.point_edge(0, 2)graph.point_edge(2, 1)graph.point_edge(1, 0)graph.point_edge(1, 4)DC DirectedCycle(graph)print(DC.has_cycle)DC.dfs()print(DC.has_cycle)运行结果
False
True使用DFS实现图中顶点的拓扑排序
主要属性方法设计
相比于之前的图新增了一个stackstack是一个列表看做栈按顺序记录拓扑排序所走过的顶点dfs() 使用DFS算法对顶点进行拓扑排序并将结果储存到stack列表中sort_vertices() 返回排序后的顶点
排序步骤 点击查看图对应的类方法
Python代码实现
class DepthFirstOrder:def __init__(self, graph):self.graph graphself.marked [False for _ in range(self.graph.num_vertices)]self.stack []def dfs(self):Search each vertex and rank its orderdef dfs(index):self.marked[index] Truefor x in self.graph.adj_list[index]:if not self.marked[x]:dfs(x)self.stack.insert(0, index)for i in range(self.graph.num_vertices):# for i in [5, 4, 3, 2, 1, 0]:if not self.marked[i]:dfs(i)return self.stackdef sort_vertices(self):return self.dfs()if __name__ __main__:graph Digraph(6)# graph.point_edge(0, 3)graph.point_edge(0, 2)graph.point_edge(0, 3)graph.point_edge(2, 4)graph.point_edge(3, 4)graph.point_edge(4, 5)graph.point_edge(1, 3)print(graph.adj_list)DF DepthFirstOrder(graph)print(DF.sort_vertices())运行结果
[[2, 3], [3], [4], [4], [5], []]
[1, 0, 3, 2, 4, 5]排序结果会受到对顶点遍历的顺序影响但是最终结果一定会是一条有效的符合逻辑的排序
检测一张图是否有环并进行拓扑排序
调用前面所实现的方法即可点击查看代码中使用到的图对应的类方法
from Structure.graph.digraph import Digraph
from Structure.graph.DepthFirstOrder import DepthFirstOrder
from Structure.graph.DirectedCycle import DirectedCycleclass TopoLogical:def __init__(self, graph):self.order Noneself.cycle DirectedCycle(graph)if not self.cycle.has_cycle:DFO DepthFirstOrder(graph)self.order DFO.sort_vertices()def has_cycle(self):# return self.cycle.has_cyclereturn not self.orderdef stack(self):return self.orderif __name__ __main__:graph Digraph(6)graph.point_edge(0, 2)graph.point_edge(0, 3)graph.point_edge(2, 4)graph.point_edge(3, 4)graph.point_edge(4, 5)graph.point_edge(1, 3)print(graph.adj_list)TL TopoLogical(graph)print(TL.has_cycle())print(TL.stack())运行结果
[[2, 3], [3], [4], [4], [5], []]
False
[1, 0, 3, 2, 4, 5]
