连通图的关节点
对树中任意节点V而言，其孩子结点为在他之后搜索到的邻接点，而其双亲结点和由回边联结的祖先结点s是在他之前搜索到的邻接点。由深度优先生成树可以得出两类关节点的特性：
1，若生成树的根有两颗或两颗以上子树，则此跟顶点必为关节点。
2，若生成树中某个非叶子结点V，其某棵子树的根和子树中的其他结点都没有指向V的祖先的回边，则V为关节点。
辅助数组visited[v]的值即为v在深度优先生成树的前序序列中的序号。
辅助数组low[v]的值为后续优先生成树的序号。而v在后续序列中的次序号和遍历时退出DFS函数的次序号相同。
以下算法，如果顶点可以把图中的不同部分分成几个独立的子树，这个顶点有可能被多次输出。例如图中的B结点。删除它可以独立出两个不同的子块{D,E}和{G,H,I,K}所以B被输出了两次。
代码*********
#include “pch.h”
#include
#include
using namespace std;
class Graph
{
public:
char * vertex;//顶点集
bool * arc;//边集
int vertexnum;
int arcnum;
Graph(int _vertexnum = 0, int _arcnum = 0) :vertex(0), arc(0), vertexnum(0), arcnum(0) {};
~Graph()
{
delete[] vertex;
delete[]arc;
}
int location(char &v);//返回顶点的位置
int first(char &v);//顶点v的第一个邻接点。返回-1表示没有邻接点
int next(char &v, int k);//顶点v的 v–vertex[k] 之后的第一个邻接点
friend istream & operator>>(istream &is, Graph &g);
friend ostream &operator<<(ostream &os, Graph&g);
};
class asistant
{//辅助数组
public:
int *visited, *low,account=1;
asistant(int n = 0) :visited(new int[n]),low(new int[n]){};
~asistant()
{
delete[]visited;
delete[]low;
}
};
void dfsarticul(Graph &g, char &v,asistant &a);
void findarticul(Graph &g, asistant &a);
int main()
{
Graph g;
cin >> g;
cout << g << endl<<endl;
asistant a(g.vertexnum);
findarticul(g, a);
cout << endl;
return 0;
}
int Graph::location(char &v)
{//定位顶点
int i = 0;
for (; i < vertexnum; ++i)
{
if (vertex[i] == v)
break;
}
return i;
}
int Graph::first(char &v)
{
int i = location(v);//v的位置
int j = 0;
for (; j < vertexnum; ++j)
{
if (i >= j)//下三角中找到第一条有关系的边就退出
if (arc[i*(i + 1) / 2 + j])
break;
else
;
else
{
if (arc[j*(j + 1) / 2 + i])
break;
}
}
if (j < vertexnum) return j;
else
{
return -1;
}
}
int Graph::next(char &v, int k)
{
int i = location(v);//v的位置
int j = k+1;
for (; j < vertexnum; ++j)
{
if (i >= j)//下三角中找到第一条有关系的边就退出
if (arc[i*(i + 1) / 2 + j])
break;
else
;
else
{
if (arc[j*(j + 1) / 2 + i])
break;
}
}
if (j < vertexnum) return j;
else
{
return -1;
}
}
istream & operator>>(istream &is, Graph &g)
{
cout << “请输入顶点数量和边的数量：”;
is >> g.vertexnum >> g.arcnum;
cout << “请输入顶点集：” << endl;
delete[] g.vertex;
g.vertex = new char[g.vertexnum]; //为顶点集重新申请空间
if (!g.vertex) cout << “failure” << endl;
for (int i = 0; i < g.vertexnum; ++i)
is >> g.vertex[i];
delete[] g.arc;
g.arc = new bool[g.vertexnum*(g.vertexnum + 1) / 2];//三角矩阵压缩存储弧的关系集；
memset(g.arc, 0, g.vertexnum*(g.vertexnum + 1) / 2 * sizeof(bool));//初始空间设置为0，表示边之间没有关系。
char v, u;
int i, j;
for (int k = 0; k < g.arcnum; ++k)
{
is >> v >> u;
i = g.location(v);
j = g.location(u);
if (i > j)
g.arc[i*(i +1) / 2 + j] = true;//下三角
else
{
g.arc[j*(j + 1) / 2 + i] = true;//上三角
}
}
return is;
}
ostream &operator<<(ostream &os, Graph&g)
{
int i = 0;
for (; i < g.vertexnum; ++i)
{
cout << setw(6) << left << i << setw(6) << left << g.vertex[i] << "";//输出位置，顶点和分割线
for (int j = 0; j < g.vertexnum; ++j)
{
if (i >= j)
cout << setw(6) << left << g.arc[i(i + 1) / 2 + j];//下三角
else
{
cout << setw(6) << left << g.arc[j*(j + 1) / 2 + i];//上三角
}
}
cout << endl;
}
return os;
}
void dfsarticul(Graph &g, char &v, asistant &a)
{
int i, w, min;
i = g.location(v);
a.visited[i] = min = ++a.account;
for (w = g.first(v); w != -1; w = g.next(v, w))
{//逐一搜索当前结点的所有临界点
if (a.visited[w] == 0)
{//如果没有访问过，就递归调用搜索
dfsarticul(g, g.vertex[w], a);
if (a.low[w] < min)
min = a.low[w];//如果孩子结点的low值比当前节点的min值小，说明孩子节点有联结向祖先的回边。更新当前节点的min值为祖先的层次值
if (a.low[w] >= a.visited[g.location(v)])
cout << v << " ";//如果孩子节点的low比当前节点的访问序列值大，说明没有链接到祖先的回边，那么当前结点就是一个关节点。他以下的结点由当前结点联结到祖先
}
else if(a.visited[w]<min)//如果孩子结点被访问过，并别孩子结点的访问顺序小于当前结点的min值，说明孩子结点可以联接到更高层次的祖先，所以更新当前结点的min值，表示它也能联结到更高的祖先
{
min = a.visited[w];
}
}
a.low[g.location(v)] = min;//当前结点所有的临界点扫描完成以后，更新当前结点可以联结到最高的祖先的访问序列。
return;
}
void findarticul(Graph &g, asistant &a)
{
a.account = 1;
a.visited[0] = 1;
memset(&a.visited[1], 0, (g.vertexnum - 1) * sizeof(int));
int w = g.first(g.vertex[0]);//第一个顶点的第一个邻接点的位置
dfsarticul(g, g.vertex[w], a);//深度优先搜索
if (a.account<g.vertexnum)
{//如果搜索的次数少于顶点数，则跟节点是关节点
cout << g.vertex[0] << " ";
w = g.next(g.vertex[0], w);
while (w!=-1)//继续搜索根结点的其他临界点
{
if (a.visited[w] == 0)
dfsarticul(g, g.vertex[w], a);
w = g.next(g.vertex[0], w);
}
}
return;
}
/*
13 17
A B C D E F G H I J K L M
A L
A F
A C
A B
B C
B D
B G
B H
B M
D E
G I
G K
G H
H K
J L
J M
L M
*/