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

我不是女神ヾ 2022-05-17 09:38 112阅读 0赞

给定一个无向连通图，顶点编号从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的遍历结果。

Sample Input

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

Sample Output

0 3 4 2 5 1

Hint

用邻接表存储。

需要注意的点就是用邻接表存储图以及从小到大遍历节点，需要对邻接表进行排序；

#include<bits/stdc++.h>
    using namespace std;
    int book[1001];
    int n,m,s;
    struct sdut
    {
        int data;
        sdut *next;
    }*head[1010],*p,*q;
    void bfs(int x)
    {
        for(int i = 0; i < m; i++)///(同一个结点的同层邻接点，节点编号小的优先遍历）排序，将节点小的放在之前;
        {
            for(p = head[i] -> next; p!=NULL; p = p -> next)
            {
                for(q = p -> next; q!=NULL; 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);
        book[s]=1;
        while(!Q.empty())
        {
            cout<<(q=Q.front())<<" ";
            Q.pop();
            for(p=head[q]->next;p;p=p->next)
            {
                if(!book[p->data])
                {
                    book[p->data]=1;
                    Q.push(p->data);
                }
            }
        }
    }
    int main()
    {
        int k;
        cin>>k;
        for(int i=0;i<1010;i++)
            head[i]=new sdut;
        while(k--)
        {
            memset(book,0,sizeof(book));
            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 sdut;
                p->data=v;
                p->next=head[u]->next;///逆序建立链表；
                head[u]->next=p;
                p=new sdut;
                p->data=u;  ///构建无向图；
                p->next=head[v]->next;
                head[v]->next=p;
            }
            bfs(s);
            cout<<endl;
        }
        return 0;
    }