当前位置：搜档网 › 图的连通性总结

图的连通性总结

boboo

1.图的遍历及应用

1.1.DFS遍历

1.2.DFS树的边分类

1.3.DFS树的性质

1.4.拓补排序

1.5.欧拉回路

2.无向图相关

2.1求割顶

2.2求图的桥

2.3求图的块

3.有向图相关

3.1求强连通分量（SCC划分）

3.2求传递闭包

4.最小环问题

一、图的遍历及应用

1.1 DFS遍历

DFS是求割顶、桥、强连通分量等问题的基础。

DFS对图进行染色，

白色：未访问；

灰色：访问中（正在访问它的后代）；

黑色：访问完毕

一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。

-发现时间D[v]:变灰的时间

-结束时间f[v]:变黑的时间

-1<=d[v]

伪代码：

DFS(G)

for every vertex u ∈ V[G] do

color[u] = WHITE

π[u] = NIL

time = 0

for every vertex u ∈ V[G] do

if color[u] = WHITE then DFS_VISIT(u)

DFS_VISIT(u)

color[u] = GRA Y

d[u] = time += 1

for every vertex v ∈ Adj[u] do

if color[v] = WHITE then

π[v] = u

DFS_VISIT(v)

color[u] = BLACK

f[u] = time += 1

1.2 DFS树的边分类

在深度优先遍历中，我们所关心的另一个问题是对产生的搜索树中的分进行分类，这种分类可以发现图中的很多重要信息。一般地，我们可以把图G所产生的深度优先搜索树（或森林）的边分为四类：

A）树枝：深度优先搜索树G中普通的边，即如果结点v在搜索边(u, v)时第一次被发现，那么边(u, v)就是一个树枝。

B）反向边：深度优先搜索树中连结结点u到它的祖先v的那些边，自环也被认为是反向边。

C）正向边：深度优先搜索树中连接顶点u到它的后裔的非树枝的边。

D）交叉边：所有其它类型的边，它们可以连结同一棵深度优先搜索树中的两个结点，只要一结点不是另一结点的祖先（一般来讲两个结点是一种兄弟关系），也可以连结分属两棵深度优先搜索树的结点。

我们可以把DFS遍历算法做一下补允，使之遇到边时能对其进行分类。算法的核心思想在于可以根据第一次被搜索的边所达到的结点v的颜色来对该边(u, v)进行分类（但正向边和交叉分不能用颜色区分出）。

1、白色表明它是树枝。

2、灰色表明它是反向边。

3、黑色表明它是正向边或交叉边，其中，如果d[u] < d[v]，则边(u, v)就是正向边；

反之，或d[u] > d[v]，则(u, v)就是交叉边。

上述证明比较简单，可根据定义证明。另外，如果图G为无向图的话，那么G的深度优先搜索树中的边只能是树枝或反向边。

在程序具体使显示颜色值以及时间戳可以省略, 用意义更加明确的pre数组和post代替d 和f数组, pre[u]和post[u]代表点u的先序/后序编号, 则检查

(u,v)可以写为

if (pre[v] = -1) then dfs(v) //树边, 递归遍历

else if (post[v] = -1) then show(“B”) //后向边

else if (pre[v] > pre[u]) then show(“F”) // 前向边

else show(“C”); // 交叉边

? pre和post的初值均为-1(0), 方便了判断

程序实现：

1.3 DFS树的性质

?括号结构性质

对于任意结点对(u, v), 考虑区间[d[u], f[u]]和[d[v], f[v]], 以下三个性质恰有一个成立:

–完全分离

– u的区间完全包含在v的区间内, 则在dfs树上u是v的后代

– v的区间完全包含在u的区间内, 则在dfs树上v是u的后代

?定理1(嵌套区间定理):

在DFS森林中v是u的后代当且仅当d[u]

?定理2(白色路径定理):

在DFS森林中v是u的后代当且仅当在d[u]时刻(u刚刚被发现), v可以由u出发只经过白色结点到达. 证明: 由嵌套区间定理可以证明

1.4 拓补排序

算法一：

?对图G使用DFS算法, 每次把一个结点变黑的同时加到链表首部

?定理1: 有向图是DAG当且仅当没有B边

–如果有B边, 有环(易证)

–如果有环c, 考虑其中第一个被发现的结点v, 环中v的上一个结点为u, 则沿环的路径v u是白色路径, 有白色路径定理, u是v的后代, 因此(u,v)是B边

?定理2: 该算法正确的得到了一个拓扑顺序

算法二：

其实还有更方便的方法，不必进行dfs遍历，统计入度的情况即可。

程序实现：(这里只给出DFS的方法)

1.5 欧拉回路

每条边经过一次且仅一次的路径。

经典的递归实现.

算法：从一个点u出发DFS，每次标记边(u,v)和(v,u)，递归调用EulerRoute(v)，然

后把(u,v)放到栈中.

程序实现：

二、无向图相关

2.1 求割顶

割顶是去掉后让无向图不再连通的点。

求割顶的算法在DFS遍历的算法上形成。

什么样的点是割顶？

在一棵DFS树中，

1.根root是割顶 ------------- 它至少有两个儿子

2.其他点v是割顶 ------------- 它有一个儿子u, 从u或者u的后代出发没有指向v祖先(不含v)的B边, 则删除v以后u和v的父亲不连通, 故为割顶。

割顶判定算法:

引入lowlink数组为从当前点以及它的后代所能到达的点的开始访问时间的最小值。

Lowlink [u]= Min { pre[u]

Pre[v] (u,v)是后向边

Lowlink [v] (u，v）是树边，u在dfs树中是v的父亲 }

–对于DFS树根, 判断度数是否大于1

–对于其他点u, 如果不是根的直接儿子, 且Lowlink[u] >= d[P[u]], 则它的父亲v=P[u]是割点。

程序实现

2.2 求图的桥

桥（割边）是去掉后让无向图不再连通的边。

求割边的算法也在DFS遍历的算法上形成。

什么样的边是桥（割边）？

边(u,v)为桥当且仅当它不在任何一个简单回路中。

发现树边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的后向边, 则删除(u,v)后u和v不连通, 因此(u,v)为桥。

桥（割边）的判定算法：

发现树边(u, v)时若Lowlink[v]>d[u](注意不能取等号,区别于求割顶), 则(u,v)为桥

实际代码是测试若lowlink[v]=pre[v]则(u,v)是桥

程序实现

2.3 求图的块

一些连通性的基本定义：

?点连通度(等价性: Whitney定理)

–定义1: 把图变非连通所需删除的最少点数

?1-连通: 一般连通

?2-连通: 双连通, 删除一个点后仍连通(无割顶)

–定义1: 把图变非连通所需删除的最小边数

–定义2: 任意两个点至少有k个不含相同边的路(edge-disjoint path).

块的定义以及性质：

一个图的块(biconnectedcomponent, bcc)是双连通的极大子图。

块与块之间没有公共边，以割顶相连。

?性质1. 每条边都包含在某个BCC中. 证明: 对于(u, v), {u, v}是双连通的, 这是某BCC的一部分

?性质2. 不同的两个BCC最多有一个公共结点, 此结点是原图的割顶

?性质3. 不同的两个BCC不含公共边. 证明: 如果有相同边, 则含有两个公共结点.

?根据性质2和性质3可知: BCC是G的边划分

块可以表示成点或边的集合。

一个显而易见的算法：

先求出所有的割顶，去掉后，对不是割顶的点进行种子染色法（此时要把割顶当成不能再扩展的边界），这样就可以得到所有的块了。

有没有更快更直接的方法呢？

有！

求块的算法：

?在求割点的算法中，我们找到割点u时，我们把u下方的整块和u导出作为图中的一个块。

?程序实现时用栈即可。

程序实现：

（用floodfill）（用栈）

三、有向图相关

3.1求强连通分量（SCC划分）

在有向图中，如果结点u 可达到结点v ，并不意味着结点v 也可达到结点u ，如果两个结点相互可达，那么称这两个结点处于同一个强连通分量（Strongly Connected Component, SCC ）。

SCC 有一个比较有趣的性质，即：图G 的SCC 与G 的转制G T

的SCC 相同。如果把SCC 的每个分量都收缩成一个点，那么，生成的图为一个DAG 。

有关求有向图SCC 划分的算法有很多，其中各有特点，也都比较优美，效率都还不错，实现起来也比较简单，同时，SCC 划分也是有向图一个很基本但重要的算法，要熟练掌握，这里记录三种算法。

? Kosaraju 算法

这个算法是一个应用了SCC 图转制的性质与拓扑排序的一些思想的算

法，整体算法非常之优美，是一个精美的算法，同时实现起来也非常简单，

思想也不难理解。这里就直接给出整体思想，具体证明目前先从略，待以后

补上。

Kosaraju-SCC(G)

1、调用DFS(G)以计算出每个结点的完成时刻f[u]；

2、计算出G T ；

3、调用DFS(G T )，但在DFS 的主循环按f[u]递减的顺序访问各结

点；

4、输出3中产生的深度优先森林中每棵树的结点，作为各自独立

的SCC 。

这个算法需要做两次DFS ，而且需要做一个图的转制，时间复杂度为：

O (V +E )。虽然这个复杂度渐进意义上是不错的，但是其中的常数较高，效

率较其它的求SCC 划分的算法稍差。

? T arjan 算法

这个算法是建立在图的DFS 遍历基础上的。首先，它对每个图G 中的

点v 定义了一个low 函数（这个函数比较重要，在求图的割顶与桥等多种算

法中也要用到），定义如下： ()

),(][][min ][w u u v w w d v d v low 所连的某条后向边的后裔为???=

定义这个函数以后，我们就可以得如出下性质：处于同一强连通分量里的点

u 与v 的low 函数值相同。根据这个性质，对DFS 算法改进一下后，求出每

个点的low 函数值，进而也就可以求出图的强连通分量了，伪代码如下：

Tarjan-SCC(G)

for every vertex u ∈ V[G] do

color[u] = WHITE

time = 0

for every vertex u ∈ V[G] do

if color[u] = WHITE then VISIT(u)

VISIT(u)

min = low[u] = time += 1

color[u] = GRA Y

for every vertex v ∈ Adj[u] do

if color[v] = WHITE then

visit(v)

else if (color[v] = GRA Y) and (low[v] < min) then

min = low[v]

if min < low[u] then low[u] = min

color[u] = BLACK

很显然，算法的时间复杂度为：O(V+E)，整个算法只执行一遍DFS遍历，相对比Kosaraju算法效率稍高，整体实现起来也很简单，可以做为一

个实用的求图SCC划分的算法。

?Gabow算法

Gabow算法使用另一个栈P保留当前路径中的结点, 发现反向边(u,v)后不

断出栈, 只保留v

程序实现：（输出的都是最大的强连通分量中的点个数）

3.2 求传递闭包

?对于图G的任意一个结点u, u可达的结点集合称为u的传递闭包

一个简单快捷的方法：

用Floyd，再枚举判断。时间复杂度：O（n^3）.

更快更好的方法：

区别对待有向图与无向图：

?无向图:

u的传递闭包为和u处于同一连通分量的点集，floodfill即可

?有向图:

先求SCC图, 则u的传递闭包为u所处SCC和它的所有后代SCC中的结点，因此对于有向图只需在SCC划分的程序基础上完成即可。具体操作时：建立起SCC划分后的新图，新图是一棵树，从此点所属的SCC拓展即可，它及每个后代SCC中的所有点即为这个点的传递闭包。

程序实现：有向图的情况，且用的是tarjan算法。

四、最小环问题

简要介绍它的两种算法：

1.删边求最短路，每条边都要求一次，最短路可用dijkstra 或spfa；

2.floyd算法的基础上实现：

pascal代码：

For k:=1 to n do

Begin

For i:=1 to k-1 do

For j:=i+1 to k-1 do

Ans:=Min(ans,d[I,k]+d[j,k]+a[I,j]);

For i:=1 to n do

For j:=1 to n do

D[I,j]:=Min(d[I,j],d[I,k]+d[k,j]);

End;

程序实现：（算法二）

(ural 1004)

图的连通性总结

图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量（SCC划分） 3.2求传递闭包 4.最小环问题

一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色，白色：未访问；灰色：访问中（正在访问它的后代）；黑色：访问完毕一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v]

基于matlab的图像识别与匹配

基于matlab的图像识别与匹配摘要图像的识别与匹配是立体视觉的一个重要分支，该项技术被广泛应用在航空测绘，星球探测机器人导航以及三维重建等领域。本文意在熟练运用图像的识别与匹配的方法，为此本文使用一个包装袋并对上面的数字进行识别与匹配。首先在包装袋上提取出来要用的数字，然后提取出该数字与包装袋上的特征点，用SIFT方法对两幅图进行识别与匹配，最终得到对应匹配数字的匹配点。仿真结果表明，该方法能够把给定数字与包装袋上的相同数字进行识别与匹配，得到了良好的实验结果，基本完成了识别与匹配的任务。

1 研究内容图像识别中的模式识别是一种从大量信息和数据出发，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别、评价的过程。图形辨别是图像识别技术的一个重要分支，图形辨别指通过对图形的图像采用特定算法，从而辨别图形或者数字，通过特征点检测，精确定位特征点，通过将模板与图形或数字匹配，根据匹配结果进行辨别。 2 研究意义数字图像处理在各个领域都有着非常重要的应用，随着数字时代的到来，视频领域的数字化也必将到来，视频图像处理技术也将会发生日新月异的变化。在多媒体技术的各个领域中，视频处理技术占有非常重要的地位，被广泛的使用于农业，智能交通，汽车电子，网络多媒体通信，实时监控系统等诸多方面。因此，现今对技术领域的研究已日趋活跃和繁荣。而图像识别也同样有着更重要的作用。 3 设计原理 3.1 算法选择 Harris 角点检测器对于图像尺度变化非常敏感，这在很大程度上限制了它的应用范围。对于仅存在平移、旋转以及很小尺度变换的图像，基于Harris 特征点的方法都可以得到准确的配准结果，但是对于存在大尺度变换的图像，这一类方法将无法保证正确的配准和拼接。后来，研究人员相继提出了具有尺度不变性的特征点检测方法，具有仿射不变性的特征点检测方法，局部不变性的特征检测方法等大量的基于不变量技术的特征检测方法。 David.Lowe 于2004年在上述算法的基础上，总结了现有的基于不变量技术的特征检测方法，正式提出了一种基于尺度空间的，对图像平移、旋转、缩放、甚至仿射变换保持不变性的图像局部特征，以及基于该特征的描述符。并将这种方法命名为尺度不变特征变换（Scale Invariant Feature Transform），以下简称SIFT 算法。SIFT 算法首先在尺度空间进行特征检测，并确定特征点的位置和特征点所处的尺度，然后使用特征点邻域梯度的主方向作为该特征点的方向特征，以实现算子对尺度和方向的无关性。利用SIFT 算法从图像中提取出的特征可用于同一个物体或场景的可靠匹配，对图像尺度和旋转具有不变性，对光照变化、

matlab判别图的连通性

《数学文化》课程报告题目：MATLAB判别图的连通性 2016年 11月26日

MATLAB判别图的连通性摘要图论中，在无向图G中，结点u和v之间若存在一条路，则称结点u和结点v是连通的。若图G只有一个连通分支，则称G是连通图。如果两点相邻接，则在矩阵中记为1，否则记为0，形成的矩阵称为邻接矩阵。若两点相互连通，则记为1，否则记为0，形成的矩阵称为可达性矩阵。用矩阵表示图，可以在matlab中进行计算关键词：连通性；matlab；矩阵；可达性

实验目的给定n个结点的有向图，判断图的连通性，如果是连通图，判断是强连通图、弱连通图还是单侧联通图实验原理与数学模型对于给定的邻接矩阵A，求出A所表示的图的可达矩阵P。对于可达矩阵P 来说，如果P的所有元素均为1，则所给的有向图是强连通的；对于P的所有元素（除主对角线元素外）Pij来说，均有：Pij+Pji>0，则所给有向图是单向连通的。当所给有向图既不是强连通的，又不是单向连通的时候，我们改造邻接矩阵为：对于矩阵A中所有的元素（除主对角线的元素外）aij，若aij=1或aji=1，则1?aij且1?aji。对于这样改造之后所得到的新的矩阵A’（A’相当于原有向图忽略方向之后所得到的无向图的邻接矩阵），再用前面所述的方法进行判断，当P’的所有元素（除主对角线的元素外）均为1时，原有向图是弱连通图；否则，原有向图是不连通的。实验内容（要点） 1．通过图的邻接矩阵计算可达性矩阵 2．通过可达性矩阵判断图的连通性 3．如果是连通图，判断图是强连通图、弱连通图还是单侧连通图实验过程记录计算可达性矩阵函数 function P=canget(A) n=length(A); P=A; for i=2:n P=P+A^i; end P=(P~=0); 主程序 clear A=input('Enter an Adjacency Matrix:'); P=canget(A);

基于MATLAB的图像处理字母识别

数字图像处理报告名称：字母识别学院：信息工程与自动化学院专业：物联网工程学号：201310410149 学生姓名：廖成武指导教师：王剑日期：2015年12月28日教务处制

目录字母识别 1.---------------------测试图像预处理及连通区域提取 2.---------------------样本库的建立采集feature 3.---------------------选择算法输入测试图像进行测试 4.---------------------总结

字母识别 1.imgPreProcess（联通区域提取）目录下 conn.m：连通区域提取分割（在原图的基础上进行了膨胀、腐蚀、膨胀的操作使截取的图像更加接近字母） %%提取数字的边界，生成新的图 clear; clc; f=imread('5.jpg'); f=imadjust(f,[0 1],[1 0]); SE=strel('square',5); %%膨胀、腐蚀、膨胀 A2=imdilate(f,SE); SE=strel('disk',3) f=imerode(A2,SE) SE=strel('square',3); f=imdilate(f,SE); gray_level=graythresh(f); f=im2bw(f,gray_level); [l,n]=bwlabel(f,8) %%8连接的连接分量标注 imshow(f) hold on for k=1:n %%分割字符子句 [r,c]=find(l==k); rbar=mean(r); cbar=mean(c); plot(cbar,rbar,'Marker','o','MarkerEdgeColor','g','MarkerFaceColor',' y','MarkerSize',10); % plot(cbar,rbar,'Marker','*','MarkerEdgecolor','w'); row=max(r)-min(r) col=max(c)-min(c) for i=1:row for j=1:col seg(i,j)=1; end

图的连通性判断

基于MATLAB的实现，此方法可以知道有几个连通域,并且知道各个顶点的归属。Branches中显示各个节点的归属，同一行的为同一连通分支中的节点。其第一列为它的分类数。例如下图，有五个连通分支，1、2、3在同一个连通分支中。这是上图的邻接矩阵，同一节点间为0。 Branches中的显示内容，第一列为连通分支数，后边跟着的是给连通分支中的节点。第一行就表示1、2、3为一个连通分支，4自己在一个连通分支中等等。 function [Branches,numBranch]=Net_Branches(ConnectMatrix) % ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % This program is designed to count the calculate connected components in networks. % Usage [Cp_Average, Cp_Nodal] = Net_ClusteringCoefficients(ConnectMatrix,Type) % Input: % ConnectMatrix --- The connect matrix without self-edges. % Output: % Branches --- A matrix, each rows of which represents the

% different connected components. % numBranch --- The numbers of connected components in network % % +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % Refer: % Ulrik Barandes % Written by Hu Yong, Nov,2010 % E-mail: carrot.hy2010@https://www.sodocs.net/doc/0d12259312.html, % based on Matlab 2008a % Version (1.0),Copywrite (c) 2010 % Input check-------------------------------------------------------------% [numNode,I] = size(ConnectMatrix); if numNode ~= I error('Pls check your connect matrix'); end % End check---------------------------------------------------------------% Node = [1:numNode]; Branches = []; while any(Node) Quence = find(Node,1); %find a non-zero number in Node set subField=[]; %one component % start search while ~isempty(Quence) currentNode = Quence(1); Quence(1) = []; %dequeue subField=[subField,currentNode]; Node(currentNode)=0; neighborNode=find(ConnectMatrix(currentNode,:)); for i=neighborNode if Node(i) ~= 0 %first found Quence=[Quence,i]; Node(i)=0; end end end subField = [subField,zeros(1,numNode-length(subField))]; Branches = [Branches;subField]; %save end numBranch = size(Branches,1);