问题标签 [undirected-graph]

我有一个连接的无向图。如何使它成为双连接添加最小数量的边？

我试着在网上搜索这个特定的算法，也试着自己思考，但什么也想不通。伪代码会很棒。谢谢！

我有一组边 E，我想知道是否可以安全地删除 E 中的边 i，这意味着如果我将其从图中删除，则该图仍应连接。

在我的理解中，这意味着边 i 必须位于一个圆上。输出应该是我无法删除的所有边的索引列表。

问题：

我的不同解决方案似乎做了正确的事情，但是太慢了（效率低下）。

我的解决方案之一是：

这种方式太慢了。

然后我决定重写我的代码并使用广度优先搜索来查看没有边缘 i 的另一条路径是否可行。

我认为它的性能足够好，但似乎不是。要么我以非常糟糕的方式实现，要么这也是该任务的错误算法。

这是我拥有的 C++ 代码中的算法（删除了一些不重要的部分）：

你知道我的任何解决方案可以让它更快吗，或者你知道我的问题有更好的算法吗？

我目前正在使用无向图编写程序。我通过创建连接的邻接矩阵来表示这一点。

我试图做的是找到给定节点连接到的所有节点（通过任何一系列边）。我试图编写一个函数，对给定节点执行此操作并返回一个向量，该向量在向量中的每个点中包含 1 或 0，该向量由给定节点是否可以通过图中的任何路径到达该节点来确定。然后我想获取这个向量并将其中的所有值相加，这将返回该节点可到达的节点数量。然后我想为图中的每个节点获取所有这些值并将它们放入一个向量中，然后找到最大值，它表示最大循环中的节点数量。

我的问题不是我的函数定义代码收到错误（虽然我是），而是我意识到我正在错误地编写这个递归函数，但我不知道如何改变它以满足我的需要。我在下面包含了我的代码，任何指导将不胜感激。

函数定义：

调用 main.cpp：

我试图在 Python 中提出一个贪心算法，它在给定某个起始顶点的情况下返回无向图中的顶点。我知道 DFS 确定是否存在循环，但我试图实际返回形成循环的顶点。我使用邻接矩阵来表示下图：

从图形上看，这是一个由单个循环组成的无向图。

我目前的思考过程是将我的起始索引设置为1我遇到的第一个索引（在这种情况下adjacencyMatrix[0][1]）。然后我会查看该行的其余部分，看看是否1有另一个，因为这意味着我当前的顶点连接到该索引。但是，我不完全确定（a）这是否是正确的方法以及（b）如何“移动”到下一个顶点。例如，我将如何导航我的嵌套for循环以从adjacencyMatrix[0][1]顶点移动到adjacencyMatrix[0][2]顶点？我会交换行和列索引吗？

编辑 我想出的这个解决方案似乎适用于我尝试过的几个图表：

这不是最优雅的解决方案，我确信需要进行一些重大的重构。

If a directed Edge is implemented something like:

then which is the difference for implementing an undirected Edge while when we create a new Edge we also have to say in both cases: new EdgeImpl(node1, node2)? I do not get the difference in implementation :(

Edit

I was analyzing, more concretely, this example

假设我们有一个无向图，以及两个节点 A 和 B。我需要编写一个方法来找到 A 和 B 之间没有环的路径。该图的所有边具有相同的权重。该方法必须在找到这样的路径后立即终止。我该如何实施？

在 igraph 中，我发现了两种将图转换为无向图的不同方法：
第一种是to_undirected简单地“将有向图转换为无向图”。第二个是在副本上as_undirected调用。to_undirected

在 NetworkX 中，我发现只有一种方法to_undirected可以简单地创建图的无向深层副本。问题是我真的找不到类似于 igraph 中第一个的方法。是否有任何解决方案可以在不使用 NetworkX 创建副本的情况下转换图形？

我正在编写一个算法来建立一个无向的对象图。在向图中的特定元素正确添加和删除边之后，我到达了某个点，我得到了这个错误。

请注意，这是在程序已经允许我向图中添加边之后，并且我将对象输入到 addEdge 方法中的方式没有任何改变。addEdge 的代码是：

在运行调试器时，我发现在代码开头调用 mGraph.get(one) 时它返回一个 HashSet，但当错误发生时它返回 Collections$UnmodifiableSet。为什么会这样？

我去无向图G，我的目标是找到所有可能的链比N 一对一关系中的节点最长。

例如：

在下图中，长度超过 2 个节点的“链”以一对一的关系是：

那么解决这个问题的最佳方法或算法是什么？

我需要创建一个限制合并机会的矩阵（以整数向量表示）。合并机会由无向网络中的相邻节点（即通过边连接）定义。

例如，考虑这个无向图：

D

¦

A --- B--------

¦ ..............¦

C----E-----F

从节点 A 开始，我可以合并 BC 和 D。如果 B 是部分，F 和 E 也可以是部分。如果 C 是一部分，E 可能是一部分。此外，我可以合并所有这些，或者一个都不合并。这对所有可能的起始节点都有效。

矩阵（或矩阵集）应包含在限制合并向量的约束中。例如，向量 [A,B,0,0,E,0] 应该被允许，而向量 [A,0,0,0,E,F] 则不允许，因为它不是一个连续的空间。不幸的是，我仍然无法创建一个包含 n 列来描述这种合并可能性的矩阵。

考虑到 n 个节点，可以创建 n 个不同的矩阵来定义 n 个不同的有向网络（每个都从不同的节点开始）。不幸的是，这会产生问题，因为并非所有的合并可能性都是允许的。

我虽然预先创建了所有合并的可能性，但是问题变得太复杂了。

谢谢！