| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 436 人关注过本帖
标题:求图的割点问题的非递归算法
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏
 问题点数:0 回复次数:2 
求图的割点问题的非递归算法
我采用边表集数据结构实现了图的割点的递归算法,但是不知道该如何转化为非递归算法,请大牛们提供思路。

/*
    Name: 图的割点
    Copyright:
    Author: 巧若拙
    Date: 20-11-14 21:17
    Description:
*/
#include<stdio.h>
#include<stdlib.h>

#define true 1  
#define false 0
#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号顶点开始深度优先搜索寻找割点(递归算法)

    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;
    }
}
搜索更多相关主题的帖子: Copyright include false 如何 用户 
2014-11-20 23:10
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:0 
其实我写了一个非递归算法,可是有问题,请大牛们帮忙指点一下,谢谢!
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)
        {
            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];//取最小值
            }
            
            SF[Stack[top]] = edge[k].next; //指向下一条边
        }
        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--;
        }
    }        
}
2014-11-20 23:12
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
收藏
得分:0 
一觉醒来,发现昨天犯了一个致命错误,SF[Stack[top]] = 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--;
        }
    }        
}
2014-11-21 08:20
快速回复:求图的割点问题的非递归算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.048013 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved