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

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

Time Limit: 1000MS Memory limit: 65536K

题目描述

给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

输入

输入第一行为整数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顶点的无向边。

输出

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

示例输入

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

示例输出

0 3 4 2 5 1

提示

用邻接表存储。

基本思路：1.用一个指针数组来存储图的信息 例如 0 3 ; 0 4 ;两组数据之后 head[0]=NULL 变为 head[0]->3->4->NULL , 同理head[3]->0->NULL ; head[4]->0->NULL ;

2.用一个bool类型的vis数组记录路径 (1 0 记录 来过 没来过);

///Accode

#include <bits/stdc++.h> using namespace std; const int maxn=1010; bool vis[maxn]; /// 0 is stand for not came this point typedef struct Graph /// 邻接表 { int data; Graph *next; } Graph,*Gra; Gra head[maxn]; ///指针类型的数组 void Insert(Gra &head,int x) /// 元素插入到邻接表的函数 { Gra q,a,in; in=new Graph; ///in 是要插入的节点 in->data=x; in->next=NULL; if (head==NULL) ///如果 head==null 说明这个节点还没存过元素 所以直接把顶点x插入 { head=new Graph; head->next=in; in->next=NULL; } else ///否则 将顶点插入到最后 { q=head; ///q 是 a 的前驱节点 a=q->next; while (a) { q=q->next; a=a->next; } q->next=in; ///新进来的元素插入尾部 in->next=NULL; } } void BFS (int t) ///广搜 { int now; Gra p,a; vis[t]=1; ///利用vis数组来判断是否来过此点 queue <int> q; q.push(t); while(!q.empty()) { now =q.front(); q.pop(); cout<<now<<" "; if (head[now]) ///如果head[now] 不为空 寻找以它为头节点的链表... { p=head[now]; a=p->next; while (a) { if (!vis[a->data]) { q.push(a->data); vis[a->data]=1; ///标记 "来过" } a=a->next; } } } } int main() { int i,n,k,m,t; int u,v; cin>>n; while (n--) { cin>>k>>m>>t; memset(vis,0,sizeof(vis)); ///visit 数组初始化 for (i=0; i<k; i++) ///head[]初始化,类似邻接矩阵的 0 初始化 { head[i]=NULL; } for (i=1; i<=m; i++) { cin>>u>>v; Insert(head[u],v); Insert(head[v],u); ///无向图 } BFS(t); } return 0; }

有关邻接表的传送门  http://blog.csdn.net/gentle_guan/article/details/52222573