我知道Tarjan算法解决了在线性时间内找到图中的桥(割边)的问题。我正在尝试以一种稍微不同的方式来解决这个问题。我试着找出所有属于一个循环的边。为此，我使用了一个父数组，比如parent[i]=j。这里j是i的父类，因为对dfs(i)的调用是在dfs(j)内部进行的，也是从dfs(j)发出的。我</e
浏览 17提问于2020-04-26得票数 0
所以我正在读Robert Sedgewick的算法第四版。书和在有向图中查找圈的方法与在无向图中查找圈的方法不同。以下是在无向图中查找循环的示例代码 public boolean[] marked;
pu
浏览 0提问于2012-06-11得票数 15
回答已采纳
1回答
创建索引本身与计算网桥列表相同。问题是如何在删除边缘后保持该索引，而不完全重新计算它。也许存储所有(简单)循环的列表并删除需要该边(索引维护)的所有循环将与"is this edge in a cycle“一起工作，以检查其要求。对于更大的图，这将是相当昂贵的计算，因为循环的数量随着连接度的增加而呈指数级增长。附注:以下摘录自“算法导论”中的术语
浏览 5提问于2021-04-14得票数 1
根据，在无向图中找到最小生成树的步骤如下：
如果我们检查以下条件，而不是这种方法，该怎么办：
(图中已经包含的顶点数) <= (图中已经包含的
浏览 6提问于2020-10-07得票数 0
回答已采纳
我“找到”了一个在无向图中寻找最大流的算法，我认为这个算法是不正确的，但我找不到我的错误。这是我的算法:我们以如下方式构造一个新的有向图:对于每条边${u，v}$，我们创建边$(u，v)$和$(v，u)$，其中$c((u，v))=c((v，u))=c({u，v})$。现在我们用下面的方法在第一个图中做一个流:让
浏览 4提问于2014-11-13得票数 1
例如，假设我有下面的类 String id;}带有地图的：
var foosMap = <String, Foo>{"foo1": new Foo("foo1"), "foo2": new Foo("foo2")};va
浏览 0提问于2013-03-20得票数 7
回答已采纳
1回答
搜索"WLAN网桥“主要给出WDS网桥(wifi设备到wifi设备通信)的结果。我想要做的基本上是连接路由器的WLAN和WAN接口(禁用NAT、路由器的DHCP等)，这样一旦无线客户端成功地向AP (无线路由器)进行身份验证，它就可以获得一个IP地址，而不是从AP，而是从道路上的DHCP服务器(在AP的WAN接口上)，并进入路由器在WA
浏览 0提问于2018-02-11得票数 0
回答已采纳
2回答
Dijkstra算法是求解最短路径问题的最快算法之一。在我的例子中，网络是由节点组成的，其中边的权重是我得到的利润。我想知道我是否可以逆转Dijkstra的算法来解决这个问题，但是我意识到如果我们在一个闭环中运行会怎么样(因为成本会越来越高，它将永远持续下去)。我知道如何把它作为整数规划问题来解决，这样我就可以验证算法的
浏览 3提问于2014-04-23得票数 1
回答已采纳
1回答
我想创建一个无向图，其中：
哪种图形算法对我有用？最好的是最后一个--约翰，鲍勃(9)。
我认为这是有向图问题上的最小生成树。我发现了Chu-Liu/Edmond的算法，我知道这个算法适用于边加权图，而且我有顶点加权
浏览 0提问于2020-08-09得票数 0
1回答
设G= (V，E)是一个加权连通无向图，E是e中的任意一条边。给出一个线性时间算法，它决定是否存在包含边e的最小生成树。我设法找到了问题1的一个奇怪的“解决方案”，它似乎是有效的，但我不认为它是线性的：
他们建议对每条边(u，v)使用联合查找和联合(u，v)，使得W(u，v) < W(e)。现在，假设e= (x，y)。= find(y)，那么x和y是不相连<
浏览 1提问于2013-03-02得票数 2
回答已采纳
1回答
我参加了斯坦福大学的在线算法课程，其中一个问题如下：
用一个改进的Dijkstra算法解决这个问题，它运行在不符合要求的</em
浏览 0提问于2018-12-02得票数 0
回答已采纳
假设您使用Kruskal或Prim的算法来计算第一个MST，您希望检查是否还有其他的MST。我可以在O(E/V)时间内做到这一点。我知道已经有一些算法可以在线性时间内找到单个MST：
随机算法可以在线性期望时间内求解。G
浏览 2提问于2013-12-20得票数 0
回答已采纳
我已经实现了一个BFS算法来检测图中的循环，这是以下代码： if(rootstring name; vector <node *> adj;这是我构建的图grp->addEdge("A","C"
浏览 0提问于2012-02-28得票数 0
3回答
很抱歉这个简单的问题，但是有什么方法可以确定一个完全连通的图吗？我读过一些论文，指出图的完全连通性是图分析的前提。我在Matlab的一些图形分析工具箱中搜索确定连通性的函数，但这些工具箱中似乎至少没有提供任何功能。你能在这方面给我一些建议吗？非常感谢！
浏览 13提问于2013-04-01得票数 0
2回答
有人知道从有向图中计算有向图的有效算法吗？请参阅 (维基百科的文章提到了底部附近的有向图案例(在泛化部分)。理想情况下，我希望在线性时间内这样做。从该节：
，如果G是有向图，它的有向线图或有向图对于G的每个边都有一个顶点。表示G中从u到v和从w到x的有向边<
浏览 7提问于2009-06-03得票数 2
11回答
我需要一个在无向图中找到所有简单循环的有效算法。我知道成本可能是指数级的，问题是NP-完全的，但我将在一个小图中使用它(最多20-30个顶点)，并且圈的数量很少。经过长时间的研究(主要是在这里)，我仍然没有一个可行的方法。以下是我的搜索摘要：
->仅检测是否存在循环
浏览 4提问于2012-09-11得票数 72
1回答
我有一个图形问题，我不确定如何解决。
我有一个无向图，有N个顶点，编号为1-N。每个编号为i的顶点都有一个任意的“等级”，它可以位于1-i的任何位置。多个顶点可以具有相同的等级。当遍历图形时，任何具有秩r的顶点都可以立即传送/遍历到具有相同秩r的另一个顶点。这意味着如果来自组件A的至少一个顶点与来自组件B的顶点具有相同的等级，则未<em
浏览 2提问于2021-12-04得票数 2
2回答
我知道如何使用DFS变体找到无向图的交点。但它似乎是对无向图和只寻找后缘。但是，如果我的图有前向边或交叉边，我知道我总是可以为每个节点运行dfs，并且计算出它，但是有更好的算法吗？
浏览 3提问于2017-05-14得票数 0
假设您有一组可以并行完成的任务。每个作业都有一个时间要求(第一个作业的时间要求是t_i )。还有一些依赖项，其中第一条是说您必须在作业u_i之前执行作业v_i，您必须尽量减少所需的总时间。通过将这些关系转换成一个有向无圈图，然后使用它来确定并行处理哪些关系，这很容易做到。
如果我不清楚，这里有一个例子。(3，12)=12个单位的时间，这需要5个单位的时间。因此，5是完成后的
浏览 4提问于2014-05-07得票数 0
回答已采纳
这是一个复习问题，我想知道我的答案是否正确。你有一个加权无向图的MST，T，然后在原始图的节点(u和v)之间引入一条新的边，以创建一个新的图G‘。给出了判定T是否是G‘的MST的线性时间算法。原始图的MST T不包含任何圈。从节点u到节
浏览 2提问于2019-10-26得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
