问题标签 [graph-algorithm]

我知道Prim 的算法，也知道它的实现，但我总是跳过我现在想问的部分。有人写道，Prim 的斐波那契堆算法实现是O(E + V log(V))，我的问题是：

• 简而言之，斐波那契堆是什么？
• 它是如何实施的？和
• 如何用斐波那契堆实现 Prim 算法？

我的图表是有向的并且非常大。图中的顶点代表城镇，边代表从城镇到城镇的公共汽车旅行路线。目标是找到从一个顶点到另一个顶点的路径。该算法考虑到公交车之间的换乘时间是非常重要的。

我会使用 Dijkstra 的算法，但它来自整个图表并找到一种方法。我需要找到一些从顶点到顶点的“最佳”方式。“最好的”是指最短的转会时间，但这不是最重要的一点。

给定一个具有顶点权重 W(V) 的无向循环平面图 G(V,E)、一个嵌入 E(G) 和两个节点 s 和 t 的固定平面，我需要找到 G 的一个分区，将其划分为两个连通分量S(G) 和 T(G)，其中 s 在 S(G) 中，t 在 T(G) 中。顶点 s 和 t 都属于嵌入 E(G) 中的外部面。

我希望分区能够很好地平衡 - 它们应该具有几乎相等的顶点权重之和。

请问有什么好的算法的想法吗？

我正在研究图形搜索算法（为了这个问题，让我们只在 DFS、BreadthFS、ID 上限制算法）。

所有这些算法都可以实现为前向搜索（从开始节点到结束节点）或向后搜索（从结束节点到开始节点）。

我的问题是，什么时候后向搜索会比前向搜索更好？对此有一般规则吗？

尝试为将两个图作为输入的算法提出一个伪代码（在乳胶中） - 比较图中的每个节点 - （我将填写比较函数），但如果它们是来自一个图的节点，则返回 0等于另一个图中的节点，否则返回 1。图中的节点可以是另一个图。所以检查是递归的。

我创建了一个程序，该程序使用 java awt 在 JFrame 中构建和绘制嵌套循环图（具有无向边）。

问题是，如果节点的位置没有明确指定，或者是随机创建的，那么图形会变得非常混乱，边会交叉，顶点会发生碰撞。

我想实现一种重新定位算法，以更均匀和更干净的方式更好地分布节点。

有人能帮我吗？

这是 Vazirani 的算法书中的一个问题

这个问题的输入是一棵树 T，边上有整数权重。权重可以是负数、零或正数。给出一个线性时间算法来找到 T 中最短的简单路径。路径的长度是路径中边的权重之和。如果没有重复的顶点，则路径是简单的。请注意，路径的端点不受约束。

提示：这与在树中寻找最大独立集的问题非常相似。

我怎样才能在线性时间内解决这个问题？

这是我的算法，但我想知道它是否是线性时间，因为它与深度优先没有什么不同：

1. 遍历树（深度优先）
2. 保留索引（节点）
3. 添加值
4. 做（1）直到树的尽头
5. 比较总和并打印路径和总和

这个问题与这个主题相似，但没有确定的答案。

我有一个算法问题，我在其中导出了许多状态之间的传递矩阵。下一步是取幂，但它非常大，所以我需要对它做一些归约。具体来说，它包含很多对称性。下面是一些关于通过简单观察可以消除多少节点的示例。

我的问题是是否有一种算法可以有效地消除有向图中的对称性，类似于我在下面手动完成的方式。

在所有情况下，初始向量对于所有节点都具有相同的值。

在第一个示例中，我们看到b、和都从彼此接收值。因此它们将始终包含相同的值，我们可以合并它们。cdea

在这个例子中，我们很快发现，从、和的角度来看，该图是相同a的。同样对于它们各自的侧节点，它附加到哪个内部节点并不重要。因此，我们可以将图减少到只有两个状态。bcd

更新：有些人很合理，不太确定“状态转移矩阵”是什么意思。这里的想法是，您可以将一个组合问题拆分为多个状态类型，以便n在您的循环中为每个状态类型。然后矩阵会告诉你如何从n-1到n。

通常你只对你的一个状态的值感兴趣，但你也需要计算其他状态，所以你总是可以进入下一个级别。然而，在某些情况下，多个状态是对称的，这意味着它们将始终具有相同的值。显然计算所有这些是相当浪费的，所以我们想减少图，直到所有节点都是“唯一的”。

下面是示例 1 中简化图的传递矩阵示例。

对论文的任何建议或参考表示赞赏。

我正在尝试编写以下函数：给定一个全为零但对象外边界（等于1）的矩阵，我想生成一个边界链代码。孔对象不在矩阵中，只是它的外边界。

*在示例图片中 - 所有矩阵单元为 0，但蓝色单元格为 1。

非常感谢任何帮助！

考虑 A* 算法。

在 Google 中可以找到一个很好的伪代码：

好吧，我不明白一件事：考虑一下图中的情况：

A* 如何能够从 a->b->c 变为 a->d... ??? 好吧，我的意思是，A* 从一个节点开始并通过节点导航。在某一点，一个节点有多个邻居，嗯，A* 能够遵循由邻居生成的路径，但在某一点它能够切换......并从前一个开始返回它的步骤节点并走另一条路，即使废弃的路径没有穿过那条路......

在代码中，启用此环境的条件是什么？