首页 > 代码库 > 图的割点（邻接矩阵实现）

图的割点（邻接矩阵实现）

2024-08-03 16:56:39   218人阅读

/*
Name: 图的割点（邻接矩阵） 
Copyright: 
Author: 巧若拙 
Date: 21-11-14 20:34
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   //最大变量（顶点）数量 


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


typedef struct EdgeNode{ //边表结点
int adjvex;  //邻接点域，存储该顶点对应的下标
// EdgeType weight; //权值，对于非网图可以不需要 
struct EdgeNode *next; //链域，指向下一个邻接点 
} EdgeNode;


typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域，存储顶点信息
EdgeNode *firstEdge; //边表头指针
} VertexNode;


int flag[MAXN] = {0}; //存储顶点是否为割点 
int num[MAXN] = {0}; //存储顶点的时间戳信息 
int low[MAXN] = {0}; //存储顶点的最小时间戳信息 
int index = 0; //用来进行时间戳的递增 


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


int main()
{
int i, m, n;
VertexNode GL[MAXN];

printf("请输入顶点数量和边数量:\n"); 
scanf("%d%d", &n, &m);

CreateGraph(GL, n, m);//创建一个图
PrintGraph(GL, n, m);//输出图

// CutPoint_DFS(GL, 0, 0, 0);//从0号顶点开始深度优先搜索寻找割点（递归算法） 
CutPoint(GL, 0, n);//采用深度优先搜索寻找割点（非递归算法） 

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

    return 0;
}


void CreateGraph(VertexNode *GL, int n, int m)//创建一个图
{
int i, u, v;
EdgeNode *e;

for (i=0; i<n; i++)//初始化图 
{
GL[i].data = http://www.mamicode.com/i;
GL[i].firstEdge = NULL;
num[i] = low[i] = flag[i] = 0;
}

for (i=0; i<m; i++) //读入边信息（注意是无向图） 
{
scanf("%d%d", &u, &v);

e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
if (!e)
{
puts("Error"); 
exit(1);
}
e->next = GL[u].firstEdge;
GL[u].firstEdge = e;
e->adjvex = v;

e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点 
if (!e)
{
puts("Error"); 
exit(1);
}
e->next = GL[v].firstEdge;
GL[v].firstEdge = e;
e->adjvex = u;
}
} 


void PrintGraph(VertexNode *GL, int n, int m)//输出图
{
int i, j;
EdgeNode *e;

for (i=0; i<n; i++)
{
printf("%d: ", i);
e = GL[i].firstEdge;
while (e)
{
printf("<%d, %d>, ", i, e->adjvex);
e = e->next;
}
printf("\n");
}
printf("\n");
} 
 
void CutPoint_DFS(VertexNode *GL, int root, int cur, int father)//采用深度优先搜索寻找割点（递归算法） 
{
int child = 0;
EdgeNode *e = GL[cur].firstEdge;

num[cur] = low[cur] = ++index;
while (e)
{
if (num[e->adjvex] == 0) //新结点做儿子
{
child++;
CutPoint_DFS(GL, root, e->adjvex, cur);

low[cur] = (low[cur] < low[e->adjvex]) ? low[cur] : low[e->adjvex];//取最小值 

if ((cur != root && num[cur] <= low[e->adjvex])
|| (cur == root && child == 2))
{
flag[cur] = 1;
}
} 
else if (e->adjvex != father) //与旁系祖先有连接，其实也可以不加这个限制条件，因为如果父亲是自己则low[cur]值不变 
{
low[cur] = (low[cur] < num[e->adjvex]) ? low[cur] : num[e->adjvex];//取最小值 
} 

e = e->next;
}
}


void CutPoint(VertexNode *GL, int root, int n)//采用深度优先搜索寻找割点（非递归算法） 
{
int Stack[MAXN]; //用来存储当前被处理顶点的栈 
EdgeNode *SF[MAXN], *e;
int child[MAXN] = {0}; //存储顶点的儿子数量 
int u, v, top = 0;

for (u=0; u<n; u++)//初始化SF 
SF[u] = GL[u].firstEdge;

Stack[top] = root;
num[root] = low[root] = ++index;
while (top >= 0)
{
e = SF[Stack[top]];
if (e)
{
SF[Stack[top]] = e->next; //指向下一条边 
if (num[e->adjvex] == 0)
{
child[Stack[top]]++;
Stack[++top] = e->adjvex;
low[e->adjvex] = num[e->adjvex] = ++index;
}
else
{
low[Stack[top]] = (low[Stack[top]] < num[e->adjvex]) ? low[Stack[top]] : num[e->adjvex];//取最小值
}
}
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--;
}
}
}

图的割点（邻接矩阵实现）


联系
我们