(1)最短路径树和最小生成树的区别： 最短路径树：源点到其它所有节点的最短路径构成的树。实际上是一个（DAG） 最小生成树：网络中任意两个顶点可达，且边集总长度最小，不能保证源点到其它点距离最小。 （2）求最短路径树的数量：乘法原理（记录每个节点的父节点可取数cnt[i]表示...

 度受限的最小生成树： 给定一张N个点,M个边的无向图,求出无向图的一颗最小生成树,但是我们要求一号节点的入度不可以超过给定的整数S 也就是一个最小生成树,要求它的一号节点,最多只能和S个节点相连. ————&mdas...

dfs 应用：求最小生成树某一结点到其它各节点的路径上的最大边 #include<iostream> using namespace std; const int N = 100; int n, m; bool vis[N][N]; int g[N][N];...

并查集 将边升序排列，两个连通图之间增加(p*q-1)条边，最小增加的权值为（w+1）。 #include<iostream> #include<algorithm> using namespace std; const int N = 6010;...

https://blog.csdn.net/sugarbliss/article/details/86551050