首页 > 代码库 > 图的割点（边表集实现）

图的割点（边表集实现）

2024-08-03 12:13:52   220人阅读

/*
    Name: 图的割点（边表集实现）
    Copyright: 
    Author: 巧若拙 
    Date: 20-11-14 21:17
    Description: 
    在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。
求割点与桥的算法是R.Tarjan发明的。对图深度优先搜索，定义DFS(u)为u在搜索树（以下简称为树）中被遍历到的次序号(等价于时间戳)。
定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点，即DFS序号最小的节点的序号。根据定义，则有：  
Low(u)=Min { DFS(u) ，DFS(v)}，其中 (u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点 Low(v) (u,v)为树枝边(父子边) 
一个顶点u是割点，当且仅当满足(1)或(2) ：
(1) u为树根，且u有多于一个子树。 
(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。
本文用边表集存储图的信息，实现了递归和非递归两种算法。 
*/
#include<stdio.h>
#include<stdlib.h>


#define MAXN 26   //最大变量（顶点）数量 
#define MAXM 100000   //最大关系式数量 


typedef char VertexType; //顶点类型由用户自定义
typedef int EdgeType; //边上的权值类型由用户自定义


typedef struct Edge{ //边集数组 
    int u, v; //弧尾和弧头 
    int next; //指向同一个弧尾的下一条边 
//    EdgeType weight; //权值，对于非网图可以不需要 
} EdgeLib;


EdgeLib edge[MAXM]; //存储边信息
int first[MAXN]; //指向顶点的第一条边
int flag[MAXN] = {0}; //存储顶点是否为割点 
int num[MAXN] = {0}; //存储顶点的时间戳信息 
int low[MAXN] = {0}; //存储顶点的最小时间戳信息 
int index = 0; //用来进行时间戳的递增 


void CreateGraph(int n, int m);//创建一个图
void PrintGraph(int n, int m);//输出图
void CutPoint_DFS(int root, int cur, int father);//采用深度优先搜索寻找割点（递归算法） 
void CutPoint(int root, int n);//采用深度优先搜索寻找割点（非递归算法） 


int main()
{
    int i, m, n;
    
    printf("请输入顶点数量和边数量:\n"); 
    scanf("%d%d", &n, &m);    
    
    CreateGraph(n, m);//创建一个图
    PrintGraph(n, m);//输出图
    
 //   CutPoint_DFS(0, 0, 0);//从0号顶点开始深度优先搜索寻找割点（递归算法） 
    CutPoint(0, n); 


    printf("\n割点为："); 
    for (i=0; i<n; i++)//输出所有割点
    {
        if (flag[i] == 1)
            printf("%d ", i);
    } 
    printf("\n");
    
    return 0;
}


void CreateGraph(int n, int m)//创建一个图
{
    int i;
    
    for (i=0; i<n; i++)//初始化图 
    {
        first[i] = -1;
        num[i] = low[i] = flag[i] = 0;
    }
    
    for (i=0; i<m+m; i+=2)  //读入边信息（注意是无向图） 
    {
        scanf("%d%d", &edge[i].u, &edge[i].v);
        edge[i].next = first[edge[i].u];
        first[edge[i].u] = i;
        
        edge[i+1].u = edge[i].v;
        edge[i+1].v = edge[i].u;
        edge[i+1].next = first[edge[i+1].u];
        first[edge[i+1].u] = i + 1;
    }
} 


void PrintGraph(int n, int m)//输出图
{
    int i, j;
    
    for (i=0; i<n; i++)
    {
        printf("%d: ", i);
        j = first[i]; //指向i的第一条边 
        while (j != -1)
        {
            printf("<%d, %d>, ", edge[j].u, edge[j].v);
            j = edge[j].next; //指向下一条边 
        }
        printf("\n");
    }
    printf("\n");
} 


void CutPoint_DFS(int root, int cur, int father)//采用深度优先搜索寻找割点（递归算法） 
{
    int k, child = 0;
    
    num[cur] = low[cur] = ++index;
    k = first[cur];
    while (k != -1)
    {
        if (num[edge[k].v] == 0) //新结点做儿子
        {
            child++;
            CutPoint_DFS(root, edge[k].v, cur);
            
            low[cur] = (low[cur] < low[edge[k].v]) ? low[cur] : low[edge[k].v];//取最小值 
            
            if ((cur != root && num[cur] <= low[edge[k].v])
             || (cur == root && child == 2))
            {
                flag[cur] = 1;
            }
        } 
        else if (edge[k].v != father) //与旁系祖先有连接，其实也可以不加这个限制条件，因为如果父亲是自己则low[cur]值不变 
        {
            low[cur] = (low[cur] < num[edge[k].v]) ? low[cur] : num[edge[k].v];//取最小值 
        } 
        
        k = edge[k].next;
    }
}


void CutPoint(int root, int n)//采用深度优先搜索寻找割点（非递归算法） 
{
    int Stack[MAXN]; //用来存储当前被处理顶点的栈 
    int SF[MAXN]; //指向顶点的第一条未搜索边
    int child[MAXN] = {0}; //存储顶点的儿子数量 
    int k, u, v, top = 0;
    
    for (u=0; u<n; u++)//初始化SF 
        SF[u] = first[u];
        
    Stack[top] = root;
    num[root] = low[root] = ++index;
    while (top >= 0)
    {
        k = SF[Stack[top]];
        if (k != -1)
        {
        SF[Stack[top]] = edge[k].next; //指向下一条边 
            if (num[edge[k].v] == 0)
            {
                child[Stack[top]]++;
                Stack[++top] = edge[k].v;
                low[edge[k].v] = num[edge[k].v] = ++index;
            }
            else
            {
                low[Stack[top]] = (low[Stack[top]] < num[edge[k].v]) ? low[Stack[top]] : num[edge[k].v];//取最小值
            }
        }
        else
        {
            if (top > 0)
            {
                u = Stack[top-1];
                v = Stack[top];
                low[u] = (low[u] < low[v]) ? low[u] : low[v];
                if ((u != root && low[v] >= num[u])
                 || (u == root && child[u] == 2))
                {
                    flag[u] = 1;
                }
            }
            top--;
        }
    }        
}

图的割点（边表集实现）


联系
我们