频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
020-寻找图的关节点-dfs
2016-07-01 09:43:34         来源:zxCan的博客  
收藏   我要投稿

关节点的定义:

在多于两个顶点的无向图G中,存在一个顶点v,如果有不同于v的两个顶点u和w,在u和w间的任何路径都必定经过顶点v,则称v为关节点。

一种更形象的说法:

关节点也叫割点,连通图中删去割点会被分割成几个连通分量。

 

我们可以通过dfs来寻找关节点。

基本思路:

在图G上进行一个dfs,遍历过程中对每个顶点v保持两个标号α[v]和β[v],α[v]为dfs的深度,β[v]初始化为α[v]在遍历过程中修改为下列几个中的最小值:

1.α[v];

2.α[u],对于每个顶点u,(v,u)是回边;

3.β[w],在dfs树中的每条边(v,w)。

关节点确定如下:

1.根是一个关节点当且仅当在dfs树中,它有两个或更多的儿子。

2.根以外的顶点v是一个关节点当且仅当v有一个儿子w,使得β[w]>=α[v]。

 

伪代码:

\

\

 

 

C++代码:

来自http://www.xuebuyuan.com/1479536.html

 

#include 
#include 

#define VERTEX_NUM	7
#define NOT_VISITED 0

int dfn;//表示某顶点在深度优先遍历中被访问的顺序
void find_articulation(int adj[][VERTEX_NUM], int visit[], int low[]);//寻找图的关节点,并输出
void DFS_articulation(int adj[][VERTEX_NUM], int vertex, int visit[], int low[]);//从vertex顶点出发,查找并输出关节点

int main()
{
	//无向连通图的邻接表数据,-1表示结束
	int Adj[VERTEX_NUM][VERTEX_NUM] = {
		{0, 1, 3, -1},
		{1, 0, 2, 3, 4, -1},
		{2, 1, 3, 4, 5, -1},
		{3, 0, 1, 2, 4, -1},
		{4, 1, 2, 3, 5, -1},
		{5, 4, 6, -1},
		{6, 5, -1}		
	};
	
	int low[VERTEX_NUM];//low[]数组的意义见上面的分析
	int visit[VERTEX_NUM];
	for (int i = 0; i < VERTEX_NUM; i++)
		visit[VERTEX_NUM] = NOT_VISITED;

	//查找图的关节点,并输出
	find_articulation(Adj, visit, low);

	system("pause");
	return 0;
}

void find_articulation(int adj[][VERTEX_NUM], int visit[], int low[])	//visit[i]保存顶点i被访问的顺序
{
	dfn = 1;
	visit[adj[0][0]] = 1;//设adj[0][0]顶点为生成树的根
	for (int i = 1; i < VERTEX_NUM; i++)
		visit[i] = NOT_VISITED;

	int vertex = adj[0][1];	
	DFS_articulation(adj, vertex, visit, low);

	if (dfn < VERTEX_NUM)	//生成树的根至少有两棵子树
	{
		printf("%d  ", vertex);//输出关节点
		for (int j = 1; adj[0][j] != -1; j++)
			if (visit[adj[0][j]] == NOT_VISITED)
				DFS_articulation(adj, adj[0][j], visit, low);
	}
}

void DFS_articulation(int adj[][VERTEX_NUM], int vertex, int visit[], int low[])
{
	dfn++;
	int min = dfn;
	visit[vertex] = dfn;

	for (int j = 1; adj[vertex][j] != -1; j++)
	{
		int w = adj[vertex][j];
		if (visit[w] == NOT_VISITED)
	
点击复制链接 与好友分享!回本站首页
相关TAG标签 关节点
上一篇:《数据结构》复习之线性表(顺序表和链表)
下一篇:如何在Ruby中编写微服务?
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站