我可以使用DFS算法确定有向图的拓扑排序。如果没有循环,则我认为找到的拓扑顺序是有效的。如果有一个循环,我认为拓扑顺序是无用的。到目前为止,我是否正确?
那么无向图呢? “拓扑结构的无向图”是有效的陈述吗?该图是否应该针对拓扑排序必须是有向无环图?
最佳答案
很难确定无向图的拓扑顺序的含义或外观。有向图的拓扑顺序是这样的:对于图中的每个边(u,v),u出现在v之前的顺序中。如果您有向图,则边(u,v)和(v,u)彼此不同,并且边缘具有清晰的起点和终点。
但是,在无向图中,边没有起点和终点-节点彼此相邻或彼此不相邻。那么,拓扑顺序是什么样的?给定一条边{u,v} = {v,u},哪个节点在排序中必须排在第一位是模棱两可的,因为两个节点都不占据另一个节点的特权位置。
关于graph - 使用DFS算法对有向图和无向图进行拓扑排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51461057/