一、圖的相關算法
1、圖的分類知識
如下圖：
? ? ? ? ? ? ?
2、生成樹概念
對連通圖進行遍歷，過程中所經過的邊和頂點的組合可看做是一棵普通樹，通常稱為生成樹。
連通圖的生成樹具有這樣的特征：邊的數量 = 頂點數 - 1
3、最小生成樹
在連通網的所有生成樹中，所有邊的代價和權值最小的生成樹，稱為最小生成樹。
? ? ? ? ? ? ?
4、 最小生成樹的算法
4.1普里姆算法(Prim算法)
它是圖論中的一種算法，可在加權連通圖里搜索最小生成樹。即由此算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權值之和亦為最小。該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；并在1957年由美國計算機科學家羅伯特·普里姆（Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該算法。因此，在某些場合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆－亞爾尼克算法。
算法如下：
void prim(MGraph g,int v)
{
? ? int lowcost[MAXV],min,n=g.vexnum;
? ? int closest[MAXV],i,j,k;
? ? for (i=0;i<n;i++)? ? ? ? ? ?//給lowcost[]和closest[]置初始值
? ? {? ?
? ? ? ? lowcost[i]=g.edges[v][i];
? ? ? ? closest[i]=v;
? ? }
? ? for (i=1;i<n;i++)? ? ? ? ? ?//找出n-1個頂點
? ? {? ?
? ? ? ? min=INF;
? ? ? ? for (j=0;j<n;j++)? ? ? ?//在(V-U)中找出離U最近的頂點k
? ? ? ? ? ? if (lowcost[j]!=0 && lowcost[j]<min)?
? ? ? ? ? ? {? ?
? ? ? ? ? ? ? ? min=lowcost[j];k=j;??
? ? ? ? ? ? }
? ? ? ? printf("? 邊(%d,%d)權為:%d\n",closest[k],k,min);
? ? ? ? lowcost[k]=0;? ? ? ? ? ?//標記k已經加入U
? ? ? ? for (j=0;j<n;j++)? ? ? ?//修改數組lowcost和closest
? ? ? ? ? ? if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])?
? ? ? ? ? ? {? ?
? ? ? ? ? ? ? ? lowcost[j]=g.edges[k][j];closest[j]=k;?
? ? ? ? ? ? }
? ? }
}
算法過程
?
? ? ? ? ? ? ?
?
4.2 克魯斯卡爾（Kruskal）算法
1、概念
該算法可以稱為“加邊法”，初始最小生成樹邊數為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里。
2、算法步驟
1. 把圖中的所有邊按代價從小到大進行排序；
2. 把圖中的n個頂點看成獨立的n棵樹組成的森林；
3. 按權值從小到大選擇邊，所選的邊連接的兩個頂點,應屬于兩顆不同的樹，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹。
4. 重復(3),直到所有頂點都在一顆樹內或者有n-1條邊為止。
3、算法過程
? ? ? ? ? ? ? ? ? ? ?
? ? ?
5、最小生成樹算法的應用
比如要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，因為鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這個時候需要找到帶權的最小生成樹，來解決這個問題。
?
二、拓撲排序
1、定義
由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
2、AOV網
在工程領域，一個大的工程通常會被劃分為許多較少的子工程，當子工程都完成了，那么整個大工程也就完成了。若以頂點表示活動，用有向邊表示子工程之間的優先關系。這樣的有向圖以頂點表示活動的網就是AOV網。AOV網表示了子工程之間的優先關系，也是活動進行時的制約關系。
3、拓撲排序
拓撲排序是將AOV網中所有的頂點排成一個線性序列的過程。并且滿足：若在AOV網中從頂點A到B有一條路徑，那么A比然在B之前。
4、執行步驟
(1) 選擇一個入度為0的頂點并輸出之；
(2) 從網中刪除此頂點及所有出邊。
循環結束后，若輸出的頂點數小于網中的頂點數，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。?
IT技術分享社區
個人博客網站：https://programmerblog.xyz
文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識
