图的连通性

《数学文化》课程报告

题 目：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:');

论中的的遍历与连通性判断

教案主题：图的遍历与连通性判断

一、引言（150字）

图是一种重要的数据结构，它由节点和节点之间的边组成。在解决很多实际问题时，经常需要对图进行遍历与连通性判断。本教案将介绍深度优先遍历（DFS）和广度优先遍历（BFS）两种常用的图的遍历算法，并结合实例讲解如何判断图的连通性。

二、深度优先遍历（DFS）（500字）

1. DFS的概念与步骤

- DFS是一种递归算法，以深度优先的顺序遍历图的节点。

- DFS的步骤：从某个节点开始，访问该节点并标记为已访问，然后递归地访问该节点的未访问邻居节点，直到所有节点都访问过为止。

2. DFS的实现与应用

- 以邻接矩阵表示图的DFS实现方法。

- 利用DFS算法可以解决一些常见问题，如迷宫求解、搜索路径等。

三、广度优先遍历（BFS）（500字）

1. BFS的概念与步骤 - BFS是一种逐层遍历的算法，从起始节点开始，按广度优先的顺序访问图的节点。

- BFS的步骤：从起始节点开始，依次访问其邻居节点，并将其邻居节点加入到访问队列中，然后按队列中的顺序逐个访问队列中的节点，直到队列为空为止。

2. BFS的实现与应用

- 以邻接表表示图的BFS实现方法。

- 利用BFS算法可以解决一些常见问题，如社交网络中的人际关系分析、寻找最短路径等。

四、图的连通性判断（500字）

1. 连通性的概念

- 在无向图中，如果任意两个节点之间都存在路径，即可称之为连通图；否则称之为非连通图。

2. 图的连通性判断

- 判断无向图的连通性方法：选择一个节点作为起始节点，通过DFS或BFS遍历图，如果所有节点都被访问到，则图是连通的。

3. 连通分量的概念

- 对于非连通图，可以将其划分为多个连通分量。每个连通分量都是一个连通图。 五、实例分析：判断连通性和寻找连通分量（400字）

判断图的连通性

连通性判断

【试题描述】

⽆向图，包含n个节点编号1⾄n，初始没有边。 现在逐次向图中添加m条边，你需要在添加边之前判断该两点是否连通。

【输⼊要求】

第⼀⾏两个正整数n、m。

接下来m⾏，每⾏两个正整数x、y。

【输出要求】m⾏，每⾏包含⼀个整数0或1，0表⽰添加这条边之前两个点不连通，1表⽰连通。

【输⼊实例】4 5

1 2

1 3

2 3

4 4

3 4

【输出实例】0

0

1

1

0

【其他说明】n,m<=300000。

【试题分析】

⽤并查集做，这是⼀道全世界最⽔的图论题，直接不⽤说，上代码……

【代码】#include

using namespace std;

int x,y,f[301001],n,m;

int find(int x)

{

if (f[x]==x) return f[x];

return f[x]=find(f[x]);

}

void merge(int v,int u)

{

int t1,t2;

t1=find(v);

t2=find(u);

if(t1!=t2) f[t2]=t1;

return ;

}

inline int read()

{

int x,f=1;

char ch=getchar();

for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;

for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');

return x*f;

}

inline void write(int x)

{

if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;

int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;

for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;

function w=liantong(D)

%使用广度优先搜索判断图是否连通

%D是01关联矩阵，且对角线元素为1

L=size(D,1);

FOUND=zeros(1,0);

%数据初始化

v=1;%当前节点集为第一个节点

FOUND=[FOUND,v];

%删除当前节点相互之间的关联边

D(v,v)=0;

%找当前节点的相邻节点

p=D(v,:);

vv=find(p==1);%当前节点的相邻的节点

if length(vv)==0

w=0;

return

end

%修正邻接矩阵

D(v,:)=zeros(1,L);

D(:,v)=zeros(L,1);

FOUND=[FOUND,vv];

while length(find(FOUND))

v=vv;

clear vv;

LL=length(v);

%第一步：删除当前节点相互间的关联边

for i=1:LL

for j=1:LL

D(v(i),v(j))=0;

D(v(j),v(i))=0;

end

end

%第二步：找与当前节点的相邻接的节点

vv=zeros(1,0);

for i=1:LL

p=D(v(i),:);

pos=find(p==1);

vv=[vv,pos];

end

if length(vv)==0%如果没有邻接节点，说明不连通

w=0;

return

end

%第三步：修正邻接矩阵 for i=1:LL

D(v(i),:)=zeros(1,L);

D(:,v(i))=zeros(L,1);

end