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

刺骨的言语ヽ痛彻心扉 2022-06-05 08:27 50阅读 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

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

#include <iostream>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    int const MAX = 150;
    
    int mmp[MAX][MAX], vt[MAX];
    int flag = 1;
    
    
    
    void bfs(int x, int m)
    {
        queue<int> qu;
        qu.push(x);
        vt[x] = 1;
        while(!qu.empty())
        {
            int tp = qu.front();
            qu.pop();
            if(flag)
            {
                cout << tp;
                flag = 0;
            }
            else
            {
                cout << " " << tp;
            }
            for(int i = 0; i < m; i++)
            {
                if(!vt[i] && mmp[tp][i])//vt表示点是否被访问过
                {
                    qu.push(i);
                    vt[i] = 1;
                }
            }
        }
    
    }
    
    int main()
    {
        int n;
        cin >> n;
        while(n--)
        {
            int m, k, t;
            cin >> k >> m >> t;
            memset(mmp, 0, sizeof(mmp));
            memset(vt, 0, sizeof(vt));
            int u, v;
            for(int i = 0; i < m; i++)
            {
                cin >> u >> v;
                mmp[u][v] = mmp[v][u] = 1;
            }
            flag = 1;
            bfs(t, m);
            cout << endl;
        }
        return 0;
    }