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

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

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

提示

用邻接表存储。

来源

先来这道题的代码： #include <stdio.h> #include <stdlib.h> #include <queue> #include <string.h> using namespace std; queue<int> q;//类，定义queue对象 int v[110]; int k; int i,j; typedef struct arcnode { int adj;//边节点的序号 struct arcnode *next;//指向下一个节点的指针 }arcnode; typedef struct vnode {//定义链表的顶点 int data;//顶点的数据 arcnode *first;//指向顶点的下一个节点 }vnode,adjlist[110]; typedef struct//图 { adjlist a;//包含图中所有顶点的链表 int vn,an;//vn为顶点个数，an为弧度个数 }alg; int creat(alg *g) { int v1,v2;//由于输入数据的类型为整形 arcnode *p;//用于遍历每一个链表 scanf("%d %d %d",&g->vn,&g->an,&k); for(i=0;i<g->vn;i++) { g->a[i].first = NULL; //将每一个链表头的指针都置为空 } for(i=0;i<g->an;i++) { scanf("%d %d",&v1, &v2); p=new arcnode; p->adj=v2; p->next=g->a[v1].first; g->a[v1].first=p;//相当于逆序建链表 //此时建立的链表的序列为从大到小， //若按照题目要求的话,需要将链表逆置，也就是元素互换 //无向图对称性 p=new arcnode; p->adj =v1; p->next = g->a[v2].first; g->a[v2].first = p; } return 1; } void bfs(alg *g,int k) { arcnode *p; memset(v,0,sizeof(v)); //将数组内的元素全部置为0 v[k]=1;//此节点已访问过标记为1 q.push(k);//将此节点的序号入栈 printf("%d",k); while(!q.empty()) {//当队列不为空的时候，说明此时图中节点 //仍未遍历完毕 i=q.front();//取出队头元素复制给i q.pop();//删除队头元素 p=g->a[i].first;//将此节点链表头指针赋给p { while(p)//当p不为空的时候，此链表未遍历完毕 { if(!v[p->adj]) {//链表中此数据未曾遍历过 v[p->adj]=1; q.push(p->adj);//即入栈 printf(" %d",p->adj); //输出此元素 } p=p->next;//指针向后移动 } } } } void swap1(alg *g) {//交换链表中元素的次序 int t; arcnode *p,*q; for(i=0;i<g->vn;i++) { for(p=g->a[i].first;p;p=p->next) { for(q=p->next;q;q=q->next) { if(p->adj>q->adj) { t=p->adj; p->adj=q->adj; q->adj=t; } } } } } int main() { int n; alg g; scanf("%d",&n); while(n--) { creat(&g); swap1(&g); bfs(&g,k); } return 0; } 自己的一点想法：

图的邻接表说白了也就是给图中每一个节点都建立一个链表，然后用这个链表储存和这个节点相邻的最近的那几个邻接点，是否有规律的储存无所谓，看题目要求具体调整。

所谓广度优先遍历，就如同树的层次遍历一样，按照开始的那一个节点，一层一层的分别取其最近的节点进行遍历输出，还需要遵守的规则，即“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有的邻接点都被访问到。若此时图中还有邻接点未被访问，则另选一个未被访问的顶点，重复上述过程，直至图中所有节点都被访问到。