图的遍历：深度和广度

划句顾

第一：深度遍历
代码如下：

1. /**********************************
   
2. *author : LaoGu
   
3. *time   :2021/11/23
   
4. *fuction:图的深度遍历--使用栈
   
5. **********************************/
   
6. 
   
7. #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. //出栈函数
   
9. int pop()
   
10. {
    
11.         stack[top--]=0;
    
12.         return 0;
    
13. }

复制代码

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

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. /**********************************
   
2. *author : LaoGu
   
3. *time   :2021/11/25
   
4. *fuction:图的广度遍历 --没有用队列，用的是栈
   
5. **********************************/
   
6. 
   
7. #include<stdio.h>
   
8. 
   
9. 
   
10. int visited[105]={0},stack[105]={0},top=-1;
    
11. 
    
12. //初始化图 --中规中矩
    
13. int init_G(int G[][105],int n)
    
14. {
    
15.         printf("\n请输入邻接表矩阵:\n");
    
16.         int i,j;
    
17.         for(i=1;i<n+1;i++)
    
18.         {
    
19.                 printf("                  ");
    
20.                 for(j=1;j<n+1;j++)
    
21.                 {
    
22.             scanf("%d",&G[i][j]);
    
23.                 }
    
24.         }
    
25.         printf("\n");
    
26.         return 0;
    
27. }
    
28. 
    
29. //入栈函数
    
30. int push(int data)
    
31. {
    
32.         stack[++top]=data;
    
33.     return 0;
    
34. }
    

复制代码

改变的是这里

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

如果你深度遍历懂的话，这个广度遍历也是看得懂的，因为我是在深度遍历的基础上修改的。

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. }

复制代码

                               
登录/注册后可看大图

运行结果：

                               
登录/注册后可看大图

如果我把队列的方法可以求出广度遍历，那我就继续把代码加在这个帖子上
我先把作业交了再说哈哈哈哈哈
如果有更快的方法，鱼油萌可以分享一下哦哦哦哦哦~
我觉得我广度代码的运行速度还是太慢了

lightninng

楼主加油！
一个小疑问，似乎广度遍历是使用队列吧？
另外，提供一个开拓思路的尝试，深度遍历是可以使用递归函数的方法实现的，动手试一下，也很有意思~

划句顾

lightninng 发表于 2021-11-26 02:23
楼主加油！
一个小疑问，似乎广度遍历是使用队列吧？
另外，提供一个开拓思路的尝试，深度遍历是可以使用 ...

昂，我昨晚为了赶紧写完作业，广度就搞个栈的（这个应该没错吧，因为我运行的时候确实是广度的结果），队列有想过，但是还没下手。
等一下来尝试一下深度递归和广度队列。

心驰神往

全桥整流

全桥整流

谢谢分享

阿萨德按时

myqf123

楼主加油

myqf123

myqf123

myqf123

100gram

学习下

100gram

100gram

1molHF

牛

tianlai7266

tianlai7266

hornwong

hornwong

青衫烟雨客