问题标签 [undirected-graph]

我知道对于要连接的具有 n 个顶点的无向图，它必须具有 n - 1 条边。但是，我的问题是它可以始终连接的最小边数是多少。例如，是否必须始终连接具有 n 个顶点和 n + 2 条边的图？如果不是，它必须有多少边才能始终连接？

我生成了这段代码来测试一个随机无向图 100 次，并随机生成图的节点和权重。我的问题是，当我尝试通过调用最小距离来存储最短路径时出现问题，当我返回列表的大小时，它始终为 1。出了什么问题？

我需要在无向图中找到两个节点之间的最小距离，这里有一些细节

• 该图是无向且巨大的（节点数约为 100,000）
• 该图是稀疏的，边数小于节点数
• 我对实际路径不感兴趣，只对距离感兴趣。

我应该为 a) 空间效率 b) 时间效率使用什么表示和算法？

编辑：如果重要的话，

• 权重都是非零正整数。
• 没有节点连接到自身。
• 两个相邻节点之间只有一条边

我有这个迷宫，它表示为无向图。这是它的样子：

在此图中，使用深度优先搜索，它向我展示了从起始节点到目标节点的解决方案。我作为起始节点的输入是0，我的目标节点是1. 我作为目标路径得到的解决方案是，0-3-11-7-5-4-1但如果你再次分析，还有另一个解决方案是0-3-11-6-7-5-4-1. 我在这里的目的不是展示最佳解决方案，而是展示它们有多少个解决方案，然后再分析最佳解决方案。

我遇到的困难是我无法打印多个解决方案。它只打印0-3-11-7-5-4-1任何其他内容，有时这0-3-11-6-7-5-4-1是因为我期望有两个要打印。这是我到目前为止所做的代码：

迷宫图源代码：

请向我详细解释为什么会发生这种情况，并就如何改进这一点给我建议/建议。如果可以，请检查我的代码质量，否则不检查也没关系。无论如何提前谢谢。

如何从这样的图中删除所有循环？所有边长都是一，所有边要么是垂直的，要么是水平的。该图已连接。

我想计算为了使图形不包含循环而必须删除的最少边数。

如果您包含示例代码（最好是 C++、C 或 Java），那将非常有帮助。

更新：显然我必须找到顶点和边的数量。我遇到的问题给出了一组指令，例如（下、左、上、下、左、左、上、下）。您从坐标平面中的 (0, 0) 开始，沿指定方向移动一个单位。这将创建一个图表。我如何从这组指令中获得顶点和边的数量？

我需要在一个文本文件中编写一个图表，其中文件的每一行都由一个节点和其所有邻居组成。它基本上是邻接列表，以及函数write_adjlist应该做什么。不幸的是，事实并非如此，因为边缘没有被复制。在维基百科的例子中，邻接列表是：

a 与 b、c 相邻

b 与 a, c 相邻

c 与 a, b 相邻

我们可以看到所有边缘都出现了两次（第(a,b)1 行和第 2 行中的边缘(b,c)，第 2 和第 3 行中的边缘......）。

但是现在如果我使用下面的代码来生成一个小世界网络：

它给了我：

我想在哪里

你知道我该怎么做才能得到我想要的输出吗？

I created a program that solves a maze that reads a text file input. I managed to solve it using Depth-first Search and the result was fine on small mazes like this:

Everything was fine solving small to medium mazes but when the maze becomes larger, it gives me an ArrayIndexOutOfBoundsException error (see below).

My program should read automatically how many nodes are in the test2.txt (this is the large maze file) file but this error happens. The code looks like this:

MazeGraph.java

In MazeGraph.java, the getNodeSize method returns an integer that is used for the constructor's parameter. To make it work, I have to take that getNodeSize method out in the constructor's parameter and instead put some larger value there like 300 for example. In stack trace, it says the problem is in the addArc method. I am trying to figure out on how to solve this problem if it works already in other mazes so that it also reads in large mazes automatically. Please, I would be grateful if someone can solve this.

This is the large file.

我有许多差异的数据。表中的一组无向图（如相邻列表关系，一个节点连接到所有节点），我需要对所有单独的无向图进行分组。

例如：特定无向图的所有节点都将在一个组中，组名将是最小值。的节点。

现在，我进行了 4,5 次自联接，然后在该查询之上对其进行分区以获得所需的输出。但是进行自我加入 4 5 次会产生性能问题。

因此，需要一些递归 sql、存储过程或其他一些逻辑来为所有级别执行相同的操作。输入数据和所需输出将类似于此链接寻找一些建议。

我有一个无向图，我需要使用深度优先搜索来遍历它。

下面的excel图表在标记列中显示了遍历后每个节点都被标记了，edgeTo列显示了是哪个节点把我们带到了那个节点。例如，我们从节点 5 到节点 1，我们从节点 7 到节点 2，等等。

我的问题是节点 6 和 8，因为它们与主图分开，我该如何正确遍历它？我的猜测是我从 6 开始到 8，但由于那时已经访问了 6，所以我不会从 8 回到 6。因此第 6 行在 edgeTo 列中留空。

我对么？我的图表正确吗？

我正在尝试创建一个 C 程序，该程序读取一个输入文件，该文件包含一组表示无向图边缘的点。我试图将每个顶点结构存储在一个使用指针实现的数组中，但是在 load_file 运行后，该数组并不包含所有顶点，它只包含第一个顶点。我也不确定如何实现 DFS 来查找每个顶点和顶点 1 之间的边数。目前底部函数是发生此逻辑的地方，但我不确定该怎么做。