数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

本是古典何须时尚 2022-07-12 06:37 164阅读 0赞

think:  
1 今天晚上截止现在只AC了这道新题，明天又要开新课了，作为一名学渣，感觉在504真的好锻炼自己，真希望自己可以留在ACM，希望这样的时光还能再多些，虽然感觉每天挺累的，但作为平常人要想和天才们减少差距，有时候拼命努力或许才能仅仅跟上他们正常的进度学习，之前看过一篇文章，写到过在一所中等大学，或许会遇到比自己聪明的，比自己努力的，既比自己聪明又比自己努力的，但是却基本不可能遇到顶尖一流大学那些比你聪明五倍勤奋十倍的同学，他们每一步付出的艰辛不是我所能想象的，自己能够遇见ACM和身边可爱的小伙伴们，或许是自己大学生活最美好的部分，不要彷徨，不要怀疑自己，静下心来，坚强前行。  
2 得回归正题了，题目作为一道广度优先搜索遍历的基础题目，很适合理解广度优先搜索遍历的BFS函数，其实BFS函数也是结合了队列思想，符合入队条件的入队，符合出队操作的执行出队，需要注意的是要用一个数组visit\[\]记录当前判断的位置是否已经入队，否则极可能会形成死循环。自己一开始初始输入t的visit\[t\]再度变化时候错误，导致多输出一遍t，注意细节  
3一开始自己关于memset函数的应用混淆，导致错误的使用memset试图将整型数组初始化为1，memset对数组操作时候只能将数组初始化为0或-1，自己基础知识不扎实已经开始影响自己，希望自己重视日常的小错误，深入理解改正错误

[sdut原题链接][sdut]

数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

Input  
输入第一行为整数n（0< n <100），表示数据的组数。  
对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)\*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。  
下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

Output  
输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

Example Input  
1  
6 7 0  
0 3  
0 4  
1 4  
1 5  
2 3  
2 4  
3 5

Example Output  
0 3 4 2 5 1

Hint  
以邻接矩阵作为存储结构。  
Author

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    int a[104][104], visit[104];
    int link[104], tp, op;
    void BFS(int n)
    {
        op++;
        for(int i = 0; i < 104; i++)
        {
            if(a[n][i] == 1 && visit[i] == 1)
            {
                link[tp++] = i;
                visit[i] = 0;
            }
        }
        if(op <= tp)
            BFS(link[op]);
    }
    int main()
    {
        int n, k, m, t, i;
        scanf("%d", &n);
        while(n--)
        {
            memset(a, 0, sizeof(a));
            ///memset(visit, 1, sizeof(visit));
            /* memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作， 其返回值为指向s的指针。该函数对数组操作时只能用于数组的置0或-1，其他值无效。*/
            for(i = 0; i < 104; i++)
                visit[i] = 1;
            tp = op = 0;
            scanf("%d %d %d", &k, &m, &t);
            for(i = 0; i < m; i++)
            {
                int u, v;
                scanf("%d %d", &u, &v);
                a[u][v] = a[v][u] = 1;
            }
    
            link[tp++] = t;
            visit[t] = 0;
            BFS(t);
    
            for(i = 0; i < tp; i++)
            {
                printf("%d%c", link[i], i == tp-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 148KB
    Submit time: 2017-02-14 21:28:16
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2141.html