連通演算法
1. 請問，在計算機圖形學中，四連通演算法填充時，種子會會重復入棧嗎
會啊，它入棧的順序是左上右下如有疑問請加429198063一起商討
2. 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-二值圖像連通域分析
數字圖像處理技術 ——鄧繼忠（我的任課老師）
3. 用C語言編寫求有向圖有多少連通圖的演算法（數據結構題目）
深度優先搜索。
http://www.cnblogs.com/dzkang2011/p/bfs_dfs.html
#include<iostream>
#include<cstdio>
usingnamespacestd;
#definemaxn100//最大頂點個數
intn,m;//頂點數，邊數
structarcnode//邊結點
{
intvertex;//與表頭結點相鄰的頂點編號
intweight=0;//連接兩頂點的邊的權值
arcnode*next;//指向下一相鄰接點
arcnode(){}
arcnode(intv,intw):vertex(v),weight(w),next(NULL){}
arcnode(intv):vertex(v),next(NULL){}
};
structvernode//頂點結點，為每一條鄰接表的表頭結點
{
intvex;//當前定點編號
arcnode*firarc;//與該頂點相連的第一個頂點組成的邊
}Ver[maxn];
voidInit()//建立圖的鄰接表需要先初始化，建立頂點結點
{
for(inti=1;i<=n;i++)
{
Ver[i].vex=i;
Ver[i].firarc=NULL;
}
}
voidInsert(inta,intb,intw)//尾插法，插入以a為起點，b為終點，權為w的邊，效率不如頭插，但是可以去重邊
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)//如果不要去重邊，去掉這一段
{
if(p->weight<w)
p->weight=w;
return;
}
while(p->next!=NULL)
{
if(p->next->vertex==b)//如果不要去重邊，去掉這一段
{
if(p->next->weight<w);
p->next->weight=w;
return;
}
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb,intw)//頭插法，效率更高，但不能去重邊
{
arcnode*q=newarcnode(b,w);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidInsert(inta,intb)//尾插法，插入以a為起點，b為終點，無權的邊，效率不如頭插，但是可以去重邊
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
if(p->vertex==b)return;//去重邊，如果不要去重邊，去掉這一句
while(p->next!=NULL)
{
if(p->next->vertex==b)//去重邊，如果不要去重邊，去掉這一句
return;
p=p->next;
}
p->next=q;
}
}
voidInsert2(inta,intb)//頭插法，效率跟高，但不能去重邊
{
arcnode*q=newarcnode(b);
if(Ver[a].firarc==NULL)
Ver[a].firarc=q;
else
{
arcnode*p=Ver[a].firarc;
q->next=p;
Ver[a].firarc=q;
}
}
voidShow()//列印圖的鄰接表（有權值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->("<<p->vertex<<","<<p->weight<<")";
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
voidShow2()//列印圖的鄰接表(無權值）
{
for(inti=1;i<=n;i++)
{
cout<<Ver[i].vex;
arcnode*p=Ver[i].firarc;
while(p!=NULL)
{
cout<<"->"<<p->vertex;
p=p->next;
}
cout<<"->NULL"<<endl;
}
}
#defineINF999999
boolvisited[maxn];//標記頂點是否被考察，初始值為false
intparent[maxn];//parent[]記錄某結點的父親結點，生成樹，初始化為-1
intd[maxn],time,f[maxn];//時間time初始化為0，d[]記錄第一次被發現時，f[]記錄結束檢查時
voiddfs(ints)//深度優先搜索（鄰接表實現），記錄時間戳，尋找最短路徑
{
cout<<s<<"";
visited[s]=true;
time++;
d[s]=time;
arcnode*p=Ver[s].firarc;
while(p!=NULL)
{
if(!visited[p->vertex])
{
parent[p->vertex]=s;
dfs(p->vertex);
}
p=p->next;
}
time++;
f[s]=time;
}
voiddfs_travel()//遍歷所有頂點，找出所有深度優先生成樹，組成森林
{
for(inti=1;i<=n;i++)//初始化
{
parent[i]=-1;
visited[i]=false;
}
time=0;
for(inti=1;i<=n;i++)//遍歷
if(!visited[i])
dfs(i);
cout<<endl;
}
intmain()
{
inta,b;
cout<<"Enternandm：";
cin>>n>>m;
Init();
while(m--)
{
cin>>a>>b;//輸入起點、終點
Insert2(a,b);//插入操作
}
Show2();//鄰接表
dfs_travel();//遍歷
intcnt=0;//連通圖個數
for(inti=1;i<=n;i++)
if(parent[i]==-1)
cnt++;
printf("%d ",cnt);
return0;
}
4. 強連通分量的Tarjan演算法思路
這個演算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼其實，我們只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那麼剩下的問題就只剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。
那麼如何確定強連通分量的根，在這里我們維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那麼，當前頂點就是一個強連通分量的根，為什麼呢？因為如果它不是強連通分量的根，那麼它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那麼存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。
至於如何拿出強連通分量，這個其實很簡單，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。現 在知道如何拿出了強連通分量了吧？是的，因為當前節點是這個強連通分量中最先被壓入堆棧的，那麼在當前節點以後壓入堆棧的並且仍在堆棧中的節點都屬於這個強連通分量。當然有人會問真的嗎？假設一個節點在當前節點壓入堆棧以後壓入並且還存在，同時它不屬於該強連通分量，那麼它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。現 在沒有疑問了吧，那麼演算法介紹就完了。
5. 強連通分量的Gabow演算法思路
這個演算法其實就是Tarjan演算法的變異體，我們觀察一下，只是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan演算法裡面的indx[]和mlik[]數組。那麼，我們說一下如何使用第二個堆棧來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan演算法中，每次mlik[i]的修改都是由於環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裡面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那麼Gabow演算法中的第二堆棧變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那麼只要出棧一直到棧頂那個頂點的訪問時間不大於深度最低的那個頂點。其中每個被彈出的節點屬於同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan演算法有了解的都應該清楚，那麼Tarjan演算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。
現 在，你應該明白其實Tarjan演算法和Gabow演算法其實是同一個思想的不同實現，但是，Gabow演算法更精妙，時間更少(不用頻繁更新mlik[])。 Gabow_Algorithm:
步驟1:
找一個沒有被訪問過的節點v，goto step2(v)。否則，演算法結束。
步驟2(v):
將v壓入堆棧stk1[]和stk2[]
對於v所有的鄰接頂點u：
1) 如果沒有訪問過，則step2(u)
2) 如果訪問過，但沒有刪除，維護stk2[](處理環的過程)
如果stk2[]的頂元素==v，那麼輸出相應的強連通分量 C++：#include<iostream>usingnamespacestd;constintMAXN=110;typedefintAdjTable[MAXN];//鄰接表類型intn;intintm[MAXN];//標記進入頂點時間intbelg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量intstk1[MAXN];//輔助堆棧intstk2[MAXN];//輔助堆棧AdjTableadj[MAXN];//鄰接表//深搜過程,該演算法的主體都在這里voidVisit(intcur,int&sig,int&scc_num){inti;intm[cur]=++sig;stk1[++stk1[0]]=cur;stk2[++stk2[0]]=cur;for(i=1;i<=adj[cur][0];++i){if(0==intm[adj[cur][i]]){Visit(adj[cur][i],sig,scc_num);}elseif(0==belg[adj[cur][i]]){while(intm[stk2[stk2[0]]]>intm[adj[cur][i]]){--stk2[0];}}}if(stk2[stk2[0]]==cur){--stk2[0];++scc_num;do{belg[stk1[stk1[0]]]=scc_num;}while(stk1[stk1[0]--]!=cur);}}//Gabow演算法,求解belg[1..n],且返回強連通分量個數,intGabow_StronglyConnectedComponent(){inti,sig,scc_num;memset(belg+1,0,sizeof(int)*n);memset(intm+1,0,sizeof(int)*n);sig=0;scc_num=0;stk1[0]=0;stk2[0]=0;for(i=1;i<=n;++i){if(0==intm[i]){Visit(i,sig,scc_num);}}returnscc_num;}Pascalproceretarjan(r:longint);varx,i,j:longint;begininc(timez);time[r]:=timez;low[r]:=timez;inc(top);zh[top]:=r;fori:=p1[r]top2[r]dobeginj:=e[i].y;iftime[j]=0thentarjan(j);iflow[j]<low[r]thenlow[r]:=low[j];end;iftime[r]=low[r]thenrepeatx:=zh[top];num[x]:=r;low[x]:=n+1;//這句話千萬別忘了dec(top);untilx=r;end;
6. 已知一個圖的連接矩陣，判斷給定兩個節點是否連通的演算法思想
用深度優先搜索，從給定節點開始，遍歷一遍所有節點，如果另一個節點遍歷到了，就連同，反之不連通
如果要算出所有節點，則每個節點都執行一次DFS，把結果存在一個二維數組里，就能查詢了！
7. sparkgraphx的連通分支演算法有什麼作用
連通分支演算法使用最小編號的頂點來標記每個連通分支。在一個社會網路，連通圖近似簇。這里我們計算一個連通分支實例，所使用的數據集和PageRank一樣。