- Prim算法
感觉Prim算法找最小生成树的过程像是一个dp的过程，从随便一个点开始，每次都是找到局部最优解，最后就可以找全整个最小生成树。
const int MAXN = 1000;const int LIM = 0x3f3f3f3f;struct MGraph{ int vexs[MAXN];//顶点表 int arc[MAXN][MAXN];//邻接矩阵 int numEdges, numVertexes;//边，点的数量};void MiniSpanTree(MGraph G){ int adjvex[MAXN]; int lowcost[MAXN];//储存每一次延伸后的最小权值 adjvex[0] = 0; lowcost[MAXN] = 0;//置0代表该点已经加入最小生成树，这里就把0这个点作为起始点 for (int i = 1; i < G.numVertexes; i++)//初始化第一个点延伸出去的边信息 { lowcost[i] = G.arc[0][i]; adjvex[i] = 0; } for (int i = 1; i < G.numVertexes; i++) { int mmin = LIM; int k; for (int j = 1; j < G.numVertexes; j++)//找到lowcost中的最小边 { if (lowcost[j] != 0 && mmin > lowcost[j]) { mmin = lowcost[j]; k = j; } } cout << '(' << adjvex[k] << '，' << k << ')' << endl;//打印最小生成树的边 lowcost[k] = 0;//把该顶点置0 for (int j = 1; j < G.numVertexes; j++)//把下一个顶点的边加入lowcost { if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) { lowcost[j] = G.arc[k][j];//更新lowcost adjvex[j] = k;//找到该点的上一个顶点 } } }} - Kruskal算法
这个算法就是一个划分集合的过程，运用了并查集的思想，并且保证集合里面不会形成环路。因为已经将边集数组提前进行从小到大的排序，所以每次加进集合的都可以认为是剩下的最优解。
#include#include using namespace std;const int MAXN = 1000;struct Edge//边集数组{ int begin; int end; int weight;};struct Graph//图{ Edge edges[MAXN]; int numVertexes,numEdges;};bool cmp(Edge a,Edge b)//定义比较函数，从小到大排序{ return a.weight