Python中的Hopcroft-Karp算法
我正在尝试使用 Python 在 Python 中实现 Hopcroft Karp 算法networkx 作为图形表示. 目前我是这样的: #二部图算法将 networkx 导入为 nx进口藏品类 HopcroftKarp(对象):无穷大 = -1def __init__(self, G):自我.G = G定义匹配(自我):self.N1, self.N2 = self.partition
..
graph-algorithm相关内容
使用堆栈的非递归深度优先搜索 (DFS)
好的，这是我在 Stack Overflow 上的第一篇文章，我已经阅读了一段时间并且非常欣赏这个网站.我希望这是可以接受的问题.所以我一直在通读 Intro to Algorithms (Cormen. MIT Press)，我一直在读图算法.我一直在研究为广度和深度优先搜索而设计的形式化算法，非常详细. 这是深度优先搜索的伪代码: DFS(G)---------------------
..
如何判断一个图是否是二部图?
我一直在尝试理解二部图.据我所知，它是一个图 G，它可以分为两个子图 U 和 V.所以 U 和 V 的交集是一个空集，并集是图 G.我试图找出一个图是否是二部图或不使用 BFS.我仍然不清楚我们如何使用 BFS 找到它. 假设我们有如下定义的图形. a:e,f是c:e,f,hd:g,he:a,b,cf:a,c,gg:f,dh:c,d 这里我需要的是逐步解释这个图是如何二分的或不使用 BF
..
如何在广度优先搜索中跟踪深度?
我有一棵树作为广度优先搜索的输入，我想知道随着算法的进展它处于哪个级别? # 广度优先搜索实现图 = {'A B C D']，'B':['A'],'C':['A','E','F'],'D':['A','G','H'],'E':['C'],'F':['C'],'G':['D'],'高清']}定义广度_第一_搜索(图，源):"""这个函数是breadth_first_search程序的实现"""#
..
是否有不超过 x 天从 a 城市到 b 城市的路线?
我在一家贸易公司面试时，被问到这个问题， 您乘坐公共汽车穿越州，公共汽车可以停在任何 C 个可能的城市，您需要找到从城市 a 到城市 b 的方法.共有 B 辆巴士，每辆巴士都在两个城市之间行驶.所有公交车都以每日为基础运行，例如每辆公交车 x 在第 d1 天离开某个城市 c1，并在另一天 d2(d2>d1)到达另一个城市 b1.假设如果您在 d 天到达一个城市，您可以搭乘任何在 d 天或之后
..
在直接加权图中找到从节点 A 到节点 B 的所有简单路径，权重之和小于某个值?
我有一个有向加权图 G=(V,E)，它可能有环. 我正在尝试确定完成任务的最佳时间效率算法:t找到 G 中源节点和目标节点之间的所有简单路径，该路径中边的总权重小于某个值(为方便起见，我们将此值表示为 PATH_WEIGHT_LIMIT) 所有权重都是正数，可以浮动. 所以，我的函数原型是: def find_paths(G, source, target, path_weig
..
BFS与拓扑排序的关系
拓扑排序可以使用 DFS(边缘反转)和队列来完成.BFS 也可以使用队列来完成.使用队列进行 BFS 时元素的存储和检索方式与使用队列进行拓扑排序时的元素存储和检索方式之间是否存在任何关系.澄清会有所帮助.谢谢. 解决方案 BFS 从源节点开始逐层遍历，使得节点按照离源的距离的顺序出现，这也意味着父节点出现在子节点之前位于下一级的节点. 这可能看起来像我们在拓扑排序中需要的东西，但是
..
包含给定节点集的最小连通子图
我有一个未加权的连通图.我想找到一个连接的子图，它肯定包含一组特定的节点，并且尽可能少的额外.这怎么可能实现? 为了以防万一，我会用更精确的语言重申这个问题.令 G(V,E) 是一个未加权、无向、连通图.设 N 是 V 的某个子集.找到 G(V,E) 的最小连通子图 G'(V',E') 使得 N 是 V' 的子集的最佳方法是什么? 近似值很好. 解决方案 我想不出一种有效的算法
..
在图中查找具有最大最小容量的路径
我正在帮助一个与工作相关的项目的朋友，他需要计算从节点 a 到节点 b 的最大容量，其中边缘具有容量.然而，从 a 到 b 的路径中的最大容量受到容量最低的边的限制. 让我试着用一个简单的例子来解释 所以这个图是一个带加权边的有向图，它可以是循环的.具有最高容量的路径将是 s->b->t 并且容量为 250，因为该边正在设置限制. 我做了一些阅读，发现这种类型的问题是一个“最宽路
..
如何在线性时间内找到树中最短的简单路径?
这是 Vazirani 的算法书中的一个问题 这个问题的输入是一个边上具有整数权重的树 T.权重可能为负，零，或正.给出一个线性时间算法来寻找 T 中最短的简单路径. a 的长度path 是路径中边的权重之和.如果没有重复顶点，则路径是简单的.笔记路径的端点是不受约束的. 提示:这与寻找树中最大独立集的问题非常相似. 如何在线性时间内解决这个问题? 这是我的算法，但我想知道
..
有效地找到所有连接的诱导子图
是否有一种有效的(*)算法来查找连接的无向顶点标记图的所有连接(诱导)子图? (*) 我明白，在一般情况下，任何这样的算法都可能有 O(2^n) 复杂度，因为对于一个集团 (Kn)，有 2^n 个连接的子图.但是，我通常处理的图的连接子图要少得多，所以我正在寻找一种方法来生成它们，而不必考虑所有 2^n 个子图并丢弃那些未连接的子图(如这个问题的解决方案. 运行时间与解决方案数量成线性
..
图形直径的算法?
如果你有一个图，需要求它的直径(两个节点之间的最大距离)，你怎么做O(log v * (v + e))复杂性. 维基百科说你可以使用 Dijkstra 算法 带有 二元堆.但我不明白这是如何工作的.谁能解释一下? 或者显示伪代码? 解决方案 我知道我迟到了一年，但我不相信这些答案中的任何一个是正确的.OP 在评论中提到边缘未加权；在这种情况下，最佳算法在 O(nω log n)
..
为什么不能在有向图上使用 Prim 或 Kruskal 算法?
Prim 和 Kruskal 算法用于找到连通图和无向图的最小生成树.为什么它们不能用在有向图上? 解决方案 这些算法一开始就工作是一个小奇迹——大多数贪婪算法只是在某些情况下崩溃和烧毁.假设您想使用它们来找到最小跨度树状(从一个顶点到所有其他顶点的有向路径)，那么 Kruskal 的一个有问题的图看起来像这样. 5-->一个//^1||2\v/-->乙3 我们将采用成本 1 的 a
..
查找图的连接点或切点的算法说明
我已经在网上搜索过，但找不到任何关于用于查找图的所有关节顶点的 DFS 算法的解释.甚至没有维基页面. 通过阅读，我了解了这里的基本事实.PDF 每个节点都有一个变量，它实际上是在查看后边缘并找到离根节点最近和最上层的节点.处理完所有边后就会找到. 但我不明白如何找到它&DFS 执行期间每个节点的 up 变量.这个变量到底在做什么? 请解释算法. 谢谢. 解决方
..
为什么 Dijkstra 算法使用减键?
教给我的 Dijkstra 算法如下 而 pqueue 不为空:距离，节点 = pqueue.delete_min()如果节点已被访问:继续别的:将节点标记为已访问如果节点 == 目标:休息对于节点的每个邻居:pqueue.insert(距离+ distance_to_neighbor，邻居) 但我一直在阅读有关该算法的一些资料，我看到很多版本都使用减少键而不是插入. 这是为什么，这两种
..
检测邻接矩阵中的循环
令A 为图G = (V,E) 的邻接矩阵.A(i,j) = 1 如果节点 i 和 j 与一条边相连，A(i,j)= 0 否则. 我的目标是了解 G 是否是非循环的.循环定义如下: i 和 j 相连:A(i,j) = 1 j 和 k 相连:A(j,k) = 1 k 和 i 相连:A(k,i) = 1 我已经实现了一个导航矩阵的解决方案，如下所示: 从边开始(i,j) 选
..
如何在Matlab中找到连接的组件?
数组 A = 2 32 54 85 67 8 我想得到'conidx = [2 3 5 6] and [4 7 8]'的结果. [2 3] 的值之一存在于第 2 行， [2 5] 的值之一存在于第 4 行， 所以[2 3]、[2 5]和[5 6]是连通的， 最后我可以得到 [2 3 5 6] 的连接索引. 否则，[4 8] 的值之一存在于第 5 行， 所以
..
使用 Dijkstra 算法的负权重
我试图理解为什么 Dijkstra 的算法不适用于负权重.阅读关于最短路径的示例，我试图找出以下场景: 2A-------B\/3 \/-2\/C 来自网站: 假设所有的边都是从左到右的，如果我们开始对于 A，Dijkstra 算法将选择边 (A,x) 最小化d(A,A)+length(edge)，即(A,B).然后它设置 d(A,B)=2 并选择另一个边 (y,C) 最小化 d(A,
..
查找两个图节点之间的所有路径
我正在研究 Dijkstras 算法的实现，以检索路由网络上互连节点之间的最短路径.我有实施工作.当我将起始节点传递给算法时，它返回所有节点的所有最短路径. 我的问题:如何检索从节点 A 到节点 G 的所有可能路径，甚至从节点 A 返回到节点 A 的所有可能路径 解决方案 寻找所有可能的路径是一个难题，因为简单路径的数量是指数级的.即使找到第 k 个最短路径 [或最长路径] 也是 N
..
查找有向图中的所有循环
如何在有向图中找到(迭代)从/到给定节点的所有循环? 例如，我想要这样的东西: A->B->AA->B->C->A 但不是:B->C->B 解决方案 我在搜索中找到了这个页面，由于循环与强连通分量不同，我一直在搜索，最后，我找到了一个有效的算法，列出了所有有向图的(基本)循环.它来自 Donald B. Johnson，该论文可以在以下链接中找到: http://www.c
..