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

ゝ一纸荒年。 2022-07-10 06:28 125阅读 0赞

数据结构实验之图论一：基于邻接矩阵的广度优先搜索遍历  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
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

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

用了两个方法，一个没用队列的output limit了，用的是递归  
这里是代码

#include <stdio.h>
    #include <stdlib.h>
    
    int map[111][111];
    int visited[111];
    int ans[111];
    
    int in = 1,out = 0;
    int k;
    
    void BFS(int t)
    {
        int i;
        out++;
        for(i=0; i<k; i++){
            if(map[t][i]==1&&visited[i]==0){
                visited[i] = 1;
                ans[in++] = i;
            }
        }
        if(in>=out)
            BFS(ans[out]);
    }
    
    int main()
    {
        int n;
        int m,t,u,v;
        int i;
        scanf("%d",&t);
        while(t--){
            memset(visited,0,sizeof(visited));
            memset(map,0,sizeof(map));
            scanf("%d %d %d",&k,&m,&t);
            for(i=0; i<m; i++){
                scanf("%d %d",&u,&v);
                map[u][v] = map[v][u] = 1;
            }
            ans[0] = t;
            visited[t] = 1;
            BFS(t);
            for(i=0; i<k-1; i++)
                printf("%d ",ans[i]);
            printf("%d\n",ans[i]);
        }
        return 0;
    }

还有一个是用队列的，榜榜眼眼的用bfs的方法做的

#include <iostream>
    #include <queue>
    #include <string.h>
    
    using namespace std;
    
    int map[111][111];
    int visited[111];
    int a[111],in;
    int k;
    
    void bfs(int t)
    {
        queue<int> q;
        for(int i=0; i<k; i++){
            if(visited[t]==0){
                visited[t] = 1;
                a[in++] = t;
                q.push(t);
                while(!q.empty()){
                    int v = q.front();
                    q.pop();
                    for(int i=0; i<k; i++){
                        if(visited[i]==0&&map[v][i]==1){
                            visited[i] = 1;
                            a[in++] = i;
                            q.push(i);
                        }
                    }
                }
            }
        }
    }
    
    int main()
    {
        int n,u,v;
        int m,t;
        cin>>n;
        while(n--){
            memset(map,0,sizeof(map));
            memset(visited,0,sizeof(visited));
            cin>>k>>m>>t;
            for(int i=0; i<m; i++){
                cin>>u>>v;
                map[u][v] = map[v][u] = 1;
            }
            in = 0;
            bfs(t);
            for(int i=0; i<in; i++){
                if(i==0)
                    cout<<a[i];
                else
                    cout<<" "<<a[i];
            }
            cout<<endl;
        }
        return 0;
    }

唉，宿舍好吵，该死的。我要睡觉了啊！