CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – 关节点(割点)和重连通分量

leave a comment »


对于一个连通图,如果删除了结点v以及相关联的边之后,图被分割成了两个或以上的连通分量,则称v是该图的一个关节点(articulation point),也叫割点

如果一个图中不存在关节点(割点),则该图为重连通图(biconnected graph)。显然重连通图是很稳定的,例如一个航空网络是重连通的,则当某调航线因为外部条件被破坏,那么旅客总可以从别的航线绕道到达目的地。

如果在连通图上至少要删除k个顶点才能破坏图的连通性,则称此图的连通度为k

对于如下的连通图G:

我们进行DFS遍历,得到如下的一棵深度优先遍历树:

实线是邻接点组成的父亲、孩子关系。虚线是回边连接的祖先、结点关系。

如果仔细观察的话,我们可以得到如下两条结论:

1、对任意顶点v,它的双亲结点和会变连接的祖先结点是它之前搜索到的邻接点。

2、对于任意顶点v,它的孩子结点是在v之后搜索到的邻接点。

为此,我们可以用visit[v]表示访问到v时是第几个号(如果从访问的第一个结点开始算1的话)。若访问到v时,它的邻接点w已经访问过,则w是v的双亲结点或回边连接的(DFS优先树的)祖先结点。如果w未曾访问过,则w是v的(DFS优先树)孩子结点。

我们还可以得到如下两个结论:

1、若生成树的根有两棵或以上的子树,则此顶点必为割点。

2、若生成树中某个非叶子结点v,其某棵子树的根和子树中其他结点均没有指向v的祖先的回边,则v为关节点。

为此我们可以再定义一个数组low[v] = Min(low[w], visit[v], visit[k]),其中w是v的(DFS树的)孩子结点,k是v的(DFS树的)回边连接的祖先结点。

由此,若low[w] >= visit[v],v必为割点。

我们可以用改造的DFS算法求出图中的所有割点

int count = 1;

void graph_dfs_inner(struct Graph* g, int* visit, int* low, int v)
{
	struct Arc* ptr = g->vexs[v].first_arc;
	int min = visit[v] = ++count;
	while(ptr!=NULL)
	{
		if(!visit[ptr->ivex])
		{
			// ptr is v's child
			graph_dfs_inner(g, visit, low, ptr->ivex);
			if(low[ptr->ivex]<min)
			{
				min = low[ptr->ivex];
			}
			if(low[ptr->ivex]>=visit[v])
			{
				printf("Gedian: %d\n", g->vexs[v].data);
			}
		} else
		{
			// ptr is v's ans
			if(visit[ptr->ivex]<min)
			{
				min = visit[ptr->ivex];
			}
		}
		ptr = ptr->next;
	}
	low[v] = min;
}

void graph_dfs(struct Graph* g)
{
	struct Arc* ptr = NULL;
	int i;
	int visit[MAX_VEXS];
	int low[MAX_VEXS];
	memset(visit, 0, sizeof(int)*MAX_VEXS);
	memset(low, 0, sizeof(int)*MAX_VEXS);
	visit[0] = count = 1;
	ptr = g->vexs[0].first_arc;
	graph_dfs_inner(g, visit, low, ptr->ivex);
	if(count < g->nvexs)
	{
		// Root has at least two sub-tree, is gedian
		printf("Gedian: %d\n", g->vexs[0].data);
		while(ptr!=NULL)
		{
			if(!visit[ptr->ivex])
			{
				graph_dfs_inner(g, visit, low, ptr->ivex);
			}
			ptr = ptr->next;
		}
	}
}

测试数据,以本文前面的连通图为例:

13
1
2
3
4
5
6
7
8
9
10
11
12
13
17
1 2
1 3
1 6
1 12
2 3
2 4
2 7
2 8
2 13
4 5
7 9
7 11
7 8
8 11
10 12
10 13
12 13

割点:

Gedian: 4
Gedian: 2
Gedian: 7
Gedian: 2
Gedian: 1

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3433

Written by cwyalpha

六月 13, 2012 在 4:45 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: