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

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int mmap[100][100];
int vv[100];
void bfs(int t,int n)
{queue<int>Q;Q.push(t);vv[t]=1;int f=1;int q;while(!Q.empty()){q=Q.front();Q.pop();if(f){f=0;printf("%d",q);}else printf(" %d",q);for(int i=0;i<n;i++)//找与q点相连接的点{if(!vv[i]&&mmap[q][i])//mmap[q][i]==1表示q点与i点相连接，!vv[i]表示i点没有找过{Q.push(i);vv[i]=1;}}}
}
int main()
{int n,k,m,t;int i,j;int u,v;scanf("%d",&n);while(n--){memset(mmap,0,sizeof(mmap));memset(vv,0,sizeof(vv));scanf("%d%d%d",&k,&m,&t);for(i=0;i<m;i++){scanf("%d%d",&u,&v);mmap[u][v]=mmap[v][u]=1;}bfs(t,k);}return 0;
}

题目描述

输入

输出

示例输入

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

示例输出

0 3 4 2 5 1

提示

//#include <iostream>
//#include <stdlib.h>
//#include <stdio.h>
//#include <string.h>
//#include <queue>
//#define M 20
//#define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
//using namespace std;
//struct node
//{
//    int u,v;
//    node *next;
//}*head[M];
//int vv[M],f=1;
//int cmpp(const void *a,const void *b)
//{
//    return (*(int *)a-*(int *)b);
//}
//void add(int u,int v)
//{
//    node *p=new node;
//    p->v=v;
//    p->next=head[u];
//    head[u]=p;
//}
//int b[100],x[100];
//void bfs(int t)
//{
//    int q,k=0;
//    queue<int>Q;
//    Q.push(t);
//    vv[t]=1;
//    f=1;
//    while(!Q.empty())
//    {
//        q=Q.front();
//        Q.pop();
//        x[++k]=q;
//        int i=0;
//        for(node *p=head[q];p!=NULL;p=p->next)
//        {
//            if(vv[p->v]==0)
//            {
//                b[i++]=p->v;
//                vv[p->v]=1;
//            }
//        }
//        if(i>=1)qsort(b,i,sizeof(b[0]),cmpp);
//        for(int j=0;j<=i-1;j++)
//            Q.push(b[j]);
//    }
//    int j;
//    for( j=1;j<=k-1;j++)
//        printf("%d ",x[j]);
//    printf("%d",x[j]);
//}
//
//struct N
//{
//    int u,v;
//} num[100];
//int cmp(const void *a,const void *b)
//{
//    return (((N *)b)->v-((N *)a)->v);
//}
//int main()
//{
//    int n,k,m;
//    int i,j;
//    int u,v,t;
//    scanf("%d",&n);
//    while(n--)
//    {
//        scanf("%d %d %d",&k,&m,&t);
//        memset(head,NULL,sizeof(head));
//        memset(vv,0,sizeof(vv));
//        for(i=0; i<m; i++)
//        {
//            scanf("%d%d",&u,&v);
//            add(u,v);
//            add(v,u);
//        }
//        bfs(t);
//        printf("\n");
//    }
//    return 0;
//}
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#define M 20
#define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
using namespace std;
struct node
{int u,v;node *next;
}*head[M];
int vv[M],f=1;void add(int u,int v)
{node *p=new node;p->v=v;p->next=head[u];head[u]=p;
}
int n,k,m;
int b[100],x[100];
void bfs(int t)
{int q,k=0;queue<int>Q;Q.push(t);vv[t]=1;f=1;while(!Q.empty()){q=Q.front();Q.pop();if(f){f=0;printf("%d",q);}else printf(" %d",q);for(node *p=head[q]; p!=NULL; p=p->next){if(vv[p->v]==0){Q.push(p->v);vv[p->v]=1;}}}
}struct N
{int u,v;
} num[100];int main()
{int i,j;int u,v,t;scanf("%d",&n);while(n--){scanf("%d %d %d",&k,&m,&t);memset(head,NULL,sizeof(head));memset(vv,0,sizeof(vv));for(i=0; i<m; i++){scanf("%d %d",&u,&v);add(u,v);add(v,u);}int tt;for(int i=0; i<m; i++)//对邻接链表排序{node *p,*q;for(p=head[i]; p; p=p->next)for(q=p->next; q; q=q->next){if(p->v>q->v)swap(p->v,q->v,tt);}}bfs(t);printf("\n");}return 0;
}