对于有向图,最着名的传递闭包算法是什么？
对于有向图，最着名的传递闭包算法是Warshall算法。
Warshall算法是一种用于计算有向图的传递闭包的经典算法。传递闭包是指在有向图中，如果存在一条从顶点A到顶点B的路径，那么顶点A到顶点B之间的所有顶点也都存在路径。传递闭包算法的目标是通过计算得到一个矩阵，该矩阵表示图中所有顶点之间的传递关系。
具体来说，Warshall算法通过迭代的方式计算传递闭包。算法的基本思想是，对于图中的每一对顶点A和B，如果存在一条直接的边从A到B，或者存在一条路径从A经过其他顶点到达B，那么就将A和B之间的传递关系标记为存在。
Warshall算法的时间复杂度为O(n^3)，其中n是图中顶点的数量。该算法在计算传递闭包时非常高效，并且可以应用于各种有向图相关的问题，例如寻找图中的强连通分量、计算图的可达性等。
腾讯云提供了云计算相关的产品和服务，其中包括云服务器、云数据库、云存储、人工智能等。具体推荐的产品和产品介绍链接地址可以参考腾讯云官方网站：https://cloud.tencent.com/
相关·内容
2回答
在对各种图形算法的讨论中，我看到了术语“路径矩阵”和“传递闭包”，它们在任何地方都没有很好的定义。
在有向图和无向图的情况下，“路径矩阵”和“传递闭包”是什么意思？
浏览 0提问于2011-07-20得票数 10
回答已采纳
1回答
确定图的传递自反闭包的时间复杂性
algorithm、complexity-theory、graph-theory、transitive-closure
考虑一个任意有向图G (可以包含自循环)和A它各自的邻接矩阵。是否有一种方法(一种算法)来计算图G在一个O(n^4)时间内传递自反闭包的邻接矩阵？有办法在O(log(n)n^3)中计算它吗？传递自反闭包定义如下：
Gt(V，E)是G：(u，v)的传递自反闭包</em
浏览 3提问于2019-12-16得票数 2
1回答
在SQL中更新图形数据
sql、database、postgresql、graph、common-table-expression
但规则是，当我的公司不再在某一主题上代表你的公司时，那么从我那里下来的任何公司都不能在同一主题上代表我的公司。C1:--pay--> C3
--sell--> C3--mail--> C1
--sell-->，为一个特定的主题？我认为递归的CTE表达式是唯一的</e
浏览 1提问于2012-08-15得票数 4
回答已采纳
1回答
图及其七个闭包
code-golf、decision-problem、graph-theory
背景什么是最小有向图(有向图)G，其中下列八个图都是不同的：自反闭包G传递闭包GG的对称传递闭
浏览 0提问于2021-01-22得票数 12
1回答
求图的偏序的理由
algorithm、graph
在最近的算法过程中，我们必须形成一个凝聚图并计算它的自反传递闭包来得到一个偏序。但从来没有真正解释过为什么我们会想要在一个图表中这样做。我理解凝聚图的要点，因为它突出了强连通的成分，但是偏序给我们的是什么，而原始图却没有呢？实现的算法如下：
浏览 3提问于2017-07-14得票数 2
1回答
如何使用Warshall的传递闭包算法来确定标准LR(1)解析器闭包？
parsing、lr、floyd-warshall、transitive-closure
我正在尝试实现Warshall的算法，以快速计算LR(1)闭包。我想我理解LR(0)的工作原理：
在我看来，即使我知道任何给定LR项的传递闭包，我仍然需要进行所有相同的计算，以确
浏览 2提问于2013-06-08得票数 7
回答已采纳
1回答
诱导子图；节点间路径的存在性
algorithm、shortest-path、graph-algorithm、subgraph
我有一个很大的有向图，G和顶点子集S，在G中，我想要做的是找到由S诱导的G的子图，附加的考虑是，如果在G中的顶点p和顶点q之间存在一些路径，那么在诱导子图中这两个顶点之间就存在边。这是关键，它比通常的诱导子图问题要复杂一些(我认为)。解决这个问题的最基本的方法是：(我意识到它可能不是最有效的，如果你有<
浏览 1提问于2011-06-03得票数 1
1回答
有向图的闭包--最大闭包问题
algorithm、data-structures、graph、graph-theory
我正在阅读这篇维基文章：和我有几个问题。
首先，本文指出“有向图的闭包是一组顶点C，因此没有边离开C”。假设我有一个图G=(V，E)，其中V= {a，b，c}和E={(a，b)，(b，c)，(a，c)}。然后，根据闭包的定义，闭包C(G) = {b，c}，因为没有离开C.的边。然而，在算法部分下的</e
浏览 1提问于2022-02-09得票数 1
回答已采纳
1回答
无连通有向图的最大子集的大小？
algorithm
给定一个有向图，我如何才能找到一个最大的眩晕子集的大小，以至于它们中没有两个是通过有向路径连接的？
这个问题(或者解决它的算法)有一个共同的名称吗？(提示：“根据Dilworth定理，该问题实际上等价于计算传递闭包后的DAG上链覆盖的最小数目，从而可以将该问题归结为二分图上的
浏览 1提问于2012-10-19得票数 1
1回答
有效地找到所有连通导出子图
algorithm、graph、time-complexity、complexity-theory、graph-algorithm
是否有一个有效的(*)算法来寻找一个连通的无向顶点标号图的所有连通(诱导)子图？(*)我理解，在一般情况下，任何这样的算法都可能有O( 2^n )的复杂度，因为对于一个团(Kn)，有2^n个连通子图。但是，我通常处理的图的连通子图要少得多，所以我正在寻找一种方法来生成它们，而
浏览 3提问于2013-03-27得票数 12
回答已采纳
1回答
SQL中具有闭包表的有向循环图
mysql、sql、transitive-closure-table
我试图确定是否可以轻松地在SQL中用闭包表(和/或其他助手表)来建模有向循环图。例如，假设我有这个有向图(全部指向下)：第一个delete查询删除1到4之间<e
浏览 2提问于2014-03-03得票数 5
1回答
仅用graphviz工具生成传递闭包
graphviz
我需要以点格式处理有向图，并得到子图的传递闭包(实际上是一个节点)。例如，给出 E -> B; C -> D; A -> B; C -> D;
我知道这在python和许多其他语言中是可能的</em
浏览 2提问于2013-09-09得票数 3
回答已采纳
4回答
图(节点和边)
haskell、graph-theory
除了使用bfs或树等，我愿意得到一种合适的方法，以便从一个节点到达图中的某个特定节点。
当我要求haskell中的代码从一个节点到达特定节点的能力时，有必要告诉您，我对haskell完全陌生。我一直在阅读教程和简单的例子，但是当涉及到实现时，我就迷失了。我的图是有向图，说我想检查我是否能从图中的节点v到达节点w。
浏览 2提问于2009-07-19得票数 2
1回答
如何将BGL有向图用作无向图(用于布局算法)？
c++、boost、boost-graph
我正在用Boost.Graph做一个有向图(实际上是一个双向图)。我想使用现有的布局算法( Kamada-Kawai或Fruchterman-Reingold)，但它们只接受无向图作为参数。使用这些布局算法最简单的方法是什么？更广泛地说，什么是引诱算法认为有向图实际上是无向图的</em
浏览 3提问于2009-02-16得票数 3
回答已采纳
1回答
给定图(维数未知)中的传递闭包
python、networkx
我有一个有向图但是我不知道里面有多少元素。它可以用不同的词来表达。例如，它们可以以a-b、b-c、c-d、……的方式连接。我想添加到这个图传递闭包，它将创建a-c，a-d等之间的连接。
对于任何给定的图，我应该在算法中进行哪些更改才能
浏览 0提问于2015-11-13得票数 1
1回答
用networkx计算有向图的传递闭包
python、networkx、directed-graph
我努力寻找如何用networkx计算有向图的传递闭包，却出人意料地一无所获。这似乎不太可能不在networkx中，所以...它在哪里?(我知道Sage包含此功能。)
浏览 1提问于2014-10-23得票数 1
1回答
确定第一组CFG
python、parsing、context-free-grammar
对于LR-解析器，第一组定义如下()：
对于所有规则X → tα (t是一个终端，α是任意的符号串)，t位于第一个(X)中。对于所有规则X → Yα (Y是一个非终端，α是任意的符号串)，FIRST(Y)的所有元素都位于第一个(X)中
浏览 3提问于2013-09-17得票数 2
3回答
有向图的Boruvka最小生成树算法
python、algorithm、graph、cuda、breadth-first-search
博鲁夫卡算法()是否只适用于无向图？例如，如果我们有一个图结构，如下所示：那么最小生成树应该包括边：然而，Boruvka的算法
浏览 1提问于2012-12-11得票数 2
1回答
如何从具有排他性子集的有向无圈图中查询
algorithm、graph-theory、dependency-management、directed-acyclic-graphs
抽象问题：我有一个DAG来存储我的程序集(顶点)及其依赖关系(边)。给定一个或多个程序集，我需要查询以获得所有涉及的程序集及其依赖项的集合。困难之
浏览 2提问于2011-09-22得票数 6
回答已采纳
2回答
当项可以在多个类中时保持一致性
object-oriented、object-oriented-design、class、relational-database
例如，我有一个商业目录网站，根据他们提供的产品/服务显示不同公司的概况。例如，LG公司生产智能手机、电视、搅拌机等。我希望公司相应地出现在每个类别上，并且每个父类别显示它持有电子公司( 243 )有243家生产电子产品的公司的公司数量。 1.独一无二的总数.里面的公司。如果LG公司生产电视和智能手机，那么母公司就会将一家公司计算两次，从而提供错误的信息。用户可能会认为在这个类别中有2家公司，而只有一家。
我怎样
浏览 0提问于2016-10-29得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
