小编Tom*_*God的帖子

我正在寻找一种算法(或任何其他方式)来确定给定的加权图是否在O(ElogV)中具有唯一的MST(最小生成树)？

我对权重没有任何了解(例如权重(e1)!=权重(e2)),如果该图只有一个唯一的MST,算法只返回True,否则返回False.

我开始使用Kruskal的算法,并检查是否find-set(u)== find-set(v)所以在MST中有一个圆圈,但这种方式并没有涵盖我想的所有场景:(

非常感谢!托梅尔.

给定一个无向图(未加权)和两个顶点u和v,如何找到u和v之间的路径,其长度可被3整除？

注意,路径不一定是简单的路径.

我想到了DFS的变体和存储路径(以及回溯)的堆栈,但是不能完全理解如何跟踪非简单路径.

时间复杂度应为O(V + E),因此我预计它必须是BFS或DFS的变体.

给定具有正权重的无向图,有两种边:锁定边和未锁定边.确定给定边缘是锁定边缘还是解锁边缘需要O(1).

1. 对于给定的两个顶点s,t和正数k = O(1),如何找到s和t之间最短路径,其中包含最多 k个锁定边缘？

2. 对于给定的两个顶点s,t和一个正数k = O(1),如何找到包含正好k个锁定边的s和t之间的最短路径？

我不知道我怎么能在这个图运行Dijkstra算法找出给定顶点之间的最短路径,以及如何改造无向图,为指导之一.