克鲁斯卡尔算法最小生成树--C语言

        同样是最小生成树,普利姆算法是从一个起始顶点开始,逐步扩展生成树,每次选择连接生成树和未包含顶点的最小边。而克鲁斯卡尔算法是按权值排序的方式,从最小的边开始逐步添加到生成树中,确保不会形成环,直到生成树包含所有顶点。

假设我有下面的一个图,克鲁斯卡尔算法就是把这些带权值的边进行排序,然后添加到树中并确保不会成环。

第一步:首先遍历所有边,记录边的前驱和后继(判断是否有环会使用到),并进行排序,这里只列举了全三个边。

第二步:将边添加到树(直接打印前驱后继顶点和权值即可),检查是否有环,这一步该如何实现?

        有环的情况如下,假设 0->2 是最先加入到树的边,其次是 2->1 ,最后是 1->0 ,因为 0 是 2 的前驱,2 是 1 的前驱,那么我们可以让 0 是 1 的前驱,这样我们只需要检查 1 的后继是不是等于前驱即可,结果是等于,所以不能纳入。

        可以这样理解:0->2 是链表,2->1 增加了链表的长度,但是1,2都属于 0 这个头节点的集合,所以当新链加入时要判断新练的尾节点是否是头节点,如果是,就说明链表有环。

以上可以用结构体来实现。

第三步:遍历第二步,遍历一共 图的边数 次。

接下来是代码部分:

首先是结构体 边(Edge) 的构建:然后创建一个数组用于存放这些边,并且对边进行初始化。

        我们可以观察到边的二维数组是关于正对角线对称的,这是因为无向图权值会出现两次,例如:0->1 和1->0 都是 6,所以我们只需要在正对角线的一侧来寻找边即可,如果在整个图中寻找边最后会找到两组相同的边。这也是为什么 for 循环的条件一个是 i 一个是 i+1。

typedef struct Edge {
	int start;
	int end;
	int weight;
}Edge;

Edge* EdgeInit(Graph* G) {
	int index = 0;
	Edge* E = (Edge*)malloc(sizeof(Edge) * G->arcsNum);
	for (int i = 0; i < G->vexsNum; i++) {
		for (int j = i + 1; j < G->vexsNum; j++) {
			if (G->arcs[i][j] != Max) {
				E[index].start = i;
				E[index].end = j;
				E[index].weight = G->arcs[i][j];
				index++;
			}
		}
	}
	return E;
}

接着是边的排序:这里是简单的冒泡排序,让边数组的顺序根据权值大小从小到大排序。

void Edgesort(Edge* E,Graph* G) {
	for (int i = 0; i < G->arcsNum; i++) {
		for (int j = i + 1; j < G->arcsNum; j++) {
			if (E[j].weight < E[i].weight) {
				Edge tmp ;
				tmp = E[i];
				E[i] = E[j];
				E[j] = tmp;
			}
		}
	}
}

最后是函数主体:

1.connected数组是存顶点的前驱节点,用来表示该顶点在哪个顶点的集合内(相当于链表的头节点)。第一个for循环初始化该数组,因为初始前驱节点都是本身。
2.第二个for循环是为了遍历每条边,如果边的前驱和后继相等,那么不打印也即是不纳入树。
3.第三个for循环是更新connected数组,更新顶点的前驱节点。

void Kurskal(Edge* E, Graph* G) {
	Edgesort(E,G);
	int* connected = (int*)malloc(sizeof(int) * G->vexsNum);
	for (int i = 0; i < G->vexsNum; i++) {
		connected[i] = i;
	}
	for (int j = 0; j < G->arcsNum; j++) {
		int start = connected[E[j].start];
		int end = connected[E[j].end];
		if (start != end) {
			printf(" %c -> %c ,weight = %d", G->vexs[start], G->vexs[end], E[j].weight);
			printf("\n");
			for (int a = 0; a < G->arcsNum; a++) {
				if (connected[a] == end ) {
					connected[a] = start;
				}
			}
		}
	}
}

下面看一个例子用来理解最后一个for循环:

        首先最小的是 0->2 边,权值为1。那么就会打印 0->2,然后更新connected数组:由左图变成右图,把connected[2]更新为connected[0],也就是说 2 的前驱是 0 ,那么它就在 0 的集合内(链表内)。

 

        假设说现在又有 2->1 边进入,那么connected数组变化如下:这时的start是0,end是1,把connected[1]的值更新为connected[2],表示纳入该集合(链表)。

        现在又有一个边 1->0 进入,现在connected[1]和connected[0]的位置都是0,也就是start等于end,这时还纳入就会造成成环问题,所以不进入if语句,不进入树。

以上就是最后一个for循环的解释。

这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎指出。

相关推荐

  1. python 算法算法

    2024-06-09 22:08:02       35 阅读
  2. 普里姆(prim)和(Kruskal)

    2024-06-09 22:08:02       24 阅读

最近更新

  1. Html_Css问答集(3)

    2024-06-09 22:08:02       0 阅读
  2. C++ 数据结构

    2024-06-09 22:08:02       0 阅读
  3. 设计模式之适配器模式

    2024-06-09 22:08:02       0 阅读
  4. GitHub每日最火火火项目(6.14)

    2024-06-09 22:08:02       0 阅读

热门阅读

  1. 解决更新Android Studio后下载Gradle超时

    2024-06-09 22:08:02       4 阅读
  2. 给自己Linux搞个『回收站』,防止文件误删除

    2024-06-09 22:08:02       4 阅读
  3. 前端通用样式调整方法(整理版)

    2024-06-09 22:08:02       4 阅读
  4. web 前端开发培训:深入探索与实战应用

    2024-06-09 22:08:02       4 阅读
  5. 线程+线程池+锁

    2024-06-09 22:08:02       5 阅读
  6. 多维vector定义

    2024-06-09 22:08:02       3 阅读
  7. 计算各聚类中心

    2024-06-09 22:08:02       4 阅读
  8. 程序代码问题随时记录

    2024-06-09 22:08:02       5 阅读
  9. 栈和队列的转换

    2024-06-09 22:08:02       4 阅读
  10. 全面解析LG webOS:从开发到智能电视的演进

    2024-06-09 22:08:02       5 阅读