文字描述

　　相关定义:假若在删去顶点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的祖先的回边。(这段话可能不太好理解，可以结合示意图和代码来看)。

 

示意图

 

 

算法分析

　　算法的时间复杂度和深度优先遍历一样。

 

代码实现

 

1 //  2 // Created by lady on 18-12-15.  3 //  4   5   6 #include 
      
         7 #include 
       
          8   9 #define MAX_VERTEX_NUM    20        //最大顶点数 10  11 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网} 12 typedef char VertexType;//顶点类型 13 typedef struct ArcNode{ 14     int adjvex; 15     struct ArcNode *nextarc; 16     char info[5]; 17 }ArcNode; 18 typedef struct VNode{ 19     VertexType data; 20     ArcNode *firstarc; 21 }VNode, AdjList[MAX_VERTEX_NUM]; 22 typedef struct{ 23     AdjList vertices; 24     int vexnum; 25     int arcnum; 26     int kind; 27 }ALGraph; 28  29 //若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。 30 static int LocateVex(ALGraph G, VertexType v) 31 { 32     int i = 0; 33     for(i=0; i
        
         adjvex = v; 49     n->nextarc = L->nextarc; 50     L->nextarc = n; 51     return 0; 52 } 53  54 //采用邻接表的存储结构，构造无向图 55 static int CreateUDG(ALGraph *G) 56 { 57     int i = 0, j = 0, k = 0; 58     int v1 = 0, v2 = 0; 59     char tmp[10] = {
    0}; 60     printf("输入顶点数，弧数:"); 61     scanf("%d,%d", &G->vexnum, &G->arcnum); 62     for(i=0; i
         
          vexnum; i++){ 63         printf("输入第%d个顶点: ", i+1); 64         memset(tmp, 0, sizeof(tmp)); 65         scanf("%s", tmp); 66         G->vertices[i].data = tmp[0]; 67         G->vertices[i].firstarc = malloc(sizeof(struct ArcNode)); 68         G->vertices[i].firstarc->adjvex = -1; 69         G->vertices[i].firstarc->nextarc = NULL; 70     } 71     for(k=0; k
          
           arcnum; k++){ 72         printf("输入第%d条弧(顶点1, 顶点2): ", k+1); 73         memset(tmp, 0, sizeof(tmp)); 74         scanf("%s", tmp); 75         sscanf(tmp, "%c,%c", &v1, &v2); 76         i = LocateVex(*G, v1); 77         j = LocateVex(*G, v2); 78         InsFirst(G->vertices[i].firstarc, j); 79         InsFirst(G->vertices[j].firstarc, i); 80     } 81     return 0; 82 } 83  84 static int CreateGraph(ALGraph *G) 85 { 86     switch(G->kind){ 87         case DG: 88         case DN: 89         case UDN: 90             return -1; 91         case UDG: 92             return CreateUDG(G); 93         default: 94             return -1; 95     } 96 } 97  98 //输出图的信息 99 static void printG(ALGraph G)100 {101     if(G.kind == DG){102         printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);103     }else if(G.kind == DN){104         printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);105     }else if(G.kind == UDG){106         printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);107     }else if(G.kind == UDN){108         printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);109     }110     int i = 0;111     ArcNode *p = NULL;112     for(i=0; i
           
            adjvex);117 p = p->nextarc;118 }119 printf("\n");120 }121 return;122 }123 124 static int count = 0;125 static int visited[MAX_VERTEX_NUM] = { 0};126 static int low[MAX_VERTEX_NUM] = { 0};127 128 //从第v0个顶点出发深度优先遍历图G，查找并输出关节点。129 void DFSArticul(ALGraph G, int v0)130 {131 int w = 0;132 int min = 0;133 ArcNode *p = NULL;134 135 count += 1;136 min = count;137 visited[v0] = count;138 printf("visited[%d,%c]=%d\n", v0, G.vertices[v0].data, count);139 for(p=G.vertices[v0].firstarc->nextarc; p; p=p->nextarc){140 w = p->adjvex;141 if(visited[w] !=0 ){142 printf("回边: (%d,%c), (%d,%c)\n", v0, G.vertices[v0].data, w, G.vertices[w].data);143 }144 if(visited[w] == 0){145 DFSArticul(G, w);146 if(low[w] < min)147 min = low[w];148 if(low[w] >= visited[v0])149 printf("关节点 (index %d, data %c) !!!!!\n", v0, G.vertices[v0].data);150 }else if(visited[w] < min){151 min = visited[w];152 }153 }154 low[v0] = min;155 printf("low[%d,%c]=%d\n", v0, G.vertices[v0].data, min);156 }157 158 void FindArticul(ALGraph G)159 {160 count = 1;161 visited[0] = 1;162 low[0] = 1;163 int i = 0;164 int v = 0;165 ArcNode *p = NULL;166 for(i=1; i
            
             nextarc;170 v = p->adjvex;171 printf("visit[0,%c]=1 low[0,%c]=1\n", G.vertices[0].data, G.vertices[0].data);172 printf("从第(%d,%c)个顶点出发深度优先遍历图G，查找并输出关节点.\n", v, G.vertices[v].data);173 DFSArticul(G, v);174 if(count < G.vexnum){175 //生成树的根至少有两颗子树176 printf("生成树的根至少有两颗子树 因为count %d < %d\n", count, G.vexnum);177 printf("关节点 (index %d, data %c) !!!!!\n", 0, G.vertices[0].data);178 while(p->nextarc){179 p = p->nextarc;180 v = p->adjvex;181 if(visited[v] == 0){182 printf("从第(%d,%c)个顶点出发深度优先遍历图G，查找并输出关节点.\n", v, G.vertices[v].data);183 DFSArticul(G, v);184 }185 }186 }187 printf("index:\t\t");188 for(i=0;i
            
           
          
         
        
       
      

 

 

 

代码运行

 

/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, 弧数 16A    -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]=2visited[12,M]=3visited[1,B]=4visited[7,H]=5visited[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]=4low[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]=9visited[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]=2low[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]=1index:        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