论坛 › 数据结构与算法 › 图的遍历：深度和广度

划句顾 发表于 2021-11-26 00:42:37

图的遍历：深度和广度

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

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

#include<stdio.h>

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

//出栈函数
int pop()
{
        stack=0;
        return 0;
}
**** Hidden Message *****
//主函数
int main(){
        int n;
        int G;
        printf("请输入结点数：");
        scanf("%d",&n);
        init_G(G,n);
        dfs(G,1,n);
        printf("遍历成功！！！\n");
    return 0;
}
static/image/hrline/5.gif
运行结果：


static/image/hrline/5.gif
第二：广度遍历{:10_256:}
代码如下：
这些基本不变，和上面的深度遍历差不多
/**********************************
*author : LaoGu
*time   :2021/11/25
*fuction:图的广度遍历 --没有用队列，用的是栈
**********************************/

#include<stdio.h>


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

//初始化图 --中规中矩
int init_G(int G[],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);
                }
        }
        printf("\n");
        return 0;
}

//入栈函数
int push(int data)
{
        stack[++top]=data;
    return 0;
}

改变的是这里
**** Hidden Message *****
如果你深度遍历懂的话，这个广度遍历也是看得懂的，因为我是在深度遍历的基础上修改的。
//主函数
int main(){
        int n,t;
        int G;
        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;
}

static/image/hrline/5.gif
运行结果：


static/image/hrline/5.gif
如果我把队列的方法可以求出广度遍历，那我就继续把代码加在这个帖子上{:10_282:}
我先把作业交了再说哈哈哈哈哈{:10_279:}

如果有更快的方法，鱼油萌可以分享一下哦哦哦哦哦~{:10_303:}
我觉得我广度代码的运行速度还是太慢了{:10_262:}

lightninng 发表于 2021-11-26 02:23:29

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

划句顾 发表于 2021-11-26 08:19:30

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

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

心驰神往 发表于 2021-11-26 09:16:36

{:5_109:}

全桥整流 发表于 2021-11-26 09:22:44

{:5_109:}

全桥整流 发表于 2021-11-26 09:23:37

谢谢分享

阿萨德按时 发表于 2021-11-26 09:26:18

{:10_254:}

myqf123 发表于 2021-11-26 10:02:20

楼主加油

myqf123 发表于 2021-11-26 10:02:57

{:5_109:}

myqf123 发表于 2021-11-26 10:03:44

{:5_99:}

myqf123 发表于 2021-11-26 10:04:15

{:5_92:}

100gram 发表于 2021-11-26 11:34:32

学习下

100gram 发表于 2021-11-26 11:35:08

{:10_256:}

100gram 发表于 2021-11-26 11:35:44

{:10_245:}

1molHF 发表于 2021-11-26 11:47:23

牛

tianlai7266 发表于 2021-11-26 12:37:29

{:10_254:}

tianlai7266 发表于 2021-11-26 12:40:01

{:10_254:}

hornwong 发表于 2021-11-26 23:02:39

{:5_95:}

hornwong 发表于 2021-11-26 23:03:12

{:5_95:}

青衫烟雨客 发表于 2021-11-27 00:00:27

{:10_254:}{:10_254:}

查看完整版本: 图的遍历：深度和广度