c/c++ 用克魯斯卡爾（kruskal）演算法構造最小生成樹

来源:https://www.cnblogs.com/xiaoshiwang/archive/2018/08/04/9420541.html
-Advertisement-
Play Games

c/c++ 用克魯斯卡爾（kruskal）演算法構造最小生成樹 最小生成樹（Minimum Cost Spanning Tree）的概念： 假設要在n個城市之間建立公路，則連通n個城市只需要n 1條線路。這時，自然會考慮，如何在最節省經費的前提下建立這個公路網路。 每2個城市之間都可以設置一條公路，相 ...


c/c++ 用克魯斯卡爾（kruskal）演算法構造最小生成樹

最小生成樹（Minimum Cost Spanning Tree）的概念：

假設要在n個城市之間建立公路，則連通n個城市只需要n-1條線路。這時，自然會考慮，如何在最節省經費的前提下建立這個公路網路。

每2個城市之間都可以設置一條公路，相應地都要付出一定的經濟代價。n個城市之間，最多可以設置n(n-1)/2條線路，那麼，如何在這些可能的線路中選擇n-1條，以使總的耗費最少？

克魯斯卡爾（kruskal）演算法的大致思路：

把每條邊的權重按照從小到大排序後，連接。連接時，需要查看要連接的兩個頂點的父節點是否相同，不同才可以連接，連接後，更新父節點。

圖為下圖：

第一步

圖1

第二步

圖2

第三步

圖3

第四步
A->D,C->D,B->C的權重都是5，這時就不知道連哪個了，所以要創建2個輔助函數is_same,mark_same。
is_same用來判斷要連接的2個點的父節點是否相同，如果相同就說明瞭，連接後，圖就存在了環，所以不可以連接，放棄這條邊，去尋找下一條邊。
mark_same用來更新節點的父節點。
當拿到的節點是AD時，發現AD的父節點都是A，所以放棄；
當拿到的節點是CD時，發現AD的父節點都是A，所以放棄；
當拿到的節點是BC時，發現B的父節點是自己，C的父節點是A，父節點不同，所以連接，並更父節點

圖4

找一半的矩陣，把各條邊的起點，終點，權重，放到edge數組裡

圖5

mixSpanTree.h

#ifndef __mixspantree__
#define __mixspantree__

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdlib.h>
#include <stdbool.h>

#define Default_vertex_size 20

#define T char//dai biao ding dian de lei xing
#define E int
#define MAX_COST 0x7FFFFFFF


typedef struct GraphMtx{
  int MaxVertices;//zui da ding dian shu liang]
  int NumVertices;//shi ji ding dian shu liang
  int NumEdges;//bian de shu lian

  T* VerticesList;//ding dian list
  int** Edge;//bian de lian jie xin xi, bu shi 0 jiu shi 1
}GraphMtx;

typedef struct Edge{
  int begin;//邊的起點
  int end;  //邊的終點
  E   cost; //邊的權重
}Edge;

//chu shi hua tu
void init_graph(GraphMtx* gm);
//列印二維數組
void show_graph(GraphMtx* gm);
//插入頂點
void insert_vertex(GraphMtx* gm, T v);
//添加頂點間的線
void insert_edge(GraphMtx* gm, T v1, T v2, E cost);

//用kruskal演算法構造最小生成樹
void minSpanTree_kruskal(GraphMtx* gm);

#endif

mixSpanTree.c

#include "mixSpanTree.h"

void init_graph(GraphMtx* gm){
  gm->MaxVertices = Default_vertex_size;
  gm->NumEdges = gm->NumVertices = 0;

  //kai pi ding dian de nei cun kong jian
  gm->VerticesList = (T*)malloc(sizeof(T) * (gm->MaxVertices));
  assert(NULL != gm->VerticesList);

  //創建二維數組
  //讓一個int的二級指針，指向一個有8個int一級指針的數組
  //開闢一個能存放gm->MaxVertices個int一級指針的記憶體空間
  gm->Edge = (int**)malloc(sizeof(int*) * (gm->MaxVertices));
  assert(NULL != gm->Edge);
  //開闢gm->MaxVertices組，能存放gm->MaxVertices個int的記憶體空間
  for(int i = 0; i < gm->MaxVertices; ++i){
    gm->Edge[i] = (int*)malloc(sizeof(int) * gm->MaxVertices);
  }
  //初始化二維數組
  //讓每個頂點之間的邊的關係都為不相連的
  for(int i = 0; i < gm->MaxVertices; ++i){
    for(int j = 0; j < gm->MaxVertices; ++j){
      if(i == j)
    gm->Edge[i][j] = 0;
      else
    gm->Edge[i][j] = MAX_COST;
    }
  }
}
//列印二維數組
void show_graph(GraphMtx* gm){
  printf("  ");
  for(int i = 0; i < gm->NumVertices; ++i){
    printf("%c  ", gm->VerticesList[i]);
  }
  printf("\n");
  for(int i = 0; i < gm->NumVertices; ++i){
    //在行首,列印出頂點的名字
    printf("%c:", gm->VerticesList[i]);
    for(int j = 0; j < gm->NumVertices; ++j){
      if(gm->Edge[i][j] == MAX_COST){
    printf("%c  ", '*');
      }
      else{
    printf("%d  ", gm->Edge[i][j]);
      }
    }
    printf("\n");
  }
  printf("\n");
}
//插入頂點
void insert_vertex(GraphMtx* gm, T v){
  //頂點空間已滿，不能再插入頂點了
  if(gm->NumVertices >= gm->MaxVertices){
    return;
  }
  gm->VerticesList[gm->NumVertices++] = v;
}

int getVertexIndex(GraphMtx* gm, T v){
  for(int i = 0; i < gm->NumVertices; ++i){
    if(gm->VerticesList[i] == v)return i;
  }
  return -1;
}
//添加頂點間的線
void insert_edge(GraphMtx* gm, T v1, T v2, E cost){
  if(v1 == v2)return;
  
  //查找2個頂點的下標
  int j = getVertexIndex(gm, v1);
  int k = getVertexIndex(gm, v2);
  //說明找到頂點了,並且點之間還沒有線
  if(j != -1 && k != -1 ){
    //因為是無方向，所以更新2個值
    gm->Edge[j][k] = gm->Edge[k][j] = cost;
    //邊數加一
    gm->NumEdges++;
  }
}

//比較邊的權重,本函數作為快速排序函數的參數來使用。
int cmp(const void* a, const void* b){
  return ((*(Edge*)a).cost - (*(Edge*)b).cost);
}
//判斷參數的2個頂點的父節點是否相同
bool is_same(int* father, int begin, int end){
  while(father[begin] != begin){
    begin = father[begin];
  }
  while(father[end] != end){
    end = father[end];
  }
  return begin == end;
}
//找到end節點的父節點x，再找到begin節點的父節點y，更新x節點的父節點為y
void mark_same(int* father, int begin, int end){
  while(father[begin] != begin){
    begin = father[begin];
  }
  while(father[end] != end){
    end = father[end];
  }
  father[end] = begin;

}
//用kruskal演算法構造最小生成樹
void minSpanTree_kruskal(GraphMtx* g){

  int n = g->NumVertices;
  Edge* edge = (Edge*)malloc(sizeof(Edge) * n*(n-1)/2);
  assert(edge != NULL);

  int k = 0;
  //查找一半的矩陣，把各條邊的起點，終點，權重，放到edge數組裡，參照上面的圖5
  for(int i = 0; i < n; ++i){
    for(int j = i; j < n; j++){
      if(g->Edge[i][j] != 0 && g->Edge[i][j] != MAX_COST){
    edge[k].begin = i;
    edge[k].end = j;
    edge[k].cost = g->Edge[i][j];
    k++;
      }
    }
  }

  //按照權重來排序(用系統函數）
  //第一個參數：要被排序的數組
  //第二個參數：數組中元素的個數
  //第三個參數：每個數組元素占用的記憶體空間
  //第四個參數：函數指針，指定排序的規則
  qsort(edge, k, sizeof(Edge), cmp);

  //初始化每個節點的父節點，讓每個節點的父節點為自身
  int *father = (int*)malloc(sizeof(int) * n);
  assert(NULL != father);
  for(int i = 0; i < n; ++i){
    father[i] = i;
  }

  for(int i = 0; i < n; ++i){
    //判斷2個節點的父節點是否相同，不相同就連接
    if(!is_same(father, edge[i].begin, edge[i].end)){
      printf("%c->%c:%d\n",g->VerticesList[edge[i].begin],g->VerticesList[edge[i].end], edge[i].cost);
      //連接後，找到節點end的父節點x，再找到節點begin的父節點y，把節點x的父節點更新為y
      mark_same(father, edge[i].begin, edge[i].end);
    }
  }
}

mixSpanTreemain.c

#include "mixSpanTree.h"

int main(){
  GraphMtx gm;
  //初始化圖
  init_graph(&gm);
  //插入頂點
  insert_vertex(&gm, 'A');
  insert_vertex(&gm, 'B');
  insert_vertex(&gm, 'C');
  insert_vertex(&gm, 'D');
  insert_vertex(&gm, 'E');
  insert_vertex(&gm, 'F');

  //添加連線
  insert_edge(&gm, 'A', 'B', 6);
  insert_edge(&gm, 'A', 'D', 5);
  insert_edge(&gm, 'A', 'C', 1);
  insert_edge(&gm, 'B', 'E', 3);
  insert_edge(&gm, 'B', 'C', 5);
  insert_edge(&gm, 'C', 'E', 6);
  insert_edge(&gm, 'C', 'D', 5);
  insert_edge(&gm, 'C', 'F', 4);
  insert_edge(&gm, 'F', 'E', 6);
  insert_edge(&gm, 'D', 'F', 2);
  //列印圖
  show_graph(&gm);

  //kruskal
  minSpanTree_kruskal(&gm);

}

完整代碼

編譯方法：gcc -g mixSpanTree.c mixSpanTreemain.c


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 統計演算法_數值/線性關係度量
    繼續統計演算法，這次也沒什麼特別的，還沒到那麼深入，也是比較基礎的1、方差-樣本2、協方差(標準差)-樣本3、變異繫數4、相關係數 依然是先造個list，這次把這個功能寫個函數，方便以後調用，另外上一篇寫過的函數這次也會繼承def create_rand_list(min_num,max_num,co ...
  • 利用phpspreadsheet切割excel大文件
    背景: 利用phpspreadsheet可以輕鬆的解析excel文件，但是phpspreadsheet的記憶體消耗也是比較大的，我試過解析將近5M的純文字excel記憶體使用量就會超過php預設的最大記憶體128M。 當然這可以用調節記憶體大小的方法來解決，但是在併發量大的時候就比較危險了。所以今天介紹下第 ...
  • 21天打造分散式爬蟲-Scrapy框架（七）
    7.1.糗事百科 安裝 pip install pypiwin32 pip install Twisted-18.7.0-cp36-cp36m-win_amd64.whl pip install scrapy 創建和運行項目 代碼 qsbk_spider.py item.py pipelines.p ...
  • 微信小程式如何調用API實現數據請求-wx.request()
    前言 微信小程式不存在 ，那麼它是如何實現數據請求功能的呢？在微信中提供了 的調用 ，這個是很不錯的。下麵就講一下如何請求數據，簡單到不行。 wx.request 看文檔時，提供了示例模板如下： 如何調取數據這是個難題，但是要模擬調用是有可能的。因為有個網址：https://easy mock.co ...
  • for，while陳述
    今天我們來說一下for 和while迴圈 Python迴圈語句的控制結構圖如下所示： for 是Python程式員使用最多的語句，for 迴圈用於迭代容器對象中的元素，這些對象可以是列表、元組、字典、集合、文件，甚至可以是自定義類或者函數 Python 布爾迴圈實例： 輸出如下：a b c d in ...
  • java基礎---類載入和對象創建過程
    類中可以存在的成員： 類載入過程： 1、JVM會先去方法區中找有沒有類對應的.class存在，如果有，就直接使用；如果沒有，就把對應類的.class載入到方法區； 2、將.class載入到方法區的時候，分為兩部分，首先將非靜態內容載入到方法區的非靜態區域內； 3、再將靜態內容載入到方法區的靜態區域內 ...
  • SpringMVC框架二：SpringMVC與MyBatis整合
    下麵整合SpringMVC和MyBatis框架，並做一個小案例 創建資料庫springmvc，並創建兩張表，加入一些數據： 兩張表：商品表，用戶表 新建Dynamic Web Project： 導包： 先把簡單的資料庫配置完成： db.properties: MyBatis的配置文件sqlMapCo ...
  • Gradle 入門
    `目錄 start` "Gradle" "書籍" "發行版本列表" "安裝配置" "SDKMAN方式" "Chocolate" "命令行選項" "守護進程" "Docker安裝" "配置鏡像源" "關鍵配置文件" "build.gradle" "初始化一個新項目" "dependency" "統一依 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類