鄰接種子演算法

㈠ [圖] 最小生成樹-Prime演算法和Kruskal演算法

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。

4 .輸出：使用集合 V _new 和 E _new 來描述所得到的最小生成樹。

下面對演算法的圖例描述

反證法：假設prim生成的不是最小生成樹

這里記頂點數v，邊數e

鄰接矩陣:O(v ² )
鄰接表:O(e * log ₂ v)

Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有 Prime 演算法和 Boruvka 演算法等。三種演算法都是貪婪演算法的應用。和 Boruvka 演算法不同的地方是，Kruskal 演算法在圖中存在相同權值的邊時也有效。

圖例描述：

對圖的頂點數 n 做歸納，證明 Kruskal 演算法對任意 n 階圖適用。

歸納基礎：

n = 1，顯然能夠找到最小生成樹。

歸納過程：

假設 Kruskal 演算法對 n ≤ k 階圖適用，那麼，在 k + 1 階圖 G 中，我們把最短邊的兩個端點 a 和 b 做一個合並操作，即把 u 與 v 合為一個點 v'，把原來接在 u 和 v 的邊都接到 v' 上去，這樣就能夠得到一個 k階圖 G'(u ,v 的合並是 k + 1 少一條邊)，G' 最小生成樹 T' 可以用Kruskal 演算法得到。

我們證明 T' + {<u,v>} 是 G 的最小生成樹。

用反證法，如果 T' + {<u,v>} 不是最小生成樹，最小生成樹是 T，即W(T) < W(T' + {<u,v>})。顯然 T 應該包含 <u,v>，否則，可以用<u,v> 加入到 T 中，形成一個環，刪除環上原有的任意一條邊，形成一棵更小權值的生成樹。而T - {<u,v>}，是 G' 的生成樹。所以 W(T-{<u,v>}) <= W(T')，也就是 W(T) <= W(T') + W(<u,v>) = W(T'+{<u,v>})，產生了矛盾。於是假設不成立，T' + {<u,v>}是 G 的最小生成樹，Kruskal 演算法對 k+1 階圖也適用。

由數學歸納法，Kruskal 演算法得證。

e * log ₂ e (e為圖中的邊數)

㈡ 寫一個演算法，判斷對給定有向圖中的指定頂點是否至少存在一條有向邊指向它。

【答案】：(1)數據結構
採用有向圖的鄰接表(出邊表)表示法。
(2)思路
圖有3種表示方法：出邊表(鄰接表的一種)、入邊表(鄰接表的一種)和鄰接矩陣。相應的有3種演算法。設n為頂點數，m為邊數。
對於出邊表，順序搜索一遍邊即可，時間代價為O(m)。
對於入邊表，判斷指定頂點的邊表頭指針是否非空即可，時間代價為O(1)。
對於鄰接矩陣，搜索矩陣中指定頂點對應的列，判斷其中是否有非0元即可，時間代價為O(n)。
以出邊表為例，給出一個演算法如下。
(3)演算法
int is_end(GraphList g,int k){
/*判斷圖g中是否有邊指向第k個結點(0＜=k＜=g.n-1)*/
EdgeList p;
inti;
for(i=0;i＜g.n;i++){
p=g.vexs[i].edgelist;
while(p!=NULL){
if(p-＞endvex==i)return 1;
p=p-＞nextedge;
}
}
return 0;
}
(4)代價分析
該演算法的時間復雜度為O(m)。

㈢ NI Vision：二值圖像連通域標記演算法

前面說到，要使用Labwindows + NI Vision（IMAQ Vision）這套商用開發框架來做數圖課設。很明顯，這套虛擬儀器開發平台由NI Instrument（美國國家儀器公司）開發的。大名鼎鼎的Labview軟體就是這個公司開發的。相比較而言，Labwindows使用ANSI C開發，但應用場景是差不多的。

在做課程作業的時候，遇到了一個很有趣的應用。輸入是米粒，比背景灰度要低，目的是輸出米粒的顆數、面積、周長和孔數，這是工業上的一個很常見的應用。具體處理過程是二值化後使用低通濾波，並計算各種性質。

界面設計如下，可以看到米粒的詳細情況。

讓我感興趣的，是通過怎樣的演算法能夠得到米粒的數量？之前曾經用過OpenCV中找最大外界矩形這個函數，但沒有具體了解演算法實現。直覺告訴我原理應該是相似的。

可以看到，每一個米粒之間都是不連通的。這里就就提出了一個概念。 連通區域（Connected Component） 是指圖像中相鄰並有相同像素值的圖像區域。 連通區域分析（Connected Component Analysis,Connected Component Labeling） 是指將圖像中的各個連通區域找出並標記。

二值圖像分析最重要的方法就是連通區域標記，它是所有二值圖像分析的基礎，它通過對二值圖像中白色像素（目標）的標記，讓每個單獨的連通區域形成一個被標識的塊，進一步的我們就可以獲取這些塊的輪廓、外接矩形、質心、不變矩等幾何參數。如果要得到米粒的數量，那麼通過連通區域分析（這里是二值圖像的連通區域分析），就可以得到標記的數量，從而得到米粒的數量。

下面這幅圖中，如果考慮4鄰接，則有3個連通區域，8鄰接則是2個。

從連通區域的定義可以知道，一個連通區域是由具有相同像素值的相鄰像素組成像素集合，因此，我們就可以通過這兩個條件在圖像中尋找連通區域，對於找到的每個連通區域，我們賦予其一個唯一的 標識（Label） ，以區別其他連通區域。

連通區域分析的基本演算法有兩種：1）Two-Pass兩便掃描法 2）Seed-Filling種子填充法 。

兩遍掃描法（Two-Pass），正如其名，指的就是通過掃描兩遍圖像，就可以將圖像中存在的所有連通區域找出並標記。

說了一堆數學語言，其實用圖很好理解

種子填充方法來源於計算機圖形學，常用於對某個圖形進行填充。它基於區域生長演算法。至於區域生長演算法是什麼，可以參照我的這篇 文章 。

同樣的，上動圖

NI Vision 中的運算元定義如下

OpenCV中也有相應的運算元

這里參照其他博客實現一下Two-Pass演算法，Seed-Filling演算法就偷懶不搞了。

Reference:
OpenCV實現圖像連通組件標記與分析
OpenCV-二值圖像連通域分析
數字圖像處理技術 ——鄧繼忠（我的任課老師）