DAG的偏序应该与从任何给定根可达的任何子图的最大距离总序兼容，对吗？那么一个稳定的排序能保持拓扑顺序吗？或者，有没有一个好的算法，在拓扑排序的同时，也考虑到子图上的任何总顺序，它是<e
浏览 55提问于2020-09-07得票数 0
问题:给定一个加权有向无圈图(DAG)和其中的一个源顶点，求出从s到给定图中所有其他顶点的最长距离。为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们这么关心线性排序。谢谢
浏览 3提问于2014-12-23得票数 12
回答已采纳
1回答
如果有一组节点N和一组顶点V_1定义具有一定拓扑顺序的图G_1，那么如何检查来自N的节点子集和定义图G_2的新顶点V_2是否保持G_1的拓扑顺序？例如：B -> CG_1：[A, B, C, D, E]的拓扑序B
浏览 1提问于2018-07-27得票数 1
回答已采纳
2回答
我可以用DFS算法确定有向图的拓扑排序。如果没有圈，我假设我找到的拓扑顺序是有效的。如果有一个循环，我假设拓扑顺序是无用的。到目前为止我是对的吗？
那么无向图呢？“拓扑类无向图”是有效的语句吗？为了拓扑排序</em
浏览 2提问于2018-07-22得票数 9
回答已采纳
1回答
我需要找出N阶有向无环图的拓扑排序的最大数目。我已经通过在各种有向无环图上运行深度优先搜索算法进行了检查，它看起来是在对图运行DFS后创建的深度优先搜索算法森林的大小。也许我完全错了或者漏掉了什么。
浏览 0提问于2013-05-20得票数 3
回答已采纳
1回答
如何使用深度优先搜索功能(dfs)生成拓扑排序？这是我的代码： def __init__(self,key): self.connectedTo = {}
浏览 0提问于2014-12-08得票数 1
有向图G= (V，E)中的母点是一个顶点v，使得从v到G的一条有向路可以到达所有其它顶点。给出了一个O(n+m)算法来检验图G是否包含母点。仅找到O(n(n+m))方式
浏览 0提问于2010-11-30得票数 7
目标是对n个未知变量{x0，x1，x2，.x(n-1)}使用m比较结果的列表C(布尔值)。每个比较是在两个n个变量之间进行的，例如x2 < x5，每个比较的对指数都是固定的，并且提前给定。还给出了:C中的所有对都是唯一的(即使翻转时也是如此，例如，对x0，x1表示没有对x1，x0)，而且永远不要将变量与自身进行比较。这意味着C最多有n*(n-1)/2条目。所以问题是，我能证明我的m比较列表C足以对列表X排序吗？显然，如果</em
浏览 2提问于2015-08-11得票数 4
3回答
我从mygraph中得到了一个顶点向量，并对这些顶点进行了拓扑排序。//and then i use
boost::topological_sort(mygraph,std::back_inserter(v2));
按拓扑顺序对顶点进行排序那么，比较v1和v2以测试我的原始顶点向量(V1)是“有序”还是“无序”的最佳方法是什么呢？编辑:例如
浏览 1提问于2011-07-13得票数 1
回答已采纳
1回答
我正在寻找一个数据结构的Java实现，该数据结构包含定义了偏序的元素集合，并且允许以某种拓扑顺序迭代这些元素(任何可能的顺序都可以；最好是随着集合内容的变化而具有稳定的排序)。在指定总排序方面，可以使用Comparator<E>实例化集合，比较器可以抛出异常(ClassCastException?)如果两个被比较的元素没有相对于彼此<
浏览 3提问于2012-09-11得票数 14
回答已采纳
1回答
我试图设计一个在O(n+m)时间内运行的算法，以确定一个哈密顿路径是否存在于给定的有向无圈图中。执行DAG的拓扑排序，然后检查排序中的连续顶点是否在图中连接。如果是这样，拓扑排序给出了哈密顿路径。另一方面，如果有哈密顿路径，则路径给出了DAG
浏览 2提问于2018-12-12得票数 0
4回答
大型DAGs拓扑排序的实例
、、、、
我正在寻找现实世界的应用程序，其中拓扑排序是在大图大小上执行的。有些领域，你可以找到这样的例子，生物信息学，依赖性解决，数据库，硬件设计，数据仓库.但我希望你们中的一些人可能遇到或听说过任何需要topsort的具体算法/项目/应用程序/数据集。即使数据/项目可能无法公开访问，任何提示(以及对潜在图形大小的大小的估计)也可能有帮助。
浏览 4提问于2011-08-31得票数 12
回答已采纳
在有向图中，若要找到强连通分量(用Kosaraju算法)，如果我们可以利用节点的反向列表完成时间，然后遍历原始图，为什么要转换邻接矩阵(反转所有边的方向)。换句话说，我们会找到所有顶点的完成时间，并开始从最低完成时间遍历到最大完成时间(通过增加完成时间)？另外，如果我们在某些DAG上进行拓扑排序，然后反向边(转置邻接矩阵)，然后再进行拓扑排序--我们是否<
浏览 2提问于2014-01-11得票数 1
回答已采纳
1回答
给出了一个有向图G= (V，E)，它具有正边权和负边权，但没有圈。设s∈V是给定的源顶点。如何找到一种算法，找到所有顶点的距离，肯定比Bellman Ford的O(VE)时间复杂度更快。
浏览 4提问于2022-01-17得票数 0
回答已采纳
我试图编写用于检测有向图中的循环的代码，如果没有循环，则返回相同的拓扑顺序。这两者有什么区别吗？
浏览 1提问于2019-10-15得票数 10
回答已采纳
2回答
有向图是否有唯一拓扑序的算法。初始化列表L
如果图中还有点，请转到第2步。最后给出了L中顶点的拓扑序，如果在第2步中可以从多个顶点中选择，那么这个拓扑序就不是唯一
浏览 1提问于2015-04-09得票数 2
回答已采纳
3回答
一个有向图G= (V，E)称为半连通的，如果对V中的所有顶点对u，v都有u- -> v或v-> u路。给出了判定G是否半连通的一个有效算法
浏览 0提问于2015-06-04得票数 13
回答已采纳
2回答
给定有向图G=(V，E)，如何检查它是否是单向连通的，即对于任意两个顶点a和b，至少满足下列条件之一：
从b到a有一条路。
浏览 2提问于2020-10-13得票数 2
回答已采纳
1回答
我有以下算法:我有一个图和一个相关的拓扑排序(在图论中，“有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点u到顶点v的每条有向边uv，在排序中u在v之前。")给定一个start_position和<e
浏览 12提问于2020-08-29得票数 0
2回答
我正在寻找一种在给定的包含圈的有向未加权图上执行拓扑排序的方法。结果不仅应该包含顶点的排序，还应该包含被给定排序违反的边集。这组边应该是最小的。
因为我的输入图可能很大，所以我不能使用指数时间算法。如果不可能在多项式时间内计算出最优解，那么对于给定的问题，什么启发式方法是合理的？
浏览 4提问于2013-06-17得票数 21
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
