给定具有权重函数G(V,E)的无向和连通图w:E->R，边e(u,v)属于E。哪种算法在线性运行时复杂度下运行，可以确保是否存在包含边e的最小生成树？
从u开始执行深度优先搜索，并忽略权重等于给定边的权重或更重的任何边。如果DFS在不访问v的情况下完成，则意味着没有循环，其中给定的边是最重的边，因此给定的边包含在某个最小生成树中。
这是要求您两次实施Prim's Minimum Spanning Tree。
第一次正常运行算法。记下mst的重量。
第二次，而不是像普里姆算法通常那样从空树开始，而是从树上已经存在的节点u和v开始，这与具有边e（u，v）相同。然后继续构建mst。
最后，如果第二个mst与第一个mst的权重相同，则边缘e（u，v）可以位于一个mst中。如果不是，则提示音更轻。
顺便说一下，2 * O（n）仍然是O（n）