最小生成树的性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树）
普里姆算法（Prim算法)
思路：以点为目标构建最小生成树
1.将初始点顶点u加入U中，初始化集合V-U中各顶点到初始顶点u的权值；
2.根据最小生成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最小。循环n-1次如下操作：
（1）从数组lowcost[k]中找到vk到集合U的最小权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标
(2)打印此边，并将vk加入U中。
（3）通过查找邻接矩阵Vk行的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进行比较，若更小则更新lowcost，并将k存入arjvex数组中
#include<bits/stdc++.h>
using namespace std;
#define MAXVEX 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G) {
int m, n, w; //vm-vn的权重w
scanf("%d %d", &G->numVertexes, &G->numEdges);
for(int i = 0; i < G->numVertexes; i++) {
getchar();
scanf("%c", &G->vexs[i]);
}
for(int i = 0; i < G->numVertexes; i++) {
for(int j = 0; j < G->numVertexes; j++) {
if(i == j) G->arc[i][j] = 0;
else G->arc[i][j] = INF;
}
}
for(int k = 0; k < G->numEdges; k++) {
scanf("%d %d %d", &m, &n, &w);
G->arc[m][n] = w;
G->arc[n][m] = G->arc[m][n];
}
}
void MiniSpanTree_Prim(MGraph G) {
int min, j, k;
int arjvex[MAXVEX]; //最小边在 U集合中的那个顶点的下标
int lowcost[MAXVEX]; // 最小边上的权值
//初始化,从点 V0开始找最小生成树T
arjvex[0] = 0; //arjvex[i] = j表示 V-U中集合中的 Vi点的最小边在U集合中的点为 Vj
lowcost[0] = 0; //lowcost[i] = 0表示将点Vi纳入集合 U ，lowcost[i] = w表示 V-U中 Vi点到 U的最小权值
for(int i = 1; i < G.numVertexes; i++) {
lowcost[i] = G.arc[0][i];
arjvex[i] = 0;
}
//根据最小生成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最小
for(int i = 1; i < G.numVertexes; i++) {
min = INF, j = 1, k = 0;
//寻找 V-U到 U的最小权值min
for(j; j < G.numVertexes; j++) {
// lowcost[j] != 0保证顶点在 V-U中，用k记录此时的最小权值边在 V-U中顶点的下标
if(lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
}
printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);
lowcost[k] = 0; //表示将Vk纳入 U
//查找邻接矩阵Vk行的各个权值，与lowcost的对应值进行比较，若更小则更新lowcost，并将k存入arjvex数组中
for(int i = 1; i < G.numVertexes; i++) {
if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {
lowcost[i] = G.arc[k][i];
arjvex[i] = k;
}
}
}
int main() {
MGraph *G = (MGraph *)malloc(sizeof(MGraph));
CreateMGraph(G);
MiniSpanTree_Prim(*G);
}
/*
input:
4 5
a
b
c
d
0 1 2
0 2 2
0 3 7
1 2 4
2 3 8
output:
V[0]-V[1] weight = 2
V[0]-V[2] weight = 2
V[0]-V[3] weight = 7
最小总权值: 11
*/
时间复杂度O(n^2)
克鲁斯卡尔算法（Kruskal算法）
思路：以边为目标进行构建最小生成树
在边集中依次寻找最小权值边，若构建是不形成环路（利用parent数组记录各点的连通分量），则将其添加到最小生成树中。
判断是否形成环路思路：
初始化parent数组为各个顶点的下标，以此表示每个顶点为不同的连通分量，寻找最小权值边时，判断该边起点和终点是否属于同一连通分量，如果不属于则将该边加入最小生成树中，并将该边的起点和终点的连通分量更改为已形成的最小生成树起始点的连通分量。
#include<bits/stdc++.h>
using namespace std;
#define MAXVEX 100
#define MAXEDGE 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
//图的邻接矩阵存储结构的定义
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
//边集数组Edge结构的定义
typedef struct {
int begin;
int end;
int weight;
}Edge;
bool vis[100][100];
void CreateMGraph(MGraph *G) {
int m, n, w; //vm-vn的权重w
scanf("%d %d", &G->numVertexes, &G->numEdges);
for(int i = 0; i < G->numVertexes; i++) {
getchar();
scanf("%c", &G->vexs[i]);
}
for(int i = 0; i < G->numVertexes; i++) {
for(int j = 0; j < G->numVertexes; j++) {
if(i == j) G->arc[i][j] = 0;
else G->arc[i][j] = INF;
}
}
for(int k = 0; k < G->numEdges; k++) {
scanf("%d %d %d", &m, &n, &w);
G->arc[m][n] = w;
G->arc[n][m] = G->arc[m][n];
}
}
void MiniSpanTree_Kruskal(MGraph G) {
int v1, v2, vs1, vs2;
Edge edges[MAXEDGE];
int parent[MAXVEX]; //标记各顶点所属的连通分量，用于判断边与边是否形成环路
//将邻接矩阵转换成按权值从小到大排序的边集数组
/*
*/
int tmp = 0, m, n, ans;
ans = (G.numVertexes*G.numVertexes) / 2 - G.numVertexes / 2;
for(int k = 0; k < ans; k++) {
int min = INF, i, j;
for(i = 0; i < G.numVertexes; i++) {
for(j = 0; j < G.numVertexes; j++) {
if(!vis[i][j] && i < j && min > G.arc[i][j]) {
min = G.arc[i][j];
m = i;
n = j;
}
}
}
if(G.arc[i][j] == INF)
continue;
edges[tmp].begin = m;
edges[tmp].end = n;
edges[tmp].weight = min;
vis[m][n] = true;
tmp++;
}
//初始化为各顶点各自为一个连通分量
for(int i = 0; i < G.numVertexes; i++)
parent[i] = i;
for(int i = 0; i < G.numEdges; i++) {
//起点终点下标
v1 = edges[i].begin;
v2 = edges[i].end;
//起点终点连通分量
vs1 = parent[v1];
vs2 = parent[v2];
//边的两个顶点属于不同的连通分量，打印，将新来的连通分量更改为起始点的连通分量
if(vs1 != vs2) {
printf("V[%d]-V[%d] weight:%d\n", edges[i].begin, edges[i].end, edges[i].weight);
for(int j = 0; j < G.numVertexes; j++) {
if(parent[j] == vs2) parent[j] = vs1;
}
}
}
}
int main() {
MGraph *G = (MGraph *)malloc(sizeof(MGraph));
CreateMGraph(G);
MiniSpanTree_Kruskal(*G);
}
/*
input:
4 5
a
b
c
d
0 1 2
0 2 2
0 3 7
1 2 4
2 3 8
output:
V[0]-V[1] weight：2
V[0]-V[2] weight：2
V[0]-V[3] weight：7
*/
时间复杂度O(elog2e) e为边数
