在所有边都在错误方向上的图上，反转拓扑排序的结果是否会产生有效的拓扑顺序，就像边在排序之前被反转一样？a -> cc -> d
可以给出a b c d的拓扑结构。在拓扑排序之前反转图形中的所有边也可以得到d c b a。这在一般情况下是真的吗？我猜没有，但我找不到一个失败的
浏览 25提问于2019-07-22得票数 0
回答已采纳
在有向图中，若要找到强连通分量(用Kosaraju算法)，如果我们可以利用节点的反向列表完成时间，然后遍历原始图，为什么要转换邻接矩阵(反转所有边的方向)。换句话说，我们会找到所有顶点的完成时间，并开始从最低完成时间遍历到最大完成时间(通过增加完成时间)？另外，如果我们在某些DAG上进行拓扑排序，然后反向边(转置邻接矩阵)，然后再进行拓扑排序--我们是否应该得到相等的数组，而不是相
浏览 2提问于2014-01-11得票数 1
回答已采纳
1回答
或者给我一个如何解决这个问题的提示？
我们考虑给定城市的街道网络。证明了如果我们最多可以通过创建p阻塞来消除这个网络中的所有循环(阻塞意味着阻塞一条街道的一条路)，那么我们就可以通过倒转最多一条p街的方式来消除城市网络中的所有循环。(改变一条给定的两条路的一条路意味着把它变成一条单向的街道；倒转一条单向的街道意味着把它变成另一条单行道。)
浏览 0提问于2018-11-03得票数 2
回答已采纳
1回答
我最近经历了CRLS的拓扑排序和DFS。他们有一个进入/退出时间的概念，通过这个概念，我们可以将图的边分类为因此，问题是-使用DFS的拓扑排序是否尝试从树中删除前向边缘，只保留树的边缘以得到排序的结果？
浏览 5提问于2021-10-22得票数 0
公式是一个数学表达式，用于计算字段的值，其中输入是集合中由其名称表示的其他字段。我给出的收藏品看起来可能是这样的：
名称："D"；公式：是否有标准的算法或数据结构来确定a)应该计算哪些字段值，以及在任何给定
浏览 3提问于2013-12-06得票数 2
回答已采纳
2回答
如何确定图是否具有非唯一拓扑排序
、、、、
我创建了一个程序，通过拓扑排序来组织一个图，给出一个图表。我确定了三个结果：
前两点的输出是正确的，而第三点则不是。例如，对于具有4个顶点和边的图: 1->2；3->1；3->4；4->2。不对!所知的不足以得出这一结论。如有任何提示或帮助，我们将不胜感激，谢谢。
浏览 2提问于2017-03-16得票数 2
回答已采纳
2回答
我有以下用于拓扑排序的伪代码Find a vertex with no successorPut It at beginning of listUntil graph is empty
我的问题是，它是否应该修改为“找到一个没有前导的顶点”？
浏览 0提问于2013-01-15得票数 1
回答已采纳
这是我的理解-我们可以找到一个Hamilton路径，通过拓扑排序一个DAG和检查是否存在一个边之间的每个顶点之间的排序顺序。在某种程度上，这表明这个拓扑秩序是唯一可以存在的。如何证明在拓扑顺序中的每个顶点之间有一个边，这可能是唯一的拓扑顺序？
浏览 11提问于2022-03-10得票数 0
回答已采纳
1回答
这是维基百科的解释：
这是前向数据流问题的典型迭代顺序。在反向后序迭代中，节点在任何后续节点被访问之前都会被访问，除非后继节点是通过后边缘到达的。(请注意，这与预设顺序不一样。)
浏览 2提问于2016-03-21得票数 22
回答已采纳
2回答
BFS与拓扑排序的关系
、、、、
拓扑排序既可以使用DFS(边反转)，也可以使用队列。BFS也可以使用队列来完成。在BFS中使用队列时存储和检索元素的方式与使用队列进行拓扑排序时的方式之间是否有任何关系？澄清是有帮助的。谢谢。
浏览 4提问于2012-09-11得票数 7
1回答
我试图设计一个在O(n+m)时间内运行的算法，以确定一个哈密顿路径是否存在于给定的有向无圈图中。执行DAG的拓扑排序，然后检查排序中的连续顶点是否在图中连接。如果是这样，拓扑排序给出了哈密顿路径。另一方面，如果有哈密顿路径，则路径给出了DAG的拓扑类型。
现在我不知道如何证明它的正确性，并找出它
浏览 2提问于2018-12-12得票数 0
1回答
“按照增加的预数排列DAG的顶点，结果是拓扑排序。”显然不是真实的陈述，但我不明白为什么不是。如果图是有向的并且没有圈，那么我们访问顶点的顺序不应该是拓扑排序的正确顺序吗？
浏览 3提问于2017-02-22得票数 1
回答已采纳
2回答
确实需要一些指导:拓扑按弧线定义排序(来自我的问题)-是一种对有向图中所有弧线进行排序的方法，因此插入到顶点的所有弧线必须出现在从这个顶点出来的弧线之前。
浏览 1提问于2012-03-26得票数 1
回答已采纳
1回答
我正在用SCCs解决一个双可满足性问题，并且有一个关于拓扑排序的问题。我所依据的算法是以反向拓扑顺序处理SCC，当它们都连接在一起时，这是很好的。我的算法在这种情况下破译：-2 3-2 -1在这个图中有两个源和两个接收器，根据起点有多个拓扑排序，因此有两个可能的最终节点。从源到接收器有多条路径，所以当我反向拓扑<
浏览 4提问于2017-04-02得票数 1
拓扑排序与DFS的区别仅仅在于，
public void depthfirstsearchrecursive() for(int i = 0;i<vertices.size();i++)这是我的拓扑</em
浏览 1提问于2016-11-09得票数 2
回答已采纳
对于无向图，如果我们需要找到一个圈，我们使用深度优先搜索，如所述，这是一种众所周知的方法，也是最优的。有没有人能想出一些有向图的例子，其中DFS找不到圈，但拓扑排序找到了？
浏览 3提问于2013-05-28得票数 6
回答已采纳
我有一个DAG来存储应用程序中某些对象之间的关系。当通过在现有顶点下面添加一个新顶点(即在新顶点中隐式创建新边)，然后(在以后的任何时候)从新顶点到其他顶点更新该结构时，我希望确保该图保持DAG，也就是说，我的代码不会创建循环。我是否必须在每个插入和连接操作中添加一个，或者在插入时是否有可以保证我不会产生循环的规则？
我可以想到的一种方法是存储每个节点的，并且只允许指向更高级别的新边缘(离源节点更远)。然而，这似乎实际上将剥夺我希望通
浏览 7提问于2009-04-06得票数 15
回答已采纳
我有一种直觉，原始图的拓扑排序与转置图的dfs相同(反转所有边) D -> B如果我转置图形(反转所有的边)
C -> B -
浏览 2提问于2020-04-25得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
