欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Prim(普里姆)算法求最小生成樹的思想及C語言實(shí)例講解

 更新時(shí)間:2016年06月26日 16:07:47   作者:_陌上花開7_  
Prim算法能夠在帶權(quán)的圖中搜索出最小生成樹,這也是各大ACM和面試及考研題目中的熱點(diǎn),下面我們就來詳細(xì)看一下Prim(普里姆)算法求最小生成樹的思想及C語言實(shí)例講解

Prim 算法思想:
從任意一頂點(diǎn) v0 開始選擇其最近頂點(diǎn) v1 構(gòu)成樹 T1,再連接與 T1 最近頂點(diǎn) v2 構(gòu)成樹 T2, 如此重復(fù)直到所有頂點(diǎn)均在所構(gòu)成樹中為止。
最小生成樹(MST):權(quán)值最小的生成樹。
生成樹和最小生成樹的應(yīng)用:要連通n個(gè)城市需要n-1條邊線路??梢园堰吷系臋?quán)值解釋為線路的造價(jià)。則最小生成樹表示使其造價(jià)最小的生成樹。
構(gòu)造網(wǎng)的最小生成樹必須解決下面兩個(gè)問題:
1、盡可能選取權(quán)值小的邊,但不能構(gòu)成回路;
2、選取n-1條恰當(dāng)?shù)倪呉赃B通n個(gè)頂點(diǎn);
MST性質(zhì):假設(shè)G=(V,E)是一個(gè)連通網(wǎng),U是頂點(diǎn)V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊,其中u∈U,v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。
prim算法假設(shè)G=(V,E)是連通的,TE是G上最小生成樹中邊的集合。算法從U={u0}(u0∈V)、TE={}開始。重復(fù)執(zhí)行下列操作:
在所有u∈U,v∈V-U的邊(u,v)∈E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中,同時(shí)v0并入U(xiǎn),直到V=U為止。
此時(shí),TE中必有n-1條邊,T=(V,TE)為G的最小生成樹。
 Prim算法的核心:始終保持TE中的邊集構(gòu)成一棵生成樹。
注意:prim算法適合稠密圖,其時(shí)間復(fù)雜度為O(n^2),其時(shí)間復(fù)雜度與邊得數(shù)目無關(guān),而kruskal算法的時(shí)間復(fù)雜度為O(eloge)跟邊的數(shù)目有關(guān),適合稀疏圖。
舉個(gè)簡單的例子來說明具體的實(shí)現(xiàn)方法:

2016626160439131.jpg (361×256)

G:圖,用鄰接矩陣表示
vcount:表示圖的頂點(diǎn)個(gè)數(shù)
max_vertexes:圖最大節(jié)點(diǎn)數(shù)
infinity:為無窮大
數(shù)組存儲(chǔ)從0開始
由于最小生成樹包含每個(gè)頂點(diǎn),那么頂點(diǎn)的選中與否就可以直接用一個(gè)數(shù)組來標(biāo)記used[max_vertexes];(我們這里直接使用程序代碼中的變量定義,這樣也易于理解);當(dāng)選中一個(gè)數(shù)組的時(shí)候那么就標(biāo)記,現(xiàn)在就有一個(gè)問題,怎么來選擇最小權(quán)值邊,注意這里最小權(quán)值邊是有限制的,邊的一個(gè)頂點(diǎn)一定在已選頂點(diǎn)中,另一個(gè)頂點(diǎn)當(dāng)然就是在未選頂點(diǎn)集合中了。我最初的一個(gè)想法就是窮搜了,就是在一個(gè)集合中選擇一個(gè)頂點(diǎn),來查找到另一個(gè)集合中的最小值,這樣雖然很易于理解,但是很明顯效率不是很高,在嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》上提供了一種比較好的方法來解決:設(shè)置兩個(gè)輔助數(shù)組lowcost[max_vertexes]和closeset[max_vertexes],lowcost[max_vertexes]數(shù)組記錄從U到V-U具有最小代價(jià)的邊。對于每個(gè)頂點(diǎn)v∈V-U,closedge[v], closeset[max_vertexes]記錄了該邊依附的在U中的頂點(diǎn)。

Prim 算法步驟:
T0 存放生成樹的邊,初值為空
輸入加權(quán)圖的帶權(quán)鄰接矩陣 C = (Cij)n×n (兩點(diǎn)間無邊相連則其大小為無窮)
為每個(gè)頂點(diǎn) v 添加一屬性 L(v) :表 v 到 T0 的最小直接距離
(1) T0←∅, V1={v0}, C(T0)=0
(2) 對任意v ∈ V,L(v)←C(v, v0)
(3) If V==V1 then stop else goto next.
(4) 在 V-V1 中找點(diǎn) u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},記 V1 中與 u 相鄰點(diǎn)為 w.
(5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u}
(6) 對任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不變。
(7) Go to 3.

C++實(shí)現(xiàn)示例
prim.txt中的內(nèi)容:

1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
5 6 6
4 6 2

 
程序代碼:

#include<stdo.h>
#include<string.h>
#include <stdlib.h>
 
#define infinity 1000000 //  定義兩個(gè)不直接相鄰一步到達(dá)頂點(diǎn)的距離 
#define max_vertexes 6 //  定義圖形中頂點(diǎn)的個(gè)數(shù)
 
typedef int Graph[max_vertexes][max_vertexes];// 邊上的權(quán)值
 
void prim(Graph G,int vcount,int father[])
{  
  int i,j,k;
  int lowcost[max_vertexes];//最小代價(jià)邊上的權(quán)值
  int closeset[max_vertexes],used[max_vertexes];//依附在U中的頂點(diǎn);標(biāo)記是否已被選中
  int min;
  int result=0;//記錄最短距離權(quán)值的和
 
 
  for (i=0;i<vcoun;k++)  //初始化所有數(shù)組,把最短距離初始化為其他頂點(diǎn)到1結(jié)點(diǎn)的距離
  {
      lowcost[i]=G[0][i]; 
      closeset[i]=0;   
   used[i]=0;  
   father[i]=-1;   
  }  
  used[0]=1;
 
 
  
  for (i=1;i<=vcount-1;i++)   
  {   
   j=0;
    min = infinity;
      
   for (k=1;k<count;k++) //for循環(huán)得到離結(jié)點(diǎn)最近的頂點(diǎn)j
   if ((!used[k])&&(lowcost[k]
   {
    min = lowcost[k];
    j=k;
   }
   father[j]=closeset[j]; 
   printf("%d %d\n",j+1,father[j]+1);//輸出當(dāng)前找到的結(jié)點(diǎn),該頂點(diǎn)依附的上一個(gè)結(jié)點(diǎn)
   result=result+G[j][closeset[j]];
   used[j]=1;;//把第j個(gè)頂點(diǎn)并入了U中  
   for (k=1;k
        
   if (!used[k]&&(G[j][k]保留到k的最短路徑
 
    {
      lowcost[k]=G[j][k];   
      closeset[k]=j;
    }   
  }
  printf("%d",result);
}
        
int main()
{
  FILE *fr;
  int i,j,weight;
  Graph G;
  int fatheer[max_vertexes];
  for(i=0; i<max_vertexes;i++)
  for(j=0; j<max_vertexer;i++)
  G[i][j] = infinity;
  fr = fopen("prim.txt","r");
  if(!fr)
  {
   printf("fopen failed\n");
   exit(1);
  }
  while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)
  {
   G[i-1][j-1] = weight;
   G[j-1][i-1] = weight;
  }
 
  prim(G,max_vertexes,fatheer);
  return 0;
 
}

測試的結(jié)果如下:
2016626160558508.jpg (490×297)

相關(guān)文章

  • 帶你理解C語言中的漢諾塔公式

    帶你理解C語言中的漢諾塔公式

    大家好,本篇文章主要講的是帶你理解C語言中的漢諾塔公式,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-01-01
  • C語言函數(shù)指針的使用詳解

    C語言函數(shù)指針的使用詳解

    在C語言中,函數(shù)指針是指向函數(shù)的指針變量,本文主要介紹了C語言函數(shù)指針的使用詳解,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-01-01
  • C/C++ Qt ToolBar菜單組件的具體使用

    C/C++ Qt ToolBar菜單組件的具體使用

    ToolBar工具欄在所有窗體應(yīng)用程序中都廣泛被使用,使用ToolBar可以很好的規(guī)范菜單功能分類,本文就詳細(xì)的介紹一下ToolBar組件的應(yīng)用,感興趣的可以了解一下
    2021-11-11
  • C++中的Lambda函數(shù)詳解

    C++中的Lambda函數(shù)詳解

    大家好,本篇文章主要講的是C++中的Lambda函數(shù)詳解,感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • 對C語言編程標(biāo)準(zhǔn)以及聲明的基本理解

    對C語言編程標(biāo)準(zhǔn)以及聲明的基本理解

    這篇文章主要介紹了對C語言編程標(biāo)準(zhǔn)以及聲明的基本理解,有助于對C語言編寫時(shí)的結(jié)構(gòu)有更加清晰的認(rèn)識(shí),需要的朋友可以參考下
    2015-11-11
  • C語言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)詳解

    C語言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)詳解

    對于數(shù)組想必大家都不陌生首先得要知道的是對于數(shù)組元素在內(nèi)存存儲(chǔ)是連續(xù)性的,下面這篇文章主要給大家介紹了關(guān)于C語言多維數(shù)組數(shù)據(jù)結(jié)構(gòu)的相關(guān)資料,需要的朋友可以參考下
    2021-12-12
  • C++讀寫配置項(xiàng)的基本操作

    C++讀寫配置項(xiàng)的基本操作

    這篇文章主要介紹了C++讀寫配置項(xiàng)的基本操作,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下
    2021-01-01
  • C++的數(shù)據(jù)類型你真的了解嗎

    C++的數(shù)據(jù)類型你真的了解嗎

    這篇文章主要為大家詳細(xì)介紹了C++的數(shù)據(jù)類型,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-02-02
  • C++實(shí)現(xiàn)LeetCode(62.不同的路徑)

    C++實(shí)現(xiàn)LeetCode(62.不同的路徑)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(62.不同的路徑),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • 雙向鏈表插入刪除基本應(yīng)用介紹

    雙向鏈表插入刪除基本應(yīng)用介紹

    本文將詳細(xì)介紹建立雙向鏈表,實(shí)現(xiàn)對雙向鏈表的插入,刪除操作,需要了解的朋友可以參考下
    2012-11-11

最新評論