求割点（关键点） 首先，对于单独的一个点，或者2个点，我们不予考虑，因为我们没法认定。 分情况： 如果待确定的点不是搜索树的根节点，那么关键点可以认为是这样的点V，他的子孙节点中存在一个节点P，从P出发继续向下拓展（也就是不再走已经走过的边，而是向下兜圈子，然后通过某个后向边回到前面已经访问过的点，这里可以看出后向边的价值，后向边在dfs中是不允许扩展的，但是我们说的“兜回到祖先”就是通过某个后向边实现的）dfs不能达到V的祖先，事实上，只要有任意一个子孙节点符合这个特性，那么v就是关键点，因为原本子孙和祖先是连通的，删除它之后，他的子孙至少无法走到他的祖先（包括它的兄弟姐妹。。。） 如果是根节点，他如果只有一个子树，那么他不是关键点，如果有多于一个的子树，那么他必然是关键点   具体实现： 具体实现是这样的，我们定义一个点上的函数dfn(v)，表示v这个点在dfs过程中第一次访问的顺序，然后，为了达到上面的定义，我们再定义一个点上的函数low(v)，low(v)表示从v出发，继续向下拓展搜索，所能达到的最早的点，也就是dfn最小的点 显然，low(v)有： low(v)=min(dfn(v),low(s),dfn(w)) 其中，s是所有儿子节点，w是v的后向边 割顶：连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。注意：完全图的连通度为总顶点数－1；牵一发而动全身的点称为割点边连通度：连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；连通图的两个特征：1 连通度<=边连通度<=顶点数2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)块的概念：没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障至少两个站点同时发生故障，这种二连通分支称为块．显然各个块之间的关系有如下两种：1　互不连接2　通过割顶连接(割顶可以属于不同的块，也可以两个块公有一个割顶)引申：无向图寻找块，关键是找割顶．满足是割顶的条件：1　如果u不是根，u成为割顶的充要条件：当且仅当存在u的一个儿子顶点s,从s或者s的后代点到u的祖先点之间不存在后向边．2　如果u是根，则u成为割顶当且仅当它不止有一个儿子点．怎样求割顶：引入一个标号函数：low(u)=min{dfn(u),low(s),dfn(w)}; s是u的一个儿子，(u,w)是后向边显然low(u)值是u或者u的后代所能追溯到的最早(序号小)的祖先序号．利用标号函数low，分析求割顶的步骤：顶点u不为根且为割顶的条件是当且仅当u有一个儿子s，使得low(s)>=dfn(u),即s和s的后代不会追溯到比u更早的祖先点．low(u)的计算步骤：1 low(u)=dfn(u);//u在dfs过程中首次被访问2 low(u)=min{low(u),dfn(w)}//检查后向边(u,w)时3 low(u)=min{low(u),low(s)}//u的儿子s的关联边被检查时注意：对任何顶点u计算low(u)的值是不断修改的，只有当以U为根的dfs子树和后代的low值,dfn值全部出现以后才停止.        ＃i nclude <stdio.h>#define maxn 30typedef struct{    int k,l;}L;L l[maxn];int g[maxn][maxn];int st[maxn];int n,p,x,i;int k[maxn];int len;int min(int a,int b){    return a<b?a:b;}void push(int a){    p++;    st[p]=a;}int pop(){     return st[p--];         }void init(){    memset(l,0,sizeof(l));    p=0;push(1);    i=1;    len=-1;    l[1].k=1;l[1].l=1;    memset(k,-1,sizeof(k));    x=0;}bool ink(int a){    for(int i=0;i<len;i++){        if(k==a) return true;    }    return false;}void algorithm(int v){    int u;    for(u=1;u<=n;u++){        if(g[v]>0){            if(l.k==0){                i++;                l.k=i;                l.l=i;                push(u);                algorithm(u);                l[v].l=min(l[v].l,l.l);                                if(l.l>=l[v].k){                        if(v!=1 && !ink(v)){                        len++;                        k[len]=v;                    }                    if(v==1) x++;                    while(st[p]!=v){                                               printf("%d  ",pop());                    }                }            }            else l[v].l=min(l[v].l,l.k);        }    }}int main(){    algorithm(1);    if(x>1){    len++;    k[len]=1;    }}

评论