全部函数通过杭电 1142，1162，1198，1213等题目测试。
#include<iostream> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<stdio.h> #include<stdlib.h> using namespace std; /* //函数集合声明下，方便查看 void Dijkstra(const denseGraph& dg, int s); void spfa(const denseGraph& dg, int s); weightType prim(const denseGraph& dg, int s); void makeSet(int x); int findSet(int x); void unionSet(int x, int y); weightType kruskal(const denseGraph& dg); */ //稀疏图，邻接链表表示 #define N 1000 //表示顶点数最大值 #define NOEDGE 1000000 //表示无边，用于距离类求解中 typedef double weightType; //表示带边权的类型 struct edge{ int v, w; weightType val; edge(int v = -1, int w = -1, weightType val = NOEDGE) :v(v), w(w), val(val){} }; struct nodeGraph{ int v; weightType val; nodeGraph* next; nodeGraph(int v = -1, weightType val = NOEDGE, nodeGraph* next = NULL) :v(v), val(val), next(next){} }; typedef nodeGraph* link; struct sparseGraph{ int Vcnt, Ecnt; //顶点数，边数 bool dg; //有向图 ? vector<link> adj; //邻接链表 sparseGraph(int v, bool dg = false) :adj(v), Vcnt(v), Ecnt(0), dg(dg){ adj.assign(v, NULL); } void insert(edge e){ int v = e.v, w = e.w; weightType val = e.val; adj[v] = new nodeGraph(w, val, adj[v]); if (!dg) adj[w] = new nodeGraph(v, val, adj[w]); ++Ecnt; } void show(){ printf("Vcnt = %d, Ecnt = %d, Directed : %d ", Vcnt, Ecnt, dg); link p = NULL; for (int i = 0; i < Vcnt; ++i){ p = adj[i]; printf("%d: ", i); while (p){ cout << p->v << ','; cout << p->val; p = p->next; if (p) printf(" "); } printf(" "); } } }; //用于Dijkstra,prim中的队列优化，可选 struct keyValue{ int key, value; keyValue(int key, int value) :key(key), value(value){} }; template<class T> struct myGreater{ bool operator() (const T& x, const T& y) const{ return x.key > y.key; } }; //Dijkstra算法 weightType dDijkstra[N]; //存放所有顶点到 s 的最短路径距离 int pDijkstra[N]; //pDijkstra[i],路径存在时，存放节点 i 的前驱，不存在时，-1 void Dijkstra(const sparseGraph &sg, int s) { bool visit[N]; for (int i = 0; i < sg.Vcnt; ++i){ visit[i] = false; dDijkstra[i] = NOEDGE; pDijkstra[i] = -1; } link p = sg.adj[s]; while (p){ dDijkstra[p->v] = p->val; pDijkstra[p->v] = s; p = p->next; } visit[s] = true; dDijkstra[s] = 0; for (int i = 0; i < sg.Vcnt - 1; ++i){ int min = NOEDGE; int v = 0; /*优先队列代替 priority_queue < keyValue, vector<keyValue>, myGreater<keyValue> > qq; for (int j = 0; j < sg.Vcnt; ++j) if (!visit[j]) qq.push(keyValue(dDijkstra[j], j)); keyValue u = qq.top(); v = u.value; min = dDijkstra[v]; */ for (int j = 0; j < sg.Vcnt; ++j){ if (!visit[j] && dDijkstra[j] < min){ v = j; min = dDijkstra[j]; } } visit[v] = true; p = sg.adj[v]; while (p){ if (!visit[p->v] && p->val + min < dDijkstra[p->v]){ dDijkstra[p->v] = p->val + min; pDijkstra[p->v] = v; } p = p->next; } } } //最短路径 SPFA算法 weightType dSpfa[N]; int pSpfa[N]; void spfa(const sparseGraph& sg, int s) { bool visit[N]; for (int i = 0; i < sg.Vcnt; ++i){ visit[i] = false; dSpfa[i] = NOEDGE; pSpfa[i] = -1; } dSpfa[s] = 0; int u; link p = NULL; queue<int> q; q.push(s); while (!q.empty()){ u = q.front(); q.pop(); p = sg.adj[u]; while (p){ int v = p->v; if (dSpfa[u] + p->val < dSpfa[v]){ dSpfa[v] = dSpfa[u] + p->val; pSpfa[v] = u; if (!visit[v]) q.push(v); } p = p->next; } } } //最小生成树 prim weightType dPrim[N]; //存放所有顶点到 s 的最短路径距离 weightType prim(const sparseGraph &sg, int s) { weightType sum = 0; bool visit[N]; for (int i = 0; i < sg.Vcnt; ++i){ visit[i] = false; dPrim[i] = NOEDGE; } link p = sg.adj[s]; while (p){ dPrim[p->v] = p->val; p = p->next; } visit[s] = true; dPrim[s] = 0; for (int i = 0; i < sg.Vcnt - 1; ++i){ weightType min = NOEDGE; int v = 0; for (int j = 0; j < sg.Vcnt; ++j){ if (!visit[j] && dPrim[j] < min){ v = j; min = dPrim[j]; } } sum += min; visit[v] = true; p = sg.adj[v]; while (p){ if (!visit[p->v] && p->val < dPrim[p->v]){ dPrim[p->v] = p->val; } p = p->next; } } return sum; } //并查集实现，点集[0,1,2,3,4,...,n-1] int parentSet[N]; int rankSet[N]; void makeSet(int x) { parentSet[x] = x; rankSet[x] = 0; } void linkSet(int x, int y) { if (rankSet[x] > rankSet[y]) parentSet[y] = x; else { parentSet[x] = y; if (rankSet[x] == rankSet[y]) ++rankSet[y]; } } int findSet(int x) { vector<int> v; while (parentSet[x] != x){ v.push_back(x); x = parentSet[x]; } for (int i = 0; i < v.size(); ++i) parentSet[v[i]] = x; return x; } void unionSet(int x, int y) { linkSet(findSet(x), findSet(y)); } //最小生成树 kruskal bool kruskalComp(const edge &a, const edge &b){ return a.val < b.val; } weightType kruskal(const sparseGraph &sg) { weightType sum = 0; vector<edge> ve; //取图的所有边，并排序 edge e; link p = NULL; for (int i = 0; i < sg.Vcnt; ++i){ p = sg.adj[i]; e.v = i; while (p){ e.w = p->v; e.val = p->val; ve.push_back(e); p = p->next; } } sort(ve.begin(), ve.end(), kruskalComp); for (int i = 0; i < sg.Vcnt; ++i) makeSet(i); for (int i = 0; i < ve.size(); ++i){ e = ve[i]; int x = findSet(e.v); int y = findSet(e.w); if (x != y){ unionSet(x, y); sum += e.val; } } return sum; } /*测试数据 5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 */ int main() { int v, w, val, n, m; cin >> n >> m; sparseGraph sg(n,true); while (m--){ cin >> v >> w >> val; sg.insert(edge(v-1, w-1, val)); } sg.show(); cout << endl; for (int i = 0; i < sg.Vcnt; ++i){ spfa(sg, i); Dijkstra(sg, i); for (int i = 0; i < sg.Vcnt; ++i) cout << dSpfa[i] << ' '; cout << endl; for (int i = 0; i < sg.Vcnt; ++i) cout << dDijkstra[i] << ' '; cout << endl; for (int i = 0; i < sg.Vcnt; ++i) cout << pSpfa[i] << ' '; cout << endl; for (int i = 0; i < sg.Vcnt; ++i) cout << pDijkstra[i] << ' '; cout << endl << endl; } for (int i = 0; i < sg.Vcnt; ++i) cout << prim(sg, i) << endl; cout << kruskal(sg) << endl; }