graph-algorithm相关内容

最小添加到强连通图

我有一组节点和它们之间的有向边.边缘没有重量. 如何找到必须添加的最小数量的边以使图牢固连接(即，应该有从每个节点到所有其他节点的路径)?这个问题有名字吗? 解决方案 这是一个非常经典的图形问题. 运行类似Tarjan-SCC算法的算法以查找所有SCC.考虑 每个SCC作为新顶点，在这些 顶点，根据原始图，我们可以得到一个新图. 显然，新图是有向无环图(DAG). 在DAG中 ..

发布时间：2020-08-22 19:59:56 algorithm graph-theory graph-algorithm 其他开发

当一个顶点权重可以减少50％时，两个顶点之间的最短路径?

这是我遇到的一个面试问题: 您会得到一个国家城市之间的飞机地图，基本上是一个带权重的有向图，它是城市之间飞机的成本.您还获得了一张优惠券，可以在任何一次航班上获得50％的优惠.找到您在两个城市之间旅行所需的最低费用? 解决方案 此问题的基本算法是Dijkstra的最短路径算法.但是，我们需要找到一种方法来包含优惠券. 我们可以通过引入优惠券状态来做到这一点.它是availabl ..

发布时间：2020-08-22 19:57:11 algorithm graph-algorithm 其他开发

AStar-名称说明

我正在寻找一种解释，为什么将AStar/A *算法称为AStar.所有类似的(最短路径问题)算法通常都像其开发人员一样命名，那么AStar代表什么? 解决方案 有称为A1和A2的算法.后来，事实证明A2是最佳算法，实际上也是可能的最佳算法，因此他给它取了一个名称A *，该符号象征性地包含了所有可能的版本号. 来源: 1964年，尼尔斯·尼尔森(Nils Nilsson)发明了一 ..

发布时间：2020-08-22 19:29:32 algorithm graph-algorithm dijkstra shortest-path a-star 其他开发

确定给定的加权图是否具有唯一的MST

我正在寻找一种算法(或其他方法)来确定给定的加权图在O(ElogV)中是否具有唯一的MST(最小生成树)? 我对权重一无所知(例如weight(e1)！= weight(e2))，如果该图仅具有一个唯一的MST，则算法仅返回True；否则，则返回False. 我首先使用Kruskal的算法，然后检查find-set(u)== find-set(v)，以便在MST中有一个圆圈，但是这种方 ..

发布时间：2020-08-22 19:26:42 algorithm graph-theory graph-algorithm minimum-spanning-tree 其他开发

查找树中两个顶点之间的简单路径(无向简单图)

给出两个顶点(A和B)和一棵树(G)(无向简单图)- 在G中A和B之间的简单路径中找到顶点. 该算法应以O(V)复杂度运行. 例如-在a和b之间的简单路径中找到顶点: dk ka kb 答案应该是:k 我试图修改BFS以实现该目标，但到目前为止似乎还行不通. 有什么建议吗? 解决方案 如果发现距离后问题是在重建路径，请按以下方式调整BFS:从要 ..

发布时间：2020-08-22 19:17:08 algorithm graph-algorithm breadth-first-search 其他开发

在python中实现Bron–Kerbosch算法

对于一个大学项目，我正在尝试实现 Bron-Kerbosch算法，也就是说，列出给定图中的所有最大集团. 我正在尝试实现第一个算法(无枢轴)，但是我的代码在# dealing with a graph as list of lists graph = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0], ..

发布时间：2020-07-19 21:53:51 python graph-algorithm clique clique-problem Python

是否在DAG的所有拓扑类型上使用随机算法?

没有人知道用于生成DAG拓扑类型的随机算法，其中算法的每次调用都具有生成每个DAG有效拓扑类型的非零概率. > 至关重要的是，该算法不能排除任何有效的拓扑类别，因为它是较大算法的一部分，如果有足够的迭代次数，则必须证明该算法能够探索给定DAG的所有拓扑类别. 有人知道这种算法是否已经开发出来吗? (或者，如果有人知道可以保证生成给定DAG的 all 拓扑类型的合理有效算法，我可能可 ..

发布时间：2020-07-04 01:35:22 random graph-algorithm directed-acyclic-graphs topological-sort 其他开发

在Boost Graph库中，为什么添加边会使Edge迭代器无效(以及其他问题)?

BGL文档中有关图表的一些问题标为“描述符和迭代器无效摘要": 为什么添加边缘会使边缘和邻接迭代器无效；为什么add_edge()行的每一列都不“确定"?进/出边缘列表是否仅会附加? 为什么移除边仅在有向图的情况下才使边迭代器无效；为什么第二行中的倒数第二列不是简单的"EL = vecS"?在无向图的情况下，是否要删除一条边，是否要将其从两个边列表中删除(一个用于源顶点，一个用于目标顶点) ..

发布时间：2020-06-29 20:36:40 iterator graph-algorithm boost-graph listiterator boost-iterators 其他开发

完整图形上最便宜的成本遍历

我想知道是否有一种算法可以: 给定一个完全连接的n个节点的图(具有不同的权重)...将为我提供从节点A(起始节点)到所有其他节点并返回到节点A的最便宜的周期吗?有没有办法改变像Primm这样的算法来实现这一目标? 感谢您的帮助 编辑:我忘了提到我正在处理一个无向图，所以每个顶点的入度=出度. 解决方案 不需要任何此类路径.当且仅当每个节点的入度等于其出度时，它才存在. 您 ..

发布时间：2020-06-17 19:06:29 graph-algorithm graph-traversal 其他开发

如何检测和保存边缘顶点中的循环连通性（孔检测）？

感谢您抽出宝贵的时间阅读我的问题。 我正在研究检测三角形网格中的孔，并用新的三角形填充它们。我已经完成了一些部分，以获取边缘顶点的列表等。以下是产生孔的顶点/边缘，请看一下图像。 （9，62）=>顶点＃9和62使边缘（左洞） （66，9）=>顶点＃66和9使得边（左洞） （70，66）=>顶点＃70和66使边缘（左洞） （62，70）=>顶点＃62和70形成边缘（左洞） （147， ..

发布时间：2020-06-03 21:58:32 algorithm data-structures graph-algorithm stl-algorithm 其他开发

Kosaraju的算法可以找到SCC，但要跟踪SCC之间的边缘？

我目前有一个Kosaraji算法的有效实现，在没有权重的有向图的情况下，它将在图中打印SCC。 我想适应 这是代码： 从集合中导入defaultdict ＃----定义----＃ #Graph Graph = {} ＃图的转置 Transpose_Graph = {} ＃图的已访问节点 Visited_Nodes_Graph = {} ＃已访 ..

发布时间：2020-06-03 21:57:18 python algorithm python-2.7 graph-algorithm kosaraju-algorithm Python

遍历对象的所有后代

遍历对象的所有后代时遇到问题。 以下代码中的'unit'类型为 Unit 在我的程序中。它具有属性 ChildUnits ，该属性返回该单元子代的 List 。 我可以成功地对孩子进行操作。然后我检查那些孩子是否有孩子，如果他们也可以，我也可以对他们进行手术。 但是，我需要检查所有后代 这是我恢复为的代码： foreach （在unit.ChildUn ..

发布时间：2020-06-03 21:52:43 c# algorithm recursion graph-algorithm traversal C#/.NET

如何使用BFS获取包含某些给定节点的路径？

我有一个未加权边的图，其中每个节点都标有字母'a'到'z'。 我想修改BFS算法以获得包含字母'c'，'o'，'d'，'e'的最短路径。这四个字母之间可能还有其他字母。您有起始节点“ a”和结束节点“ b”。您可以假定该路径始终是按该顺序包含这四个字母的路径。为了满足该条件，我该如何修改BFS？ 解决方案 如果您知道如何找到两者之间的最短路径具有BFS的节点，则可以按以下方式解决问题 ..

发布时间：2020-06-03 21:47:20 algorithm graph-algorithm 其他开发

从Expression-Tree提取所有可能的路径并求值以保持TRUE

这是我上一个的后续问题：用于逻辑表达式解析和评估的更好的类结构 简介： 规则作为字符串 逻辑和，逻辑或，逻辑求反和分组，通过标识符（ID）的括号括起来 例如：“ {100} AND（（{{101}或{102}）OR（{103}和{104}））非（{105} OR {106}）“ 当前已被评估为节点的二叉树，如下所示： 从此处获取的代码：如何解析布尔表达式并将其加载到 ..

发布时间：2020-06-03 21:30:40 c# algorithm binary-tree graph-algorithm decision-tree C#/.NET

我可以使用在每个节点上都有一个完整单词的特里吗？

我想实现一个特里来检查路径的有效性，因此我将构建一棵树，通过按目录将其分解，其中包含所有可能的路径构造。因此，诸如 / guest / friendsList / search 之类的东西将从根节点转到其子 guest ，然后是访客的子 friendsList ，然后friendsList的孩子搜索。如果搜索是叶节点，则我的字符串 / guest / friendsList / search 将被 ..

发布时间：2020-06-03 21:30:23 algorithm tree graph-algorithm trie prefix-tree 其他开发

获取图中行驶的最长路线

我有一个相互连接的节点数组 我在下面的节点网络中。这里以0为起点，我想尽可能多地移动节点，而一个节点仅移动一次。 在从0到目标节点的行程中，我也只希望有一个奇数节点（例如1、3、5、7）。 现在，我需要找出从起始位置0开始可以走的最长路线。 示例： int [] array = {0，9，0，2，6，6，8，0，8，3，0}; 在上图中 ..

发布时间：2020-06-03 21:20:01 java algorithm graph tree graph-algorithm Java开发

Tarjan算法的非递归版本

我有以下Tarjan算法的（递归）实现，可以在图中找到强连通的组件，并且可以正常工作： 公共类StronglyConnectedComponents { public static List>搜索（图形图） { StronglyConnectedComponents scc = new StronglyConnectedComponents（）; ret ..

发布时间：2020-06-03 21:10:09 c# algorithm graph-algorithm tarjans-algorithm C#/.NET

最佳匹配算法将对局平均分配

我需要一种算法，该算法可以进行任何数量的对决，如您在下面看到的那样，并尽可能地将它们平均分组，每次参加一次。我为8和3支球队全面产生了以下比赛。我遇到了很多问题，无法完成上一轮的孤儿游戏。 现在，这些回合是任意的，但是您可以告诉每个参加者可以在每个回合中找到（1,2,3,4,5,6,7,8）。现在可以删除或添加这些对战，并在下面生成这些对战后对其进行随机排序，因此需要平均分配它们并在以后找到 ..

发布时间：2020-06-03 21:08:48 c# .net algorithm graph-algorithm tournament C#/.NET

如何找到两个图的最大公共子图？

嗨，我需要一个寻找图算法的帮助 我正在研究与距离函数有关的以下方程式 d（g1，g2）= 1-│mcs（g1，g2）│/ │g1│+│g2│-│mcs（g1，g2）│ 其中 d（g1，g2）：是基于最大公共子图 的距离函数。 g1，g2 是两个图。 mcs（g1，g2）：是两个图g1，g2 的最大公共子图，其中mcs是两个主题 ..

发布时间：2020-06-03 21:02:43 algorithm graph-algorithm 其他开发

在无向图上查找和打印O（n）复杂度简单循环的算法

给出图G（V，E），无向图。 | E | = m，| V | = n 该图的数据结构为邻接列表 如何查找和打印复杂度为 O（n）的简单循环（或打印没有这样的循环）？ （如果有循环，输出应该是循环的一部分的顶点列表。） 我知道如何根据 O的复杂度找到循环（n），互联网上也有人。 我的问题是如何打印它。 这是我尝试做的事情： D ..

发布时间：2020-06-03 21:01:40 algorithm graph-algorithm depth-first-search 其他开发