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

#include<bits/stdc++.h> using namespace std; typedef struct no { int num; struct no *next; }node; node *head[105]; int visit[10000]; void creat(int u,int v) { node *p; p=new node; p->num=v; p->next=head[u]; head[u]=p; } int bfs(int b,int k) { node *p; queue<int> q; q.push(b); visit[b]=1; int flag=1; while(!q.empty()) { int h=q.front(); q.pop(); if(flag) { flag=0; printf("%d",h);} else {printf(" %d",h);} for(p=head[h];p!=NULL;p=p->next) { if(!visit[p->num]) { q.push(p->num); visit[p->num]=1; } } } return 0; } int main() { node *p,*q; int n,k,m,t,i,u,v,jh; scanf("%d",&n); while(n--) { memset(head,NULL,sizeof(node)); memset(visit,0,sizeof(visit)); scanf("%d %d %d",&k,&m,&t); for(i=0;i<m;i++) { scanf("%d %d",&u,&v); creat(u,v); creat(v,u); } for(i=0;i<k;i++) { for(p=head[i];p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->num>q->num) { jh=p->num; p->num=q->num; q->num=jh; } } } } bfs(t,k); printf("\n"); } return 0; }