问题标签 [undirected-graph]

我试图更好地理解 Dijkstra 算法。我附上了我教科书中的算法图像。伪代码显示输入是一个无向图，但算法对于有向图有什么不同吗？我用有向图的输入查找了算法，但没有发现任何差异。

我编写了一个谓词find_path(S,T,Visited,Path)，它可以搜索我的无向图并找到从节点 S 到节点 T 的路径，然后返回边值列表（边值是边事实中的第三个值）。我写的谓词似乎工作正常，但是它只返回搜索结果的布尔值，没有边缘值列表。有人可以就我如何做到这一点提出建议吗？提前致谢。

这是我的代码和我正在使用的无向图的图像

如果我有一个未加权的有向多重图，其中，对于从节点 1 到节点 2 的每条边，都有一条从节点 2 到节点 1 的边，这是否意味着可以将其视为无向图？

为了给出背景，我正在模拟一个地铁系统，在每个连接的车站之间，有一条火车可以去往任何一种方式。

PS对不起标题。想不出一个简洁的表达方式。

在已执行 DFS 的无向图中（为了生成 DFS 树并将每条边分类为树边或后边），图中是否存在仅由后边组成的循环，即没有树边缘？

我有一大组代表一组图的顶点/节点。请注意，在这个完整的集合中可能有许多独立的图。目标是找到所有这些图中的最小顶点数，这些顶点对应于那些选定顶点捕获的所有边上的最大权重总和。我在熊猫中有邻接矩阵，我正在使用networkx。

下面是一个包含三列的示例数据框，其中 Number_Of_Trips 是权重。我可以提供 node = 10*trips 的权重，以便将两个指标合并在一起。即最大化旅行次数 - 10*NumberOfNodes

所以我正在尝试使用java在无向图中查找路径。我觉得我可能走在正确的轨道上，非常接近获得它，但是，我一直遇到路障并收到错误提示。我正在使用链表来存储边和顶点。

Graph2.java:17：错误：通用数组创建 adj = new LinkedList[v];

这是我的代码

您好我正在尝试弄清楚如何计算加权无向图中两个节点之间的平均距离。此外，这个图是一棵树，所以它有 V - 1 条边。

我考虑过使用 Floyd Warshall 计算所有最短路径，然后计算平均值。但这将是 O(E^3) 时间复杂度。这真的是不够的。

我也一直在考虑使用动态编程来解决它，但我真的不明白如何......谁能给我一些建议吗？我不想要一个直接的答案，只是一些提示，以便我可以继续思考:)

我正在尝试实现单词阶梯问题，我必须尽可能以最短的路径将一个单词转换为另一个单词。显然我们可以使用广度优先搜索（BFS）来解决它，但在此之前我们必须先绘制图表。我有实现了桶的概念，如果某些单词与桶类型匹配，则它们属于桶。但我的图表没有正确实现。

给定的单词列表是 ["CAT", "BAT", "COT", "COG", "COW", "RAT", "BUT", "CUT", "DOG", "WED"]

所以对于每个单词我可以创建一个桶。例如对于单词'CAT'，我可以有三个桶_AT，C_T，CA_。类似地，我可以为其余的单词创建存储桶，并且与存储桶类型匹配的单词将属于这些存储桶。

用手实现应该给我这样的图表

由于图形是无向的，因此对于顶点 COG，其相邻顶点应该是 DOG、COW、COT（关系双向工作），但相反，我得到 COG 与任何事物无关。下面是我的代码

我得到的结果是

我希望结果是这样的

我究竟做错了什么？

我正在尝试实现单词阶梯问题，我必须尽可能以最短的路径将一个单词转换为另一个单词。显然我们可以使用广度优先搜索（BFS）来解决它，但在此之前我们必须先绘制图表。我有实现了桶的概念，如果某些单词与桶类型匹配，则它们属于桶。但我的图表没有正确实现。

给定的单词列表是 ["CAT", "BAT", "COT", "COG", "COW", "RAT", "BUT", "CUT", "DOG", "WED"]

所以对于每个单词我可以创建一个桶。例如对于单词'CAT'，我可以有三个桶_AT，C_T，CA_。类似地，我可以为其余的单词创建存储桶，并且与存储桶类型匹配的单词将属于这些存储桶。

我用图形表达问题的代码工作正常，我得到这样的图形（理论上）

现在我需要找到将“CAT”转换为“DOG”的最短操作数。所以我使用 BFS 的修改方法来实现它。当我制作自己的示例图时它工作正常。例如

代码工作正常，我得到了正确的结果。但是如果我有一个巨大的单词列表，比如 1500，那么键入并创建这么长的字典是不可行的。所以我创建了一个函数，从列表中获取这些单词，实现我在上面讨论过的技术并为我创建了图表，直到这里都可以正常工作。但是当我尝试获得两个单词之间的最短距离时，出现以下错误

这是我下面的代码

要检查每个顶点的相邻顶点，我们可以这样做

得到的输出如下正确地描述了上面的图表。

那会出什么问题呢？

我有一个无向图，我想在其中找到所有可能的路径，连接给定集合的所有节点。这是一个NP问题吗？有没有一种算法可以做到这一点，或者有一个很好的方法来完成它？我不关心每条路径接触集合中节点的顺序，我只需要它通过它们中的每一个。