双连通性(算法篇)

算法之双连通性

双连通性

概念：

• 双连通性就是当删除图中的一个顶点，使图分割成两个图，则这个图就具有双连通性，而能导致图分割成多张图的顶点称为割点
• 背向边：当一个顶点被访问时，选取该顶点其中一个未访问过的邻接顶点进行访问，没被选取到的邻接顶点与当前顶点形成的边称为背向边

寻找割点：

• 从图中任一顶点开始，执行深度优先搜索并在顶点被访问时给它们编号。对于每一个顶点v我们称其先序编号为Num(v);

• 对于深度优先搜索生成树上的每一个顶点v，计算编号最低的顶点，我们称之为Low(v);对于求解每个顶点的Low，需要对深度优先生成树进行一次后序遍历算出，因为求出顶点v的Low的规则如下：

  1. Num(v)
  2. 所有背向边(v,w)中的最低Num(w)
  3. 树的所有边(v,w)中的最低Low(w) --所以需要后序遍历
  4. Low(v)等于前面三个变量中的最小值。

• 如果一个顶点v为割点，需要满足它的子节点w的Low(w)>=Num(v)

实现代码：

struct listnode{int data;     //numbool flag;    //判断是否访问过int parent;     //父节点int low;listnode* next;
};int count=1;void findart(int v){an[v].flag= true;an[v].low=an[v].data=count++;listnode* p=an[v].next;while (p!= nullptr){if(!an[p->data].flag){an[p->data].parent=v;findart(p->data);if(an[p->data].low>=an[v].data){cout<<"V"<<v<<"为割点"<<endl;}an[v].low=min(an[v].low,an[p->data].low);}else if(an[v].parent!=p->data){an[v].low=min(an[v].low,an[p->data].data);}p=p->next;}}

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms