最小生成树Kruskal算法:首先对边的权值进行从小到大排列，每次从剩余的边中选择权值较小且边的两个顶点不在
同一个集合内的边（就是不会产生回路的边），加到生成树中，直到加入的边为n-1为止
时间复杂度：m 边数 n顶点数 对边进行快速排序是O(MlogM) 在m条边中选择n-1条边的是O(MlogN); 故时间
复杂度为O(MlogM + MlogN);通常M比N大很多，故时间复杂度为O(MlogM);
#pragma mark - - 最小生成树 Kruskal 算法
struct edge {
int u; // 顶点
int v; // 顶点
int w; // 权值
};
struct edge e[10];
void quicksort(int left,int right) {
if (left>right) {
return ;
}
int I=left;
int j=right;
int temp = e[left].w; //基准数
struct edge t;
while (i!=j) {
// 从右往左找 直到找到一个小于基准数 停下
while (e[j].w >= temp && i<j) {
j--;
}
// 从左往右找 直到找到一个大于基准数 停下
while (e[i].w <= temp && i<j) {
I++;
}
// 如果不相等
if (i<j) {
//交换
t =e[I];
e[i] =e[j];
e[j] = t;
}
}
// 相等 基准数归位 将left 和 i交换
t = e[left];
e[left] = e[I];
e[i] = t;
quicksort(left, i-1); // 继续处理左边的
quicksort(i+1, right); // 继续处理右边的
}
// 并查集寻找祖先 函数
int getf(int v, int f[]) {
if (f[v] == v) {
return v;
}else {
// 路径压缩
f[v] = getf(f[v], f);
return f[v];
}
}
int merge(int v,int u,int f[]) {
int t1;
int t2;
t1 = getf(v, f);
t2 = getf(u, f);
if (t1!=t2) {
f[t2] =t1;
return 1;
}
return 0;
}
-(void)test1 {
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
int m=9;
int n=6;
// 初始化 边数据
for (int i=1; i<=m; i++) {
struct edge t;
t.u = s[i][0];
t.v = s[i][1];
t.w = s[i][2];
e[i] = t;
}
// 快速排序 边数据
quicksort(1, m);
// 初始化 并查集
int f[10];
for (int i=1; i<=n; i++) {
f[i] = I;
}
//Kruskal算法 核心
int sum=0;
int count=0;
// 从小到大 枚举每一条边
for (int i=1; i<=m; i++) {
if (merge(e[i].u, e[i].v, f)) {
count ++;
sum += e[i].w;
printf("{%d,%d,%d} ",e[i].u,e[i].v,e[i].w);
}
if (count==n-1) {
break ;
}
}
printf("\n\n%d\n\n",sum);
}
Prim 算法:
1.从任意一个顶点开始构造树，假设从顶点1开始。首先将顶点1加入生成树中，用一个一维数组Book来标记哪些顶点
已经加入生成树
2.用数组dis记录生成树到各个顶点的距离。最初生成树中只有1个顶点。有直连边时，数组dis中存储的就是1号顶点
到该顶点的边的权值，没有直连边的时候就是无穷大，即初始化dis数组
3.从数组dis中选出离生成树最近的顶点（假设这个顶点为j）加入到生成树中（Book[j]==1）。然后以j为中间点，
更新生成树到每一个非树顶点的距离（松弛），即如果dis[k] > e[j][k]则更新为dis[k]=e[j][k](j在生成树
中，e[j][k]就是表示非树顶点k到生成树的以j为中间点的距离，dis[k]表示非树顶点k到生成树的以其他顶点(
顶点j除外)为中间点的最短距离)
4.重复上述操作，直到生成树中有n个顶点为止~
#pragma mark - - 最小生成树 Prim 算法 (DJP算法)
-(void)test2 {
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
int m=9;
int n=6;
int z[10][10];
int inf =9999;
// 初始化 边数据
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
z[i][j] =0;
}else {
z[i][j] =inf;
}
}
}
for (int i=1; i<=m; i++) {
int s1 = s[i][0];
int s2 = s[i][1];
int s3 = s[i][2];
// 无向图
z[s1][s2] = s3;
z[s2][s1] = s3;
}
// 初始化化 dis数组
int dis[10];
for (int i=0; i<10; i++) {
dis[i] = 9999;
}
// 初始化book数组 标记一个顶点是否已经加入到生成树
int book[10] = {0};
// 假设从顶点1开始
dis[1] =0;
// 记录总距离
int sum=0;
// Prim算法 核心
for (int j=1; j<=n; j++) {
// 较小值
int min =inf;
// 较小点
int u=0;
// 找到最小值
for (int i=1; i<=n; i++) {
if (book[i]==0 && dis[i]<min) {
min = dis[I];
u=I;
}
}
book[u] =1;
sum+=dis[u];
// 扫描当前顶点u所有边 再以u为中间点，更新生成树到每一个非树顶点的距离
for (int k=1; k<=n; k++) {
if (dis[k] > z[u][k] && book[k]==0) {
dis[k] = z[u][k];
}
}
}
printf("\n最短距离为%d\n\n",sum);
}
优化方向：
1.dis[]最小值 可以用堆排序
2.扫描当前顶点u所有边 再以u为中间点，更新生成树到每一个非树顶点的距离，这块可以用邻接表
#pragma mark - - 优化 Prim 算法
int size=6;
int dis[7];
int h[7]; //保存堆数据 h[i]=t 表示顶点t
int pos[7]; // pos用来存储每个顶点在堆中的位置 pos[h[i]] = I;
int book[7]={0};
void siftdown(int i) {
int t=0;
int flag=0;
while (2*i<=size && flag == 0) {
if (dis[h[i]] > dis[h[2*i]]) {
t =2*I;
}else {
t = I;
}
if (1+2*i <= size) {
if (dis[h[t]] > dis[h[2*i+1]]) {
t =2*I+1;
}
}
if (t!=i) {
swap(t, i);
I=t;
}else {
flag=1;
}
}
}
void swap(int x, int y) {
int t = h[x];
h[x] = h[y];
h[y] = t;
// 同步更新 pos
t = pos[h[x]];
pos[h[x]] = pos[h[y]];
pos[h[y]] = t;
return;
}
// 从堆顶取出一个元素
int pop() {
int t;
t = h[1];
pos[t] =0;
h[1] = h[size];
pos[h[1]] = 1;
size --;
siftdown(1);
return t;
}
void siftup(int i) {
if (i==1) {
return ;
}
int flag=0;
while (i!=1 && flag == 0) {
if (dis[h[i]] < dis[h[i/2]]) {
swap(i, i/2);
}else {
flag =1;
}
i=I/2;
}
}
-(void)test3 {
int u[20],v[20],w[20];
int first[20],next[20];
int m=9;
int n=6;
int count=0;
int sum=0;
int inf=9999;
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
for (int i=1; i<=m; i++) {
u[i] = s[i][0];
v[i] = s[i][1];
w[i] = s[i][2];
}
// 由于是无向图 所以需要把所有边反向再存储一遍
for (int i=m+1; i<=2*m; i++) {
u[i] = v[i-m];
v[i] = u[i-m];
w[i] = w[i-m];
}
//初始化 first
for (int i=0; i<20; i++) {
first[i] = -1;
}
// 邻接表
for (int i=1; i<=2*m; i++) {
next[i] = first[u[I]];
first[u[i]] = I;
}
// Prim 核心代码
// 将1号点加入生成树
book[1] =1;
count++;
// 初始化dis数组，这里是1号顶点到其余各个顶点的初始距离
for (int i=0; i<=n; i++) {
dis[i] = inf;
}
dis[1]=0;
int k=first[1];
while (k!=-1) {
dis[v[k]] = w[k];
k=next[k];
}
// 初始化堆
for (int i=1; i<=size; i++) {
h[i] =I;
pos[i] =I;
}
for (int i=size/2; i>=1; i--) {
siftdown(i);
}
//先弹出一个堆顶元素 因为此时堆顶是1号顶点
pop();
while (count<n) {
int j=pop();
book[j]=1;
count++;
sum+=dis[j];
// 扫描当前顶点j的所有的边 再以j为中间顶点 进行松弛
k =first[j];
while (k!=-1) {
if (book[v[k]]==0 && dis[v[k]] > w[k]) {
dis[v[k]] =w[k];
siftup(pos[v[k]]);
}
k=next[k];
}
}
printf("\n最短距离为%d\n\n",sum);
}
