问题标签 [undirected-graph]

我正在寻找一种算法，当一个给定的两个节点's'和't'在一个未处理的图中，找到最小切边，它将图分成两个A和B，'s'将在A和't ' 将在 B.

我看到大多数人建议使用 Ford-Fulkerson 算法来完成这项任务，在这里。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以通过动态树来加速。因为我想以最快的方式找到最小切边。

哪种算法可以更快地在巨大的无向图中找到最小切边？

在研究这些算法的细节时，我想听听一些建议。

提前致谢

输入：顶点列表和邻接列表。

输出：好的顶点的最大子集。

（如果一个子集中的顶点至少有 2 个相邻的顶点和至少 2 个不相邻的顶点，我们就称它为“好顶点”。）

示例 1：

示例 2：

因为对于输出中的每个顶点，它至少有 2 个顶点连接，并且至少有 2 个顶点没有与之连接。

我一直在尝试找到一种算法来搜索图是否已连接。该图是无向的，我只想找到一个解决方案（可以有多个）或者如果没有。我在找一个alg。执行接近线性时间，可能是 O(logN) 或 O(NlogN)。

DFS 能否胜任这项任务，或者对于这个特定问题是否有另一种选择？

我有一个边缘列表作为单元格数组 ['a' 'b','c' 'b','b' 'a']

我一直在尝试使用 G=graph(s,t) 在 MATLAB 中生成一个图形，但我得到一个重复边的错误，我认为这是因为 [ab] 和 [ba]。我无法删除单元格数组中的那些。

我怎样才能删除那些？

谢谢你。

该图以如下格式表示：

我需要使用相邻列表来读取这些边缘。但是如果我想把它当作一个无向图，也就是忽略所有边的所有直接性。我怎么知道每对节点的连通性？

例如，在无向图中，(NODE 2, NODE 8) 之间的最短距离是 2 (2->1>8)，但是使用 Dijkstra 算法对该图得到 4 (2->3->6->7 -> 8）。如何在仍然使用相同技术读取边的同时表示无向图？

我正在处理图表中的一个问题，并试图找出找到独特的路径

让我举个例子，让我们考虑一个有 4 个节点和 6 个边的图，边如下 -

1 2
2 3
3 4
4 1
1 3
2 4

长度为 5 的唯一循环路径将是 -

1. 1 -> 2 -> 3 -> 4 -> 1

2. 1 -> 3 -> 2 -> 4 -> 1

3. 1 -> 2 -> 4 -> 3 -> 1

   如果路径的边集相等，则认为两条路径相等。考虑两条路径 1 -> 2 -> 3 -> 4 -> 1 和 1 -> 3 -> 2 -> 4 -> 1 第一条路径就是集合 = [(1,2), (2,3 ), (3,4), (4,1)]，而第二个是 = [(1,3), (3,2), (2,4), (4,1)]
   显然，这两组是不同的，因此路径也是不同的。边的顺序无关紧要，因为您只比较任何两组（路径）之间公共边的存在。

获得循环路径后，如何检查路径中是否具有相同的节点集？即 , 1 -> 2 -> 3 -> 4 -> 1 和 1 -> 4 -> 3 -> 2 -> 1 具有相同的集合，即
[(1,2), (2,3), (3 ,4), (4,1)] 以不同的顺序。
我想实现一对集合的映射并检查重复项.. 仍在寻找更好的选择。对如何进行的任何帮助表示赞赏？

我有一个连接路径的网格，如下所示：

网格是一个二维数组，创建如下：

数组的每个元素都包含一个类型block如下的对象：

为了定义连接的组件，我在网格上实现了广度优先搜索。我需要它完全连接。这是我的 BFS 代码：

问题是当我运行算法时，结果count非常高，就像在 50 年代一样，最多应该是 1 或 2。

我究竟做错了什么？

我对有向图的实现工作正常。这是一个“惰性”版本，因为它使用简单的优先级队列而不是索引队列。我更改了代码以获得无向图的解决方案，但它不起作用。dijkstra(int s)是一个类的方法Graph。的实现Graph基于邻接列表。整个代码基于 Sedgewick 书中的解释。

我一直在尝试使用无向图创建邻接列表。一切都很顺利，除了当我需要一个节点（或我的代码中的顶点）有多个连接到它的边时。我有 6 个顶点 A、B、C、D、E、F，只有从 A 到 B、A 到 C、A 到 D 的边， 这就是概念上的样子。 我一直在一遍又一遍地尝试提出一种将多个边缘连接在一起的算法，但我无法弄清楚。这是我的结构供参考，我的 else 语句是我需要走到链接边缘的末端并附加新边缘的地方。

如果无向图的边可以这样定向，则无向图具有传递方向，即如果 (x, y) 和 (y, z) 是生成的有向图中的两条边，则在生成的有向图中也存在一条边 (x, z)得到的有向图。

我正在使用真实的食物网网络，我需要检查密集的无向图（模拟食物网中的竞争）是否具有传递方向。无向图在 Java 中表示为邻接矩阵。

编辑：

例如， 对于这个无向图，

我们可以用这种方式定位边缘。因此，该图具有传递方向。