问题标签 [undirected-graph]

我正在尝试使用顶点的“实时提要”在 Java 中创建一个无向图。我有来自 txt 文件的顶点。文件的结构是这样的，

1 2 #connect node 1 with node 2

2 3 #connect node 1 with node 2

等等。我决定创建一个 ArrayList 的 ArrayList（一个 2d ArrayList）来将节点和边存储在一个数组列表中。我的要求是我必须保持恒定的时间来检查两个边缘之间是否存在路径。我还没有真正使用过 2d ArrayList，你们的任何先机将不胜感激。

所以，我对 Python 和一般编程比较陌生。但是，我有一个没有权重的无向图。有些节点是连接的，有些没有。有些只有一个连接，有些会有多个。每个节点代表一个个体，如果它们的对应节点由一条边连接，则可以与另一个个体匹配。我有兴趣找到仅包含成对匹配的所有最大基数集。

我首先遍历节点并立即删除匹配项。代码膨胀得很快，变得一团糟。我想知道是否有一种简单而干净的方法来做到这一点。我从包 networkx 中尝试了 maximal_matching(G) ，但它总是只提供一个匹配。

我正在尝试从邻接表中制作一个无向图来练习 Karger 的 Min Cut 算法。以下是我的代码

假设邻接表如下，顶点用整数表示

总的来说，该图将有 5 条边，因此包含与顶点关联的边的索引的列表长度不能超过 5 长。

例如，我希望顶点“2”只有两条边的索引，即具有顶点 1 和 3 的边。相反，我得到的是[0, 1, 2, 3, 0, 2, 1, 3]. 我需要帮助找出问题所在。

给定一个二叉树的表示，它可以有最多n 个节点：

从最多有n 个节点的二叉树构造一个无向图。

Graph 表示为一个结构：

我们可以使用Prim、Kruskal或DFS等算法从图中得到一棵树。

问题：有没有一种算法可以从二叉树创建图？例如，如果按顺序遍历二叉树，那么如何从中创建无向图？

我有以下工作程序：（可以在此站点上进行测试：http: //swish.swi-prolog.org，我删除了指向已保存程序的直接链接，因为我注意到任何人都可以编辑它。）

它在无向图中搜索两点之间的路径。重要的部分是结果在“主”谓词的范围内返回。（在 Track 变量中）

结果：

我的问题：

1. 访问节点列表以两种不同的方式传递给谓词。在绑定的 Visited 变量和未绑定的 Track 变量中。这两种不同形式的参数传递的名称是什么？

2. 通常我只想使用未绑定的参数传递（跟踪变量），将结果放在主谓词的范围内。但是我也必须添加 Visited 变量，因为成员检查对 Track 变量不起作用（我不知道为什么）。是否有可能仅以无限制的方式通过 Track 使其工作？（没有 Visited 变量）

非常感谢！

无向图中的握手引理状态偶数个顶点必须具有奇数度。

但是3个人互相握手，6个握手，或者两个一个。所以没有奇数度的顶点。

握手引理是否成立，因为 0 是偶数并且有零个奇数度的顶点？

我并不怀疑引理是正确的，只是认为我错过了一些非常明显的东西。

我们提供了一个无向图、源节点、目标节点和额外边的权重，您可以使用它来连接之前未连接的任何两个节点。您必须找到源和目的地之间可能的路径的最小权重。您只能使用提供的边缘一次。这是一个示例：具有 5 条边的图形如下 1->2 权重为 1,2->3 权重为 2,3->4 权重为 3,4->5 权重为 1,1- >4 权重为 3，源顶点为顶点 1，目的地为顶点 4。我们必须告诉最小路径长度。（在这种情况下是 2）我们可以使用添加一个额外的权重边缘 1（这里从 1 到 5 ）我想知道如何在 java 中实现它。

我正在测试 igraph python 来绘制无向图。问题是标签由于某些原因被切断。标签包含空格，所以我不得不用下划线替换空格。

例如：如果标签是 Mike_Jorden，则仅显示 e_jorde，有时显示 ike_jorde。

我的输入是格式为 N_Col 的 csv 文件，例如作为输入：

我的代码如下：

我尝试了不同的布局算法，但仍然遇到同样的问题。请有任何建议。

我们可以假设所有边的权重都是正的，并且您可以在 O(1) 时间内枚举从顶点向外引导的边，以及向内引导的边。

例如，您可以执行 Dijkstra 遍历（或 A*，具有可接受的启发式）并标记每个顶点从起点到终点的距离，然后在这些标记上反向递归，因为它们描述了最佳路径上的可能前任. 也就是说，对于每个可能的前任，如果标记距离之间的差异等于连接它们的边的权重，您可以确定它是否在贪婪的最佳路径上找到。

在查看可能的前辈时，传入边的成本加上到每个顶点的最佳距离之间的差异等于在解决方案中包含这条边所导致的最优性损失（最优路径上的边为零）。所以也许问题变成了：如何最好地扩展它以产生所有可能的路径，通过递减最优性排序？有没有一种干净的方法来对这种元图执行最佳优先遍历？

这似乎是寻求有用解决方案的正确方向。也许需要记住的有用的事情是，如果您到目前为止探索的路径部分可能是至少x次优的解决方案的一部分，则只需沿着最后访问的x距离进行循环检查（任何x次优的路径不可能包含比x更长的循环）。

有没有更有效的方法？

作为一个额外的问题，是否也可以在具有负边权重的图（已知大小）上执行此操作？如果引入负循环会变得更加困难吗？（请记住，由于我们只在寻找非循环路径，这并不一定意味着最优解会消失。）

无向图和无权图有什么区别？它们是一样的吗？只想100%确定。

我对这一切都很陌生。请不要锁定我只是需要帮助并想学习。