求图的割点问题的非递归算法
我采用边表集数据结构实现了图的割点的递归算法，但是不知道该如何转化为非递归算法，请大牛们提供思路。/*
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;
}
}
