鱼C论坛

 找回密码
 立即注册
查看: 16018|回复: 146

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

  [复制链接]
发表于 2021-11-26 00:42:37 | 显示全部楼层 |阅读模式

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

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

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

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

#include<stdio.h>
int visited[105]={0},
     stack[105]={0},
         top=-1;
//初始化图
int init_G(int G[][105],int n)
{
        printf("请输入邻接表矩阵\n");
        int i,j;
        for(i=1;i<n+1;i++)
        {
                for(j=1;j<n+1;j++)
                {
            scanf("%d",&G[i][j]);
                }
        }
        printf("\n");
        return 0;
}
//入栈函数
int push(int data)
{
        stack[++top]=data;
    return 0;
}

//出栈函数
int pop()
{
        stack[top--]=0;
        return 0;
}
游客,如果您要查看本帖隐藏内容请回复
//主函数
int main(){
        int n;
        int G[105][105];
        printf("请输入结点数:");
        scanf("%d",&n);
        init_G(G,n);
        dfs(G,1,n);
        printf("遍历成功!!!\n");
    return 0;
}

                               
登录/注册后可看大图

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


                               
登录/注册后可看大图

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

#include<stdio.h>


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

//初始化图 --中规中矩 
int init_G(int G[][105],int n)
{
        printf("\n请输入邻接表矩阵:\n");
        int i,j;
        for(i=1;i<n+1;i++)
        {
                printf("                  ");
                for(j=1;j<n+1;j++)
                {
            scanf("%d",&G[i][j]);
                }
        }
        printf("\n");
        return 0;
}

//入栈函数
int push(int data)
{
        stack[++top]=data;
    return 0;
}
改变的是这里
游客,如果您要查看本帖隐藏内容请回复

如果你深度遍历懂的话,这个广度遍历也是看得懂的,因为我是在深度遍历的基础上修改的。
//主函数
int main(){
        int n,t;
        int G[105][105];
        printf("请输入结点数:");
        scanf("%d",&n);
        init_G(G,n);   //初始化图 
        printf("请问要从哪个结点开始广度遍历:");
        scanf("%d",&t);
        printf("在第【%d】个结点开始广度遍历的结果为:",t);
        dfs(G,t,n);
    printf("\n"); 
        printf("恭喜你,遍历成功!!!\n");
    return 0;
}


                               
登录/注册后可看大图

运行结果:
运行结果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 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 15:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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