连通算法
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一样。