目录
前言
一、克鲁斯卡尔算法构造过程
二、算法实现
1.辅助结构体、数组
2.算法核心
3.排序函数
总结
前言
承接上文普里姆算法，这里的克鲁斯卡尔算法是解决最短联通路径的另一种算法，细节就不多概述了，思想都是一样的，知识解决问题的出发点不一样
一、克鲁斯卡尔算法构造过程
1.首先克鲁斯卡尔算法是以边出发，通过比较边的大小来确定点
2.在联通网中将所有的边进行从小到大的排序
3.按次序输出边的两个点
4.重复3过程，知道全部的点都处理完
二、算法实现
1.辅助结构体、数组
这里需要将每条边所对应的点和权值都需要用一个结构体存储起来，方便后期的使用
代码如下（示例）：
typedef struct
{
VerType head;//边的始点
VerType tail;//边的终点
AreType lowcost;//最小边上的权值
}edge, * Edge;
2.算法核心
这里我将解析都写成注释了，这里就不一一进行赘述了，大家看代码就好了
代码如下（示例）：
void Kruskal(Edge &E,Graph &G)//算法核心开始
{
E = (Edge)malloc(sizeof(edge) * G.side);//开辟空间，有多少条边开辟多少空间
VerType* vexset = (char*)malloc(sizeof(char) * G.vertex);//开辟一个辅助数组来判断点是否已经使用
if (!E || !vexset)
return ;
for (int i = 0; i < G.vertex; i++)
{
vexset[i] = G.Ver[i];//将所有的点存入辅助数组中，后面进行判定
}
int num = 0;
for (int i = 0; i < G.vertex; i++)//将有联系的边对应的两个点进行存储
{
for (int j = i; j < G.vertex; j++)
{
if (G.Are[i][j] != MaxInt)
{
E[num].lowcost = G.Are[i][j];
E[num].head = G.Ver[i];
E[num].tail = G.Ver[j];
num++;
}
}
}
Sort(E,G);//将所有的边按照顺序排序，方便后面寻找点
问题点：排序出现问题
//for (int i = 0; i < G.side; i++)
//{
// printf("%d%c%c ", E[i].lowcost,E[i].head,E[i].tail);//打印测试，说明排序出现问题！！
//}
/*printf("\n");*/
for (int i = 0; i < G.side; i++)
{
int h = local_vertex(G, E[i].head);//头节点的位置
int t = local_vertex(G, E[i].tail);//尾节点的位置
char h1 = vexset[h];//找到辅助数组中的点
char t1 = vexset[t];
char hh = G.Ver[h];//通过图的点来打印
char tt = G.Ver[t];
if (h1 != t1)//只要我的辅助数组中的点没有全部相同说明还有点没有处理完
{
printf("%c%c ", hh, tt);
for (int j = 0; j < G.vertex; j++)//通过此循环判断点是不是全部处理完
{
if (t1 == vexset[j])
{
vexset[j] = h1;
}
}
}
}
}
3.排序函数
这里我就用的最简单的冒泡，如果大家有更好的方法，那就用自己最好的方法就可以了
但是这里要注意，你将权值排序，那边所对应的点也要跟着移动
代码示例：
void Sort(Edge e,Graph G)//将边进行排序
{
for (int i = 0; i < G.side - 1; i++)
{
for (int j = 0; j < G.side - 1 - i; j++)
{
if (e[j].lowcost > e[j + 1].lowcost)//排序过程中不仅要交换权值，还要将边所对应点进行交换
{
int temp = e[j].lowcost;
e[j].lowcost = e[j + 1].lowcost;
e[j + 1].lowcost = temp;
char h = e[j].head;
e[j].head = e[j + 1].head;
e[j + 1].head = h;
char t = e[j].tail;
e[j].tail = e[j + 1].tail;
e[j + 1].tail = t;
}
}
}
}
总结
这里就不再仔细的去分析算法的过程了，如果要具体了解最小生成树可以看看之前的普里姆算法，核心都是一样的，只是处理的方式不一样，谢谢大家关注咯!(顺嘴提一下，没有图的基础这里确实看不懂，如果对图有疑问可以再看看我前面的图的创建)
这里我只是实现了这个算法，并没有优化，所以肯定是存在问题，希望大家多多理解
最后放一下所有的代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxInt 32767
typedef char VerType;
typedef int AreType;
typedef struct graph
{
AreType side;
AreType vertex;
VerType* Ver;//顶点
AreType** Are;
}Graph;
typedef struct
{
VerType head;//边的始点
VerType tail;//边的终点
AreType lowcost;//最小边上的权值
}edge, * Edge;
int Local(Graph G, char vertex)
{
for (int i = 0; i < G.vertex; i++)
{
if (G.Ver[i] == vertex)//遍历寻找边的位置
{
return i;
}
}
}
void Visit(Graph G)
{
for (int i = 0; i < G.vertex; i++)
{
printf("%-2c", G.Ver[i]);//打印输入的顶点
}
printf("\n");
for (int i = 0; i < G.vertex; i++)
{
for (int j = 0; j < G.vertex; j++)
{
if (G.Are[i][j] == MaxInt)
printf("& ");//打印邻接矩阵
else
printf("%-2d", G.Are[i][j]);
}
printf("\n");
}
}
void CreatGraph(Graph& G, FILE* fp)
{
char input;
G.Ver = (VerType*)malloc(sizeof(VerType) * G.vertex);
G.Are = (AreType**)malloc(sizeof(AreType*) * G.vertex);
for (int i = 0; i < G.vertex; i++)
{
G.Are[i] = (AreType*)malloc(sizeof(AreType) * G.vertex);
}
if ((!G.Ver) && (!G.Are))//分配不成功退出
return;
for (int i = 0; i < G.vertex; i++)
{
fscanf(fp, "%c\n", &input);
G.Ver[i] = input;
}
for (int i = 0; i < G.vertex; i++)
{
for (int j = 0; j < G.vertex; j++)//对邻接矩阵进行初始化
{
G.Are[i][j] = MaxInt;
}
}
}
void WxW(Graph G, FILE* fp) //邻接无向网
{
char b1, b2;
int n;
for (int k = 0; k < G.side; k++)
{
fscanf(fp, "%c,%c,%d\n", &b1, &b2, &n);
int i = Local(G, b1);
int j = Local(G, b2);
G.Are[i][j] = n;
G.Are[j][i] = n;
}
}
void Sort(Edge e,Graph G)//将边进行排序
{
for (int i = 0; i < G.side - 1; i++)
{
for (int j = 0; j < G.side - 1 - i; j++)
{
if (e[j].lowcost > e[j + 1].lowcost)//排序过程中不仅要交换权值，还要将边所对应点进行交换
{
int temp = e[j].lowcost;
e[j].lowcost = e[j + 1].lowcost;
e[j + 1].lowcost = temp;
char h = e[j].head;
e[j].head = e[j + 1].head;
e[j + 1].head = h;
char t = e[j].tail;
e[j].tail = e[j + 1].tail;
e[j + 1].tail = t;
}
}
}
}
int local_vertex(Graph G, VerType ver)//返回边的始点
{
int i = 0;
for (int i = 0; i < G.vertex; i++)
{
if (ver==G.Ver[i])
{
return i;
}
}
}
void Kruskal(Edge &E,Graph &G)//算法核心开始
{
E = (Edge)malloc(sizeof(edge) * G.side);//开辟空间，有多少条边开辟多少空间
VerType* vexset = (char*)malloc(sizeof(char) * G.vertex);//开辟一个辅助数组来判断点是否已经使用
if (!E || !vexset)
return ;
for (int i = 0; i < G.vertex; i++)
{
vexset[i] = G.Ver[i];//将所有的点存入辅助数组中，后面进行判定
}
int num = 0;
for (int i = 0; i < G.vertex; i++)//将有联系的边对应的两个点进行存储
{
for (int j = i; j < G.vertex; j++)
{
if (G.Are[i][j] != MaxInt)
{
E[num].lowcost = G.Are[i][j];
E[num].head = G.Ver[i];
E[num].tail = G.Ver[j];
num++;
}
}
}
Sort(E,G);//将所有的边按照顺序排序，方便后面寻找点
问题点：排序出现问题
//for (int i = 0; i < G.side; i++)
//{
// printf("%d%c%c ", E[i].lowcost,E[i].head,E[i].tail);//打印测试，说明排序出现问题！！
//}
/*printf("\n");*/
for (int i = 0; i < G.side; i++)
{
int h = local_vertex(G, E[i].head);//头节点的位置
int t = local_vertex(G, E[i].tail);//尾节点的位置
char h1 = vexset[h];//找到辅助数组中的点
char t1 = vexset[t];
char hh = G.Ver[h];//通过图的点来打印
char tt = G.Ver[t];
if (h1 != t1)//不能是同一个点
{
printf("%c%c ", hh, tt);
for (int j = 0; j < G.vertex; j++)//通过此循环判断点是不是全部处理完
{
if (t1 == vexset[j])
{
vexset[j] = h1;
}
}
}
}
}
int main()
{
Graph G;
Edge E;
int d, b;
FILE* fp;
fp = fopen("abc.txt", "r");//读取名为abc的文本文件
if (fp == NULL)
printf("文件为空！");
fscanf(fp, "%d %d\n", &d, &b);
G.vertex = d;
G.side = b;
CreatGraph(G, fp);
WxW(G, fp);
fclose(fp);
Visit(G);
Kruskal(E,G);
return 0;;
}
