图的割点（解释及实现）

大家好，欢迎来到IT知识分享网。

1.割点是什么

在一个无向连通图中，如果删除某个顶点后，图不再连通（任意两顶点之间不能相互到达），我们称这样的顶点为割点。 

2.找割点的办法

很容易就可以想到一个方法，依次删除每一个顶点，然后对图进行DFS或BFS或并查集来判断图是否连通。如果删除某个顶点后，导致图不再连通，那么说明该顶点就是割点。 但是对每一个顶点都进行遍历，时间复杂度会很高。 

2.1方法的核心

2.2 具体过程

2.3实现

#include <iostream> #include <vector> using namespace std; /* * 测试用例 6 7（顶点数和边数） 1 4 1 3 4 2 3 2 2 5 2 6 5 6 */ class Cut_point { 
    private: int vertice = 0;//顶点数 int edge = 0;//边数 //0行0列不存储信息，graph[i][j]表示节点i到节点j的权值为graph[i][j] vector<vector<int>> graph;//存储图的信息 //在所有的数组中下标0均不存值 vector<int> flag;//记录图中的割点，即flag[i] == 1； vector<int> num;//记录每个节点遍历的顺序（num[i] = j表示节点i是第j个被遍历的） vector<int> low;//记录节点不经过父顶点回溯的最早的节点（low[i] = j表示节点i最早回到j节点） int root = 1;//记录根节点 int index = 0;//记录num中的值 public: Cut_point(int x = 0, int y = 0) :vertice(x), edge(y) { 
    graph.resize(vertice + 1); for (int i = 0;i <= vertice; i++) { 
    graph[i].resize(vertice + 1,0); } flag.resize(vertice + 1, 0); num.resize(vertice + 1, 0); low.resize(vertice + 1, 0); } //图以及图相关的数据结构初始化 void Init_Graph() { 
    int u = 0, v = 0; for (int i = 0; i < edge; i++) { 
    cin >> u >> v; graph[u][v] = 1; graph[v][u] = 1;//无向图的初始化，没有权重信息，初始化为1即可 } } vector<int> Cut_point_By_DFS(int curernt,int father) { 
    int child = 0;//记录current节点的汉字总数 index++;//当前访问的顺序加1 num[curernt] = index;//表示current节点是在第index被访问的 low[curernt] = index; for (int i = 1; i <= vertice; i++) { 
    if (graph[curernt][i] == 1) { 
    //节点i还没有被访问过 if (num[i] == 0) { 
    child++;//i是current的孩子 Cut_point_By_DFS(i, curernt);//继续往下DFS //个人理解：在所有到current的边中，找最小下标的  low[curernt] = min(low[curernt], low[i]); //更新current节点能够访问到的最早顶点的顺序 if (curernt != root && low[i] >= num[curernt])//当前节点不是根节点，并且满足low[i] >= num[current]，则当前节点为割点 { 
    flag[curernt] = 1; } //如果当前顶点是根节点，在生成树中根节点中必须要有两个儿子，那么这个根节点才是割点 if (curernt == root && child == 2) { 
    flag[curernt] = 1; } } else { 
    //节点i已经被访问过，并且这个顶点不是当前节点current的父亲，则说明此时的i为current的祖先， //因此就需要更新当前节点current能够访问到最早顶点的index low[curernt] = min(low[curernt], num[i]); } } } return flag; } }; int main() { 
    int vertice = 0, edge = 0;//顶点数，边数 cout << "请输入顶点数和边数：" << endl; cin >> vertice >> edge; vector<int> flag; Cut_point point(vertice,edge); cout << "请输入边的信息：" << endl; point.Init_Graph(); flag = point.Cut_point_By_DFS(1, 1);//从1号顶点开始进行DFS，并且认为1号顶点是根节点 cout << "割点为："; for (int i = 1; i <= vertice; i++) { 
    if (flag[i] == 1) { 
    cout << i << " "; } } return 0; }