題目：求一個連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，圖不再連通，描述算法。

分析：

1. 最簡單也是最直接的算法是，刪除一個點然后判斷連通性，如果刪除此點，圖不再連通，則此點是割點，反之不是割點（圖的連通性一般通過深搜來判定，是否能一次搜索完 全部頂點）；

2. 通過深搜優先生成樹來判定。從任一點出發深度優先遍歷得到優先生成樹，對于樹中任一頂點Ｖ而言，其孩子節點為鄰接點。由深度優先生成樹可得出兩類割點的特性：

???? （１）若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為割點。因為圖中不存在連接不同子樹頂點的邊，若刪除此節點，則樹便成為森林；

???? （２）若生成樹中某個非葉子頂點V，其某棵子樹的根和子樹中的其他節點均沒有指向V的祖先的回邊，則V為割點。因為刪去v，則其子樹和圖的其它部分被分割開來。

仍然利用深搜算法，只不過在這里定義visited[v]表示為深度優先搜索遍歷圖時訪問頂點v的次序號，定義low[v]=Min{visited[v]，low[w]，visited[k]}，其中w是頂點v在深度優先生成樹上的孩子節點；k是頂點v在深度優先生成樹上由回邊聯結的祖先節點。

?? 割點判定條件：如果對于某個頂點v，存在孩子節點w且low[w]>=visited[v]，則該頂點v必為關節點。因為當w是v的孩子節點時，low[w]>=visited[v]，表明w及其子孫均無指向v的祖先的回邊，那么當刪除頂點v后，v的孩子節點將于其他節點被分割開來，從來形成新的連通分量。

#include <iostream> #include <string> #include <queue> using namespace std; #define MAXN 100 struct ArcNode { int adjVertex; //邊到的頂點 ArcNode *next; }; struct VNode { string data; ArcNode *firstArc; }; typedef VNode AdjList[MAXN]; struct Graph { int vertexNum; int arcNum; AdjList vertexs; }; int Locate(Graph g,string str) { for(int i = 0;i<g.vertexNum;i++) { if(str == g.vertexs[i].data) return i; } return -1; } void Create(Graph &g) { string start,end; cout << "請輸入頂點和邊數："<<endl; cin>>g.vertexNum>>g.arcNum; for(int i = 0;i<g.vertexNum;i++) { cout<<"請輸入第"<<i<<"個頂點:"<<endl; cin>>g.vertexs[i].data; g.vertexs[i].firstArc = NULL; } for(int i = 0;i <g.arcNum;i++) { cout<<"請輸入第"<<i<<"條邊的起始和結束頂點"<<endl; cin>>start>>end; int m = Locate(g,start); int n = Locate(g,end); ArcNode *node = new ArcNode; node->adjVertex = n; node->next = g.vertexs[m].firstArc; g.vertexs[m].firstArc = node; ArcNode *node1 = new ArcNode; node1->adjVertex = m; node1->next = g.vertexs[n].firstArc; g.vertexs[n].firstArc = node1; } } void Print(Graph g) { for(int i = 0;i<g.vertexNum;i++) { cout << g.vertexs[i].data; ArcNode *p = g.vertexs[i].firstArc; while(p) { cout<<"-->"<<g.vertexs[p->adjVertex].data; p = p->next; } cout <<endl; } } int FirstAdjVex(Graph g,int v)//返回v的第一個鄰接頂點序號 { ArcNode *p = g.vertexs[v].firstArc; if(p!= NULL) return p->adjVertex; else return -1; } int NextAdjVex(Graph g,int v,int w) //返回頂點v相對于w的下一個鄰接點的序號 { ArcNode *p = g.vertexs[v].firstArc; while(p) { if(p->adjVertex == w) break; p = p->next; } if(p->adjVertex !=w || !p->next) return -1; return p->next->adjVertex; } //求割點 int countN; int visted[MAXN]; int low[MAXN]; void DFSCutPoint(Graph g,int v0) { int min = 0,w; visted[v0] = min = ++countN;;//v0是第count個訪問的頂點，min的初值為visited[v0]，即v0的訪問次序 for(ArcNode *p = g.vertexs[v0].firstArc;p;p=p->next) { w = p->adjVertex; if(!visted[w]) { DFSCutPoint(g,w);//從第w個頂點出發深搜，查找并輸出關節點（割點），返回前求得low[w] if(low[w] < min)//如果v0的孩子節點w的low[]小，說明孩子節點還與其他節點（祖先）相鄰 min = low[w]; if(low[w]>=visted[v0] ) //v0的孩子節點w只與v0相連，則v0是關節點（割點） cout<<g.vertexs[w].data<<" "; } else if(visted[w] < min)//w已訪問，則w是v0生成樹上祖先，它的訪問順序必小于min min =visted[w]; } low[v0] = min;//low[v0]取三者最小值 } void FindCutPoint(Graph g) { visted[0] = true; for(int i = 1;i<g.vertexNum;i++) visted[i] = false; ArcNode *p=g.vertexs[0].firstArc; int v = p->adjVertex; DFSCutPoint(g,v); if(countN < g.vertexNum) { cout << g.vertexs[0].data<<" "; while(p->next) { p = p->next; v = p->adjVertex; if(!visted[v]) DFSCutPoint(g,v); } } } int main() { Graph g; Create(g); cout<<"割點如下: "<<endl; FindCutPoint(g); return 0;

轉載于:https://www.cnblogs.com/tham/p/6827246.html

總結

以上是生活随笔為你收集整理的求一个连通图的割点（去掉一个点后图不再连通）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。