1回答
考虑一个任意有向图G (可以包含自循环)和A它各自的邻接矩阵。是否有一种方法(一种算法)来计算图G在一个O(n^4)时间内传递自反闭包的邻接矩阵？有办法在O(log(n)n^3)中计算它吗？传递自反闭包定义如下：
Gt(V，E)是G：(u，v)的传递自反闭包，仅当u=v或者是G中从u到v<e
浏览 3提问于2019-12-16得票数 2
我正在尝试实现Warshall的算法，以快速计算LR(1)闭包。我想我理解LR(0)的工作原理：
在我看来，即使我知道任何给定LR项的传递闭包，我仍然需要进行所
浏览 2提问于2013-06-08得票数 7
回答已采纳
1回答
我有一个有向图但是我不知道里面有多少元素。它可以用不同的词来表达。例如，它们可以以a-b、b-c、c-d、……的方式连接。我想添加到这个图传递闭包，它将创建a-c，a-d等之间的连接。
对于任何给定的图，我应该在算法中进行哪些更改才能达到传递闭包。现在，它只适用于包含3
浏览 0提问于2015-11-13得票数 1
1回答
我正在尝试计算一个图的传递闭包。让我们以这个图为例(该图描述了该图及其邻接和连接矩阵)：
使用我在页面上找到的沃肖尔算法，我生成了这个连通性矩阵(=传递闭包？)，这与图片中的不同： 01111 01111我也尝试过使用 applet，它也给了我一个不同的结果：01111
0111
浏览 3提问于2012-11-18得票数 2
回答已采纳
1回答
在最近的算法过程中，我们必须形成一个凝聚图并计算它的自反传递闭包来得到一个偏序。但从来没有真正解释过为什么我们会想要在一个图表中这样做。我理解凝聚图的要点，因为它突出了强连通的成分，但是偏序给我们的是什么，而原始图却没有呢？实现的算法如下：
邻接矩阵
浏览 3提问于2017-07-14得票数 2
华尔计算有向图传递闭包的算法通常采用以下形式(来自)： //ImplementsWarshall’s algorithm fori, j ] or (R(k−1)[i, k] and R(k−1)[k, j])但是我们可以加快上面的实现，方法是注意到没有任何更新，如果在这种情况下，我们可以跳过运行更新这种改进不影响运行时吗？
浏览 0提问于2019-06-01得票数 1
回答已采纳
2回答
图的传递闭包的定义如下：
这在O(n^3)中很容易实现，其中n是顶点的数量。我想知道是否可以在O(n^2)时间内完成。
浏览 0提问于2009-03-31得票数 7
回答已采纳
1回答
我有一个很大的有向图，G和顶点子集S，在G中，我想要做的是找到由S诱导的G的子图，附加的考虑是，如果在G中的顶点p和顶点q之间存在一些路径，那么在诱导子图中这两个顶点之间就存在边。这是关键，它比通常的诱导子图问题要复杂一些(我认为)。如果存在这种路径，在诱导子图中插入p和q之间的边。就我的目的而言，n^2时间没那么糟糕。
因此，我想我有两个问题: 1)确定两个顶点
浏览 1提问于2011-06-03得票数 1
我需要以点格式处理有向图，并得到子图的传递闭包(实际上是一个节点)。例如，给出 E -> B; C -> D; A -> B; C -> D;
我知道这在python和许多其他语言中是可能的有什么简单<em
浏览 2提问于2013-09-09得票数 3
回答已采纳
在对各种图形算法的讨论中，我看到了术语“路径矩阵”和“传递闭包”，它们在任何地方都没有很好的定义。
在有向图和无向图的情况下，“路径矩阵”和“传递闭包”是什么意思？
浏览 0提问于2011-07-20得票数 10
回答已采纳
1回答
我努力寻找如何用networkx计算有向图的传递闭包，却出人意料地一无所获。这似乎不太可能不在networkx中，所以...它在哪里?(我知道Sage包含此功能。)
浏览 1提问于2014-10-23得票数 1
1回答
有效地找到所有连通导出子图
、、、、
是否有一个有效的(*)算法来寻找一个连通的无向顶点标号图的所有连通(诱导)子图？(*)我理解，在一般情况下，任何这样的算法都可能有O( 2^n )的复杂度，因为对于一个团(Kn)，有2^n个连通子图。但是，我通常处理的图的连通子图要少得多，所以我正在寻找一种方法来生成它们，而不必考虑所有2^n个子图并丢弃那些不连通的子图(就像在
浏览 3提问于2013-03-27得票数 12
回答已采纳
1回答
枚举等价类
、、
,n}上的等价关系，作为等效对(a,b)的完整列表给出(这已经是传递性的，不需要计算传递闭包)。n是大的(例如，最多几百万)；等效对的总数最多是O(n) (而且通常要少得多)，而且单个等效类是小的(我没有这方面的数字，但比方说O(log n))。我想要的是:一种单独枚举所有等效类的方法，即依次获得每个等效类的完整元素集；复杂度最
浏览 4提问于2021-03-26得票数 1
1回答
我正在从现有的边制作一个无向图。这个闭包是由级别k参数化的，这样k=1就意味着将添加新的边。，图G最终会变成一个团(即传递闭包)。但是，我希望在特定的k级别上得到一个传递的闭包。我可以使用获得完整的传递闭包。但我正在为特定层面的过渡性封闭而奋斗。我能够通过使用k=1表示来实现
浏览 0提问于2019-04-06得票数 0
回答已采纳
2回答
设G是由邻接矩阵给出的n个顶点和m条边的DAG。我还需要以矩阵的形式计算它的闭包。我们有一台计算机，每个字都是b位。我需要在(n^2+nm/b)中找到一个计算传递闭包的算法增加了寻找dag传递闭包</e
浏览 4提问于2013-01-03得票数 3
2回答
我有一个有向无圈图，其中每个节点代表一个任务，每个有向边A -> B意味着task A应该在 task B启动之前完成
所以这实际上是一个工作流。在这个图中，边A -> B被认为是多余的，因为任务B需要先完成任务C，任务C需要先完成任务A。(更不用说另一条路径A -> D -> E -> B，它使A -> B变得不必要)
问题是:我想识别(比方说，只是输出)图上的所有冗余依赖(边)。我的朋友和我有这样的</
浏览 3提问于2017-07-18得票数 2
回答已采纳
4回答
我正在尝试根据附加到顶点的一些参数来压缩它。你知道如何从原始图中有效地找到子集顶点的边吗？{9: 10，7: 9，8: 9，6: 7，3: 8，2: 3，4，5: 4，6，4: 7，1: 2}如何查找子集的连接？请将传递闭包视为一个问题。我需要找到<
浏览 0提问于2011-04-22得票数 0
1回答
DAG中的最小路径覆盖
、、、
我想知道是否存在一个有效的算法来计算有向无环图的最小路径覆盖。请不要将最小“路径覆盖”与“顶点不相交的路径覆盖”混淆。对于后者，我知道一个有效的算法，使用相应的二部图的最大匹配。但这只适用于顶点不相交的情况。当每个顶点可以被多次访问时，是否可以放松相同的算法以获得路径覆盖的答案？
浏览 4提问于2013-06-10得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
