首页 > 软件 > 图的深度优先遍历和广度优先遍历 c编程

图的深度优先遍历和广度优先遍历 c编程

软件 2022-05-16

求一个C语言编程,图的遍历,深度优先和广度优先搜索的程序。要浅显易懂的~~~~

给你一个作为参考吧 #include #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }Graph; //队列类 class Q

用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建;图的深度优先遍历、广度优先遍历。

/*
程序1:邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边,如果要无向只需要反过来多加一遍即可。
*/
#include
#include
#defineMAXM100000
#defineMAXN10000
intnext[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;
voidinput_data()
{
scanf("%d%d",&n,&m);
inti,x,y;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}else
printf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])dfs(y);
p=next[p];
}
}
voidbfs(intk)
{
head=0;tail=1;
flag[k]=1;dl[1]=k;
while(head{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
intp=first[x];
while(p!=0)
{
inty=en[p];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
p=next[p];
}
}
}
intmain()
{
input_data();//读入图信息。
pre();//初始化
printf("图的深度优先遍历结果:");
inti;
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");
return0;
}
/*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include
#include
#defineMAXN1000
intn,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];
voidinput_data()
{
scanf("%d%d",&n,&m);
inti;
for(i=1;i<=m;i++)
{
intx,y;
scanf("%d%d",&x,&y);
w[x][0]++;
w[x][w[x][0]]=y;
}
}
voidpre()
{
memset(flag,0,sizeof(flag));
pd=0;
}
voiddfs(intx)
{
flag[x]=1;
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])dfs(y);
}
}
voidbfs(intt)
{
inthead=0,tail=1;
dl[1]=t;flag[t]=1;
while(head{
intx=dl[++head];
if(!pd)
{
pd=1;
printf("%d",x);
}elseprintf("%d",x);
inti;
for(i=1;i<=w[x][0];i++)
{
inty=w[x][i];
if(!flag[y])
{
flag[y]=1;
dl[++tail]=y;
}
}
}
}
intmain()
{
input_data();
printf("图的深度优先遍历结果:");
pre();
inti;
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");
return0;
}

如何写 图的深度优先和广度优先遍历的C程序。

深度优先遍历可以用递归写,访问跟节点,然后递归遍历根节点的各个子树,注意是遍历子树不是访问孩子节点 广度优先遍历可以用队列,访问根节点,然后把根节点的各个孩子节点放入队列,每次访问一个节点之后,访问队头节点,把那个节点的儿子节点继续放入队列

什么是图的深度优先遍历?什么是图的广度优先遍历?

深度优先,就是先遍历它的一个邻节点,这个节点的邻节点。。。然后才遍历其他的邻节点 广度优先,就是先把它所有的邻节点都遍历完以后,再遍历它每个邻节点的邻节点 深度优先遍历(Depth-First Traversal) 1.图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另

c#)图的深度优先搜索和广度优先搜索算法的实现

#include "exam8-2.cpp" void BFS(ALGraph *G,int v) { ArcNode *p; int queue[MAXV],front=0,rear=0; //定义循环队列并初始化 int visited[MAXV]; //定义存放结点的访问标志的数组 int w,i; for (i=0;in;i++) visited[i]=0; //访问标志数组初始化 printf("%2d",v); //输出被访问顶点的编号 visited[v]=1; //置已访问标记 rear=(rear+1)%MAXV; queue[rear]=v; //v进队 while

标签:编程 信息技术 CC++ C(编程语言) 编程语言

大明白知识网 Copyright © 2020-2022 www.wangpan131.com. Some Rights Reserved.