标签: graph-algorithm

拓扑排序可以使用 DFS（边缘反转）和队列来完成。BFS 也可以使用队列来完成。使用队列进行 BFS 时元素的存储和检索方式与使用队列进行拓扑排序时的元素存储和检索方式之间是否存在任何关系。澄清会有所帮助。谢谢。

邻接矩阵表示任意树中节点之间的连接。

这是一个呈现无向图的邻接矩阵实例：

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

该矩阵表示一个图，其中节点 1 和 2 相连，1 和 3 相连，2 和 3 相连。

如何使用这种矩阵在这样的图中暴力破解所有可能路径的组合？我的意思是只选择节点 1 是一个单独的组合。那么，比如说，1-2 是一个单独的组合。1-2-3; 3-1-2。但是 1-2-3-1 是不可能的，因为重复选择了同一个节点。

那么如何使用这些规则对所有组合进行暴力破解呢？

我更喜欢 C#、C++ 或 Java 语言示例）

我有一个有向无环图，每个顶点的权重 >= 0。有一个顶点是图的“开始”，另一个顶点是图的“结束”。这个想法是找到从起点到终点的路径，其中顶点的权重之和更大。例如，我有下一张图：

I(0) -> V1(3) -> F(0)
I(0) -> V1(3) -> V2(1) -> F(0)
I(0) -> V3(0.5) -> V2(1) -> F(0)

成本最高的路径是 I(0) -> V1(3) -> V2(1) -> F(0)，其成本为 4。

现在，我正在使用 BFS 枚举从 I 到 F 的每条路径，如上例所示，然后，我选择总和最大的那个。恐怕这种方法真的很幼稚。

有没有更好的算法来做到这一点？这个问题可以简化为另一个问题吗？

所以我最近实现了一个非递归版本的DFS。事实证明，一旦节点被压入堆栈或弹出，我就可以将它们标记为“已访问”。我正在解决的问题特别指出，当将其推入堆栈时将其标记为“已访问”。这两个版本都是某种 DFS 吗？或者是一个是DFS，另一个不是。欢迎任何建议。

我认为如果我采用第二种方式，它将模仿递归 dfs。但为什么另一种有效呢？

递归dfs（请忽略这一点）

dfsRec(node)
{
    visitedArray[node]=1;

    for all neighbours of node
        if they aren't visited
            dfsRec(neighbour);
}

dfs(startNode)
{
    visitedArray;
    dfsRec(startNode);  
}

我想在 CFG 中找到所有可能的线性独立路径。根据我对算法的有限了解，CFG 本质上是一个包含循环的有向图。圈复杂度的公式很简单。我想知道是否有办法获得从开始到结束节点的所有线性独立路径（由圈复杂度给出）

谢谢！

我想出了以下问题,我不知道解决方案,也无法找到"查找"术语进一步调查.

假设我们有N个有序节点(n_1,n_2 ...... n_N),每个节点之间的固定距离为1.所以dist(n_1,n_N)= N-1.现在我们被允许连接任意两个节点,从而有效地将它们的距离减少到1.假设我们可以有这样的连接.

问题是:我们如何选择连接哪些节点以最小化任何两个节点之间的总距离？

这个问题是一个已经充分研究过的问题的已知变体吗？是否存在有效的解决方案(或者我们只希望最小化任意两个节点之间的最大距离的变体)

谢谢

我们假设图由具有值和无向边的节点组成。
我想将图划分为几个组，我选择这些组来满足每个分区组具有与节点具有相似或相同的值总和的条件。

您能否推荐哪些算法可用于在满足我提到的条件的情况下对图进行分区？
如果您附上用 python 或 java 实现的算法，我将更加感激。


（为了方便您理解，我们附上了图片和数据类型。）

<Data information>
[node_id]: n_1, n_2, n_3 ,, etc
[node_value]: 10, 5, 20,, etc
[node_adjacency_data] : Please refer to the attached picture.
[node_latitude]: 37.25201, 37.25211, 37.25219,, etc
[node_longitude]: 127.10195, 127.11321, 127.11377,, etc 

使用数组的 Dijkstra 算法的时间复杂度为 O(V^2)，如果实现优先级队列，我们​​可以进一步将复杂度提高到 O(E log V)。但它的空间复杂度又如何呢？两种情况都是 O(V) 吗？

我正在尝试解决这个问题：https : //cses.fi/problemset/task/1160/

基本上，这个问题要求编码器Q在后继N节点图中处理最短路径查询，其中Q和N的数字高达 100000。我已经被这个问题困住了好几天，我的想法都不够快，可以通过所有测试用例。

我的第一个想法是使用某种全对最短路径算法，例如 Floyd-Warshall 算法。然而，这种算法将在运行O(N^3 + Q)时间，这是方法太慢了这个问题。

我的第二个想法是使用广度优先搜索单独处理每个查询。这个算法会O(Q*N)及时运行，这比我的第一个想法快，但对于问题来说仍然太慢。

我尝试在网上搜索解决方案，但没有找到任何解释。有人可以指出我正确的方向吗？

给定一个称重，连接并有向图G=(V,E)具有n顶点和m边缘，以及给定的一个预先计算的最短路径的距离的矩阵S，其中S是n*n S(i,j)表示从顶点的最短路径的重量i至顶点j。

我们只知道一条边的权重(u, v)发生了变化（增加或减少）。

对于两个特定的顶点s，t 我们想要更新这两个顶点之间的最短路径长度。

这可以在 O(1).

这怎么可能？这个答案的诀窍是什么？