文字描述
相关定义:假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点.一个没有关节点的连通图称为重连通图. 在重连通图上,任意一对顶点之间至少存在两条路径, 则在删去某个顶点以及依附于该顶点的各边时也不破坏图的连通性.若在连通图上至少删除k个顶点才能破坏图的连通性,则称此图的连通度为k.
判断图是否是重连通的,可以先利用深度优先搜索求得图的关节点,一个没有关节点的图便是重连通的.由深度优先生成树可得出两类关节点的特性:
1 若生成树的根有两颗或两颗以上的子树, 则此根顶点必为关节点. 因为.若删去根顶点,生成树便变成生成森林.如示意图中的顶点A
2 若生成树中某个非叶子顶点v,其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边,则v为关节点. 因为,若删去v,则其子树和图的其他部分被分割开来.如示意图中的顶点B,D,G
若该图Graph={V,{Edge}}重新定义遍历时的访问数组visit，并引入一个新的数足low，则由一次深度优先遍历便可求得连通图中存在的所有关节点。
若对于某个顶点v，存在函数节点w，且low[w]>=visited[v], 则v必为关节点。因为当w是v的孩子结点时，low[w]>=visited[v], 表明w及其子孙均无指向v的祖先的回边。(这段话可能不太好理解，可以结合示意图和代码来看)。
示意图
算法分析
算法的时间复杂度和深度优先遍历一样。
代码实现
//
// Created by lady on 18-12-15.
// #include <stdlib.h>
#include <stdio.h> #define MAX_VERTEX_NUM 20 //最大顶点数 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}
typedef char VertexType;//顶点类型
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
char info[];
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum;
int arcnum;
int kind;
}ALGraph; //若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
static int LocateVex(ALGraph G, VertexType v)
{
int i = ;
for(i=; i<G.vexnum; i++){
if(G.vertices[i].data == v)
return i;
}
return -;
}
static VertexType LocateData(ALGraph G, int index)
{
return G.vertices[index].data;
} //在链表L的头部前插入v
static int InsFirst(ArcNode *L, int v)
{
ArcNode *n = (ArcNode *)malloc(sizeof(struct ArcNode));
n->adjvex = v;
n->nextarc = L->nextarc;
L->nextarc = n;
return ;
} //采用邻接表的存储结构，构造无向图
static int CreateUDG(ALGraph *G)
{
int i = , j = , k = ;
int v1 = , v2 = ;
char tmp[] = {};
printf("输入顶点数，弧数:");
scanf("%d,%d", &G->vexnum, &G->arcnum);
for(i=; i<G->vexnum; i++){
printf("输入第%d个顶点: ", i+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
G->vertices[i].data = tmp[];
G->vertices[i].firstarc = malloc(sizeof(struct ArcNode));
G->vertices[i].firstarc->adjvex = -;
G->vertices[i].firstarc->nextarc = NULL;
}
for(k=; k<G->arcnum; k++){
printf("输入第%d条弧(顶点1, 顶点2): ", k+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
sscanf(tmp, "%c,%c", &v1, &v2);
i = LocateVex(*G, v1);
j = LocateVex(*G, v2);
InsFirst(G->vertices[i].firstarc, j);
InsFirst(G->vertices[j].firstarc, i);
}
return ;
} static int CreateGraph(ALGraph *G)
{
switch(G->kind){
case DG:
case DN:
case UDN:
return -;
case UDG:
return CreateUDG(G);
default:
return -;
}
} //输出图的信息
static void printG(ALGraph G)
{
if(G.kind == DG){
printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == DN){
printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == UDG){
printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}else if(G.kind == UDN){
printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
}
int i = ;
ArcNode *p = NULL;
for(i=; i<G.vexnum; i++){
printf("%c\t", G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p){
printf("%d\t", p->adjvex);
p = p->nextarc;
}
printf("\n");
}
return;
} static int count = ;
static int visited[MAX_VERTEX_NUM] = {};
static int low[MAX_VERTEX_NUM] = {}; //从第v0个顶点出发深度优先遍历图G，查找并输出关节点。
void DFSArticul(ALGraph G, int v0)
{
int w = ;
int min = ;
ArcNode *p = NULL; count += ;
min = count;
visited[v0] = count;
printf("visited[%d,%c]=%d\n", v0, G.vertices[v0].data, count);
for(p=G.vertices[v0].firstarc->nextarc; p; p=p->nextarc){
w = p->adjvex;
if(visited[w] != ){
printf("回边: (%d,%c), (%d,%c)\n", v0, G.vertices[v0].data, w, G.vertices[w].data);
}
if(visited[w] == ){
DFSArticul(G, w);
if(low[w] < min)
min = low[w];
if(low[w] >= visited[v0])
printf("关节点 (index %d, data %c) !!!!!\n", v0, G.vertices[v0].data);
}else if(visited[w] < min){
min = visited[w];
}
}
low[v0] = min;
printf("low[%d,%c]=%d\n", v0, G.vertices[v0].data, min);
} void FindArticul(ALGraph G)
{
count = ;
visited[] = ;
low[] = ;
int i = ;
int v = ;
ArcNode *p = NULL;
for(i=; i<G.vexnum; ++i){
visited[i] = ;
}
p = G.vertices[].firstarc->nextarc;
v = p->adjvex;
printf("visit[0,%c]=1 low[0,%c]=1\n", G.vertices[].data, G.vertices[].data);
printf("从第(%d,%c)个顶点出发深度优先遍历图G，查找并输出关节点.\n", v, G.vertices[v].data);
DFSArticul(G, v);
if(count < G.vexnum){
//生成树的根至少有两颗子树
printf("生成树的根至少有两颗子树 因为count %d < %d\n", count, G.vexnum);
printf("关节点 (index %d, data %c) !!!!!\n", , G.vertices[].data);
while(p->nextarc){
p = p->nextarc;
v = p->adjvex;
if(visited[v] == ){
printf("从第(%d,%c)个顶点出发深度优先遍历图G，查找并输出关节点.\n", v, G.vertices[v].data);
DFSArticul(G, v);
}
}
}
printf("index:\t\t");
for(i=;i<G.vexnum; i++){
printf("%d\t", i);
}
printf("\n"); printf("data:\t\t");
for(i=;i<G.vexnum; i++){
printf("%c\t", G.vertices[i].data);
}
printf("\n"); printf("visited[]:\t");
for(i=;i<G.vexnum; i++){
printf("%d\t", visited[i]);
}
printf("\n"); printf("low[]:\t\t");
for(i=;i<G.vexnum; i++){
printf("%d\t", low[i]);
}
printf("\n");
} int main(int argc, char *argv[])
{
printf("创建一个无向图, ");
ALGraph G;
G.kind = UDG;
CreateGraph(&G); printf("\n打印此无向图中存放的结点信息, ");
printG(G); printf("\n查找并输出以邻接表作存储结构的图G的全部关节点:\n");
FindArticul(G);
return ;
}
利用深度优先遍历输出图中的关节点
代码运行
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
创建一个无向图, 输入顶点数，弧数:13,16
输入第1个顶点: A
输入第2个顶点: B
输入第3个顶点: C
输入第4个顶点: D
输入第5个顶点: E
输入第6个顶点: F
输入第7个顶点: G
输入第8个顶点: H
输入第9个顶点: I
输入第10个顶点: J
输入第11个顶点: K
输入第12个顶点: L
输入第13个顶点: M
输入第1条弧(顶点1, 顶点2): A,B
输入第2条弧(顶点1, 顶点2): A,C
输入第3条弧(顶点1, 顶点2): A,F
输入第4条弧(顶点1, 顶点2): A,L
输入第5条弧(顶点1, 顶点2): L,J
输入第6条弧(顶点1, 顶点2): M,J
输入第7条弧(顶点1, 顶点2): M,L
输入第8条弧(顶点1, 顶点2): M,B
输入第9条弧(顶点1, 顶点2): B,D
输入第10条弧(顶点1, 顶点2): D,E
输入第11条弧(顶点1, 顶点2): B,G
输入第12条弧(顶点1, 顶点2): B,H
输入第13条弧(顶点1, 顶点2): G,H
输入第14条弧(顶点1, 顶点2): G,I
输入第15条弧(顶点1, 顶点2): G,K
输入第16条弧(顶点1, 顶点2): H,K 打印此无向图中存放的结点信息, 类型：无向图；顶点数 13, 弧数 16
A -1 11 5 2 1
B -1 7 6 3 12 0
C -1 0
D -1 4 1
E -1 3
F -1 0
G -1 10 8 7 1
H -1 10 6 1
I -1 6
J -1 12 11
K -1 7 6
L -1 12 9 0
M -1 1 11 9 查找并输出以邻接表作存储结构的图G的全部关节点:
visit[0,A]=1 low[0,A]=1
从第(11,L)个顶点出发深度优先遍历图G，查找并输出关节点.
visited[11,L]=2
visited[12,M]=3
visited[1,B]=4
visited[7,H]=5
visited[10,K]=6
回边: (10,K), (7,H)
visited[6,G]=7
回边: (6,G), (10,K)
visited[8,I]=8
回边: (8,I), (6,G)
low[8,I]=7
关节点 (index 6, data G) !!!!!
回边: (6,G), (7,H)
回边: (6,G), (1,B)
low[6,G]=4
low[10,K]=4
回边: (7,H), (6,G)
回边: (7,H), (1,B)
low[7,H]=4
关节点 (index 1, data B) !!!!!
回边: (1,B), (6,G)
visited[3,D]=9
visited[4,E]=10
回边: (4,E), (3,D)
low[4,E]=9
关节点 (index 3, data D) !!!!!
回边: (3,D), (1,B)
low[3,D]=4
关节点 (index 1, data B) !!!!!
回边: (1,B), (12,M)
回边: (1,B), (0,A)
low[1,B]=1
回边: (12,M), (11,L)
visited[9,J]=11
回边: (9,J), (12,M)
回边: (9,J), (11,L)
low[9,J]=2
low[12,M]=1
回边: (11,L), (9,J)
回边: (11,L), (0,A)
low[11,L]=1
生成树的根至少有两颗子树 因为count 11 < 13
关节点 (index 0, data A) !!!!!
从第(5,F)个顶点出发深度优先遍历图G，查找并输出关节点.
visited[5,F]=12
回边: (5,F), (0,A)
low[5,F]=1
从第(2,C)个顶点出发深度优先遍历图G，查找并输出关节点.
visited[2,C]=13
回边: (2,C), (0,A)
low[2,C]=1
index: 0 1 2 3 4 5 6 7 8 9 10 11 12
data: A B C D E F G H I J K L M
visited[]: 1 4 13 9 10 12 7 5 8 11 6 2 3
low[]: 1 1 1 4 9 1 4 4 7 2 4 1 1 Process finished with exit code 0