數據結構—Kruskal最小生成樹

原理：參考趣學數據結構

代碼：

快速排序：

#pragma once #define elemType int typedef struct vER {elemType u;elemType v;int weight; }VER; int quickSort(VER a[], int l, int h) {//快速排序int i = l, j = h;VER p = a[l];while (i < j) {while (i<j&&a[j].weight>p.weight) {//從右往左遍歷查找比p更小的元素j--;}if (i < j) {a[i++] = a[j];}while (i < j&&a[i].weight <= p.weight) {//從左往右遍歷查找比p更大的元素i++;}if (i < j) {a[j--] = a[i];}}a[i] = p;//分界的值，左邊小于等于p，右邊大于preturn i; } void fenZhi(VER a[], int l, int h) {//分治if (l < h) {int mid = quickSort(a, l, h);//以mid為分界線，進行分治，然后遞歸下去排序fenZhi(a, l, mid - 1);fenZhi(a, mid + 1, h);} }

Kruskal代碼：

#include<stdio.h> #include<stdlib.h> #include"quickSort.h" #define N 100 #define elemType int //const int MAX_INT = (1 << 31) - 1; //const int MAX_INT = 0X7fffffff; #define INF (((unsigned int)(-1)) >> 1) int visited[N]; typedef struct GraphMatrix {elemType vNode[N][N];int vNum, eNum; }GraphMatrix; void initGMaxtix(GraphMatrix &G) {//初始化鄰接矩陣printf("輸入頂點數和邊數\n");scanf_s("%d%d", &G.vNum, &G.eNum);for (int i = 0; i < G.vNum; i++) {//初始化鄰接矩陣for (int j = 0; j < G.vNum; j++) {G.vNode[i][j] = INF;}}printf("輸入頂點v1到頂點v2和其邊的權重\n");for (int i = 0; i < G.eNum; i++) {int v1, v2, weights;scanf_s("%d%d%d", &v1, &v2, &weights);G.vNode[v1][v2] = weights;} } void print16(GraphMatrix G) {printf("鄰接矩陣如下:\n");for (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {printf("%d ", G.vNode[i][j]);}printf("\n");} } bool merge(int u, int v,int vNum) {//把所有是與v頂點同一個集合的 加入到與u頂點的同一個集合int p = visited[u];int q = visited[v];if (p == q) {//同一個集合return false;}for (int i = 0; i < vNum; i++) {if (visited[i] == q) {visited[i] = p;}}return true; } void Kruskal(GraphMatrix G, int gouZaoSCTreeENum) {//最小生成樹VER a[N];int k = 0;//構造結構體頂點之間權重數組for (int i = 0; i < G.vNum; i++) {for (int j = 0; j < G.vNum; j++) {if (G.vNode[i][j] < INF) {//有邊a[k].u = i;a[k].v = j;a[k].weight = G.vNode[i][j];k++;}}}//對邊權重進行快速排序fenZhi(a, 0, k - 1);int ans = 0;int n = G.eNum;for (int i = 0; i < gouZaoSCTreeENum; i++) {if (merge(a[i].u, a[i].v, G.vNum)) {ans += a[i].weight;printf("\n%d-----%d有邊\n", a[i].u, a[i].v);n--;if (n == 1) {printf("\n最小生成樹的邊的總長度為%d\n", ans);break;}}} } int main() {GraphMatrix G;initGMaxtix(G);print16(G);printf("\n");for (int i = 0; i < G.vNum; i++) {//首先初始化G.vNum個集合visited[i] = i;}printf("Kruskal最小生成樹\n");Kruskal(G, G.eNum);printf("\n");system("pause");return 0; }

測試截圖：

時間復雜度O(nlogn),空間復雜度O(n)

如果存在什么問題，歡迎批評指正！謝謝！

總結

以上是生活随笔為你收集整理的数据结构---Kruskal最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。