学步园

参考数据结构(C语言版)第七章，算法7.10和7.11

求解思路
1.深度优先生成树的根是关节点的充要条件是它至少有两个子女
2.任何其它顶点u是关节点的充要条件是u至少有一个子女w，使得经过只由w，w的后代以及一条回边构成的路径不可能到达u的祖先，因为删除顶点u及其关联的边将使w及其后代与u的祖先断开联系。

    假设顶点w的祖先包括w本身，为了表示一个顶点经过其后代以及一条回边所能到达的最高祖先，对于图的每个顶点w，定义low（w）为从w经过其后代以及一条回边所能到达的最高祖先的dfn（表示某顶点在深度优先遍历中被访问的顺序）。
    显然，low(w)是从w经过其后代以及一条回边所能到达的顶点的dfn中最低的，并可由下公式计算：

               low(w) = min {dfn(w), min {low(x)| x是w的一个子女}, min {dfn(x)| (w, x) 是一条回边}}

实现代码如下：(由于测试代码较少，程序很可能出错，希望发现错误的朋友及时指正)

#include <cstdio>
#include <cstdlib>

#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)
		{
			DFS_articulation(adj, w, visit, low);
			if (low[w] < min)
				min = low[w];
			if (low[w] >= visit[vertex])
				printf("%d  ", vertex);//输出关节点
		}
		else if (visit[w] < min)
			min = visit[w];//w已访问，w是vertex在生成树上的祖先
	}

	low[vertex] = min;
}

//运行结束时出现的问题:Stack around the variable 'visit' was corrupted

//解决办法
//把“project->配置属性->c/c++->代码生成->基本运行时检查 设置为默认值，就没有这样的错误了。
//关于MSDN的解释是在堆栈外面读写某数据。错误是名为RTC1的编译器检测的。又看了更多的技术文章，
//发现这样的错误是程序员在项目到了一定大的时候，它占用的堆栈量就比较大。我也深有体会。
//因为自己本来编写一个类，运行时没有错，但是在添加成员属性的时候，在其它方式不变的情况下就容易发生这样的错误。
//所以据此我猜应该是VS2005（2008）在内部就限定了堆栈的大小，当项目足够大的时候，就会溢出。