鱼C论坛

 找回密码
 立即注册
查看: 288|回复: 39

[学习笔记] 图的遍历:深度和广度

[复制链接]
回帖奖励 92 鱼币 回复本帖可获得 2 鱼币奖励! 每人限 1 次(中奖概率 60%)
发表于 2021-11-26 00:42:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 划句顾 于 2021-11-26 01:02 编辑

第一:深度遍历
代码如下:
  1. /**********************************
  2. *author : LaoGu
  3. *time   :2021/11/23
  4. *fuction:图的深度遍历--使用栈
  5. **********************************/

  6. #include<stdio.h>
复制代码
  1. int visited[105]={0},
  2.      stack[105]={0},
  3.          top=-1;
复制代码
  1. //初始化图
  2. int init_G(int G[][105],int n)
  3. {
  4.         printf("请输入邻接表矩阵\n");
  5.         int i,j;
  6.         for(i=1;i<n+1;i++)
  7.         {
  8.                 for(j=1;j<n+1;j++)
  9.                 {
  10.             scanf("%d",&G[i][j]);
  11.                 }
  12.         }
  13.         printf("\n");
  14.         return 0;
  15. }
复制代码
  1. //入栈函数
  2. int push(int data)
  3. {
  4.         stack[++top]=data;
  5.     return 0;
  6. }

  7. //出栈函数
  8. int pop()
  9. {
  10.         stack[top--]=0;
  11.         return 0;
  12. }
复制代码

游客,如果您要查看本帖隐藏内容请回复

  1. //主函数
  2. int main(){
  3.         int n;
  4.         int G[105][105];
  5.         printf("请输入结点数:");
  6.         scanf("%d",&n);
  7.         init_G(G,n);
  8.         dfs(G,1,n);
  9.         printf("遍历成功!!!\n");
  10.     return 0;
  11. }
复制代码


                               
登录/注册后可看大图

运行结果:
运行结果1.jpg


                               
登录/注册后可看大图

第二:广度遍历
代码如下:
这些基本不变,和上面的深度遍历差不多
  1. /**********************************
  2. *author : LaoGu
  3. *time   :2021/11/25
  4. *fuction:图的广度遍历 --没有用队列,用的是栈
  5. **********************************/

  6. #include<stdio.h>


  7. int visited[105]={0},stack[105]={0},top=-1;

  8. //初始化图 --中规中矩
  9. int init_G(int G[][105],int n)
  10. {
  11.         printf("\n请输入邻接表矩阵:\n");
  12.         int i,j;
  13.         for(i=1;i<n+1;i++)
  14.         {
  15.                 printf("                  ");
  16.                 for(j=1;j<n+1;j++)
  17.                 {
  18.             scanf("%d",&G[i][j]);
  19.                 }
  20.         }
  21.         printf("\n");
  22.         return 0;
  23. }

  24. //入栈函数
  25. int push(int data)
  26. {
  27.         stack[++top]=data;
  28.     return 0;
  29. }
复制代码

改变的是这里
游客,如果您要查看本帖隐藏内容请回复

如果你深度遍历懂的话,这个广度遍历也是看得懂的,因为我是在深度遍历的基础上修改的。
  1. //主函数
  2. int main(){
  3.         int n,t;
  4.         int G[105][105];
  5.         printf("请输入结点数:");
  6.         scanf("%d",&n);
  7.         init_G(G,n);   //初始化图
  8.         printf("请问要从哪个结点开始广度遍历:");
  9.         scanf("%d",&t);
  10.         printf("在第【%d】个结点开始广度遍历的结果为:",t);
  11.         dfs(G,t,n);
  12.     printf("\n");
  13.         printf("恭喜你,遍历成功!!!\n");
  14.     return 0;
  15. }
复制代码



                               
登录/注册后可看大图

运行结果:
运行结果2.jpg


                               
登录/注册后可看大图

如果我把队列的方法可以求出广度遍历,那我就继续把代码加在这个帖子上
我先把作业交了再说哈哈哈哈哈
如果有更快的方法,鱼油萌可以分享一下哦哦哦哦哦~
我觉得我广度代码的运行速度还是太慢了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 02:23:29 | 显示全部楼层
楼主加油!
一个小疑问,似乎广度遍历是使用队列吧?
另外,提供一个开拓思路的尝试,深度遍历是可以使用递归函数的方法实现的,动手试一下,也很有意思~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2021-11-26 08:19:30 | 显示全部楼层
lightninng 发表于 2021-11-26 02:23
楼主加油!
一个小疑问,似乎广度遍历是使用队列吧?
另外,提供一个开拓思路的尝试,深度遍历是可以使用 ...

昂,我昨晚为了赶紧写完作业,广度就搞个栈的(这个应该没错吧,因为我运行的时候确实是广度的结果),队列有想过,但是还没下手。
等一下来尝试一下深度递归和广度队列。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 09:16:36 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 09:22:44 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 09:23:37 | 显示全部楼层

回帖奖励 +2 鱼币

谢谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 09:26:18 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 10:02:20 | 显示全部楼层
楼主加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 10:02:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 10:03:44 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 10:04:15 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 11:34:32 | 显示全部楼层
学习下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 11:35:08 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 11:35:44 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 11:47:23 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 12:37:29 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 12:40:01 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 23:02:39 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-26 23:03:12 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2021-11-27 00:00:27 | 显示全部楼层

回帖奖励 +2 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2021-12-7 10:12

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表