用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。
发布网友
发布时间：2022-05-13 18:25
共1个回答
热心网友
时间：2023-10-20 12:43
程序1：邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include <stdio.h>
#include <string.h>
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
void input_data()
{
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf("%d",x);
}else
printf(" %d",x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y]) dfs(y);
p=next[p];
}
}
void bfs(int k)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while (head<tail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int p=first[x];
while (p!=0)
{
int y=en[p];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
int main()
{
input_data();//读入图信息。
pre();//初始化
printf("图的深度优先遍历结果:");
int i;
for (i=1;i<=n;i++)//对整张图进行dfs; 加这个for主要是为了防止不多个子图的情况
if (!flag[i])
dfs(i);
printf("\n-------------------------------------------------------------\n");
pre();//初始化
printf("图的广度优先遍历结果为:");
for (i=1;i<=n;i++)
if (!flag[i])
bfs(i);
printf("\n----------------------end------------------------------------\n");
return 0;
}
/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1000
int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
void input_data()
{
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
void pre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
void dfs(int x)
{
flag[x]=1;
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int i;
for (i=1;i<=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y]) dfs(y);
}
}
void bfs(int t)
{
int head=0,tail=1;
dl[1]=t;flag[t]=1;
while (head<tail)
{
int x=dl[++head];
if (!pd)
{
pd=1;
printf("%d",x);
}else printf(" %d",x);
int i;
for (i=1;i<=w[x][0];i++)
{
int y=w[x][i];
if (!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
int main()
{
input_data();
printf("图的深度优先遍历结果:");
pre();
int i;
for (i=1;i<=n;i++)
if (!flag[i])
dfs(i);
printf("\n---------------------------------------------------------------\n");
printf("图的广度优先遍历结果:");
pre();
for (i=1;i<=n;i++)
if (!flag[i])
bfs(i);
printf("\n-----------------------------end--------------------------------\n");
return 0;
}
