图算法总结

最小生成树问题 方法一：Kruskal

核心思想：从边入手找顶点（贪心思想），每次从图中都找最短边

时间复杂度：|E|log|E|（适用于稀疏图）

#includeusing namespace std;#define maxWeight 999//表示正无穷 #define maxn 105//表示最大边数 #define Maxsize 100//表示最大顶点数int n;//边的个数 //并查集操作int parent[Maxsize];//存储根节点 int CollapsingFind(int i){for(int r = i;parent[r]>=0;r = parent[r]);//找到树根//压缩树高while(i!=r){int s = parent[i];parent[i] = r;i = s;} return r;}void WeightedUnion(int i,int j){int ri = Find(i), rj = Find(j);if(ri != rj){int temp = parent[i]+parent[j];//记录两棵树的节点数 if(parent[j]//如果有比之前更短的，则选择 dis[k] = tmp;}}}}int main(){int num = 0;while(scanf("%d",&n) && n){for(int i=1;i "//e[edgesum].start = 0;//e[edgesum].end = i;//e[edgesum].w = 0;//edgesum++;//}for (int i = 1; i > a >> b;//di-dj a >> b >> c;e[edgesum].start = b;e[edgesum].end = a;e[edgesum].w = t[a] + c;edgesum++;}BellmanFord();int max = -999, min = 999;int maxi, mini;for (int i = 1; i max) {max = d[i];maxi = i;}}cout m) {edgesum = 0;for (int i = 1; i > c[i];//s[i]=0 --> s[i-1] a >> b >> d;//s[b]-s[a-1]>=c --> s[a-1]