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

爱被打了一巴掌 2022-06-10 12:25 109阅读 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 <bits/stdc++.h>
    using namespace std;
    
    struct  node
    {
        int data;
        node *next;
    };
    node *head[1010], *p;
    void BFS(int s);
    bool Vis[1010];
    int n, m, s;
    
    int main()
    {
        int k;
        cin >> k;
        for(int i = 0; i < 1010; i++)
        {
            head[i] = new node;
        }
        while(k --)
        {
            memset(Vis, 0, sizeof(Vis));
            cin >> n >> m >> s;
            for(int i = 0; i < n; i++)
            {
                head[i] -> next = NULL;
            }
            for(int i = 0; i < m; i++)
            {
                int u, v;
                cin >> u >> v;
                p = new node;
                p -> data = v;
                p -> next = head[u] -> next;
                head[u] -> next = p;
                p = new node;
                p -> data = u;
                p -> next = head[v] -> next;
                head[v] -> next = p;
            }
            BFS(s);
            cout << endl;
        }
        return 0;
    }
    
    void BFS(int s)
    {
    
        for(int i = 0; i < m; i++)//(同一个结点的同层邻接点，节点编号小的优先遍历）排序，将节点小的放在之前;
        {
            for(node *p = head[i] -> next; p; p = p -> next)
            {
                for(node *q = p -> next; q; q = q -> next)
                {
                    if(p -> data > q -> data)
                    {
                        int tmp = p -> data;
                        p -> data = q -> data;
                        q -> data = tmp;
                    }
                }
            }
        }
        int q;
        queue<int >Q;
        Q.push(s);
        Vis[s] = 1;
        while(!Q.empty())
        {
            cout << (q = Q.front()) << ' ';
            Q.pop();
            for(p = head[q] -> next; p; p = p -> next)
            {
                if(!Vis[p -> data])
                {
                    Vis[p -> data] = 1;
                    Q.push(p -> data);
                }
            }
        }
    }
    
    
    /***************************************************
    Result: Accepted
    Take time: 0ms
    Take Memory: 204KB
    Submit time: 2017-02-20 21:11:02
    ****************************************************/