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

题目链接：点击打开链接

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

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 <bits/stdc++.h> #include <algorithm> using namespace std; void Creat_graph(int n,int m,int s) { int u,v; queue <int>Q;///利用队列先进先出的特点 int vis[110] = {0};///用以标记，该点是否已经遍历过了 int mp[110][110] = {0};///地图最开始要清零 for(int i = 0;i < m;i++) { scanf("%d%d",&u,&v); mp[u][v] = mp[v][u] = 1; } Q.push(s); vis[s] = 1; while(!Q.empty()) { int p = Q.front(); printf("%d ",p); Q.pop(); for(int j = 0;j < n;j++) { if(mp[p][j] && !vis[j]) { Q.push(j); vis[j] = 1; } } } } int main() { int t; int n,m,s; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&s); Creat_graph(n,m,s); } return 0; }

 hhh   

非STL算法：

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #define Maxsize 1100 using namespace std; int flag; int vis[Maxsize]; struct node { int data; node *next; }; typedef struct { node *Front; node *rear; int height; }Squeue; int Init_Queue(Squeue &Q) { Q.Front = Q.rear = (node *)malloc(Maxsize*sizeof(node)); if(!Q.Front) return -1; Q.Front->next = NULL; Q.rear->next = NULL; Q.height = 0; return 0; } void Push_Queue(Squeue &Q,int Data) { node *p; p = new node; p->data = Data; p->next = NULL; Q.rear->next = p; Q.rear = p; Q.height++; } void Pop_Queue(Squeue &Q) { node *p; p = new node; p = Q.Front->next; Q.Front->next = p->next; if(Q.rear == p) Q.rear = Q.Front; free(p); Q.height--; } int Gettop(Squeue &Q) { node *p; p = new node; p = Q.Front->next; return p->data; } int Is_empty(Squeue &Q) { if(Q.Front == Q.rear) return 1; else return 0; } typedef struct { int vexnum,arcnum,start; int edge[Maxsize][Maxsize]; }Graph; Graph *Creat_Graph(Graph *G) { int u,v; scanf("%d%d%d",&G->vexnum,&G->arcnum,&G->start); for(int i = 0;i < G->vexnum;i++) for(int j = 0;j < G->vexnum;j++) G->edge[i][j] = 0; for(int i = 0;i < G->arcnum;i++) { scanf("%d%d",&u,&v); G->edge[u][v] = G->edge[v][u] = 1; } return G; } void BFS(Graph *G,int k) { Squeue Q; Init_Queue(Q); Push_Queue(Q,k); vis[k] = 1; //int p = Gettop(Q); // printf("%d",k); while(!Is_empty(Q)) { int p = Gettop(Q); if(flag == 1) { printf("%d",p); flag++; } else printf(" %d",p); Pop_Queue(Q); for(int i = 0;i < G->vexnum;i++) { if(!vis[i] && G->edge[p][i]==1) { Push_Queue(Q,i); vis[i] = 1; } } } } void BFSTreavers(Graph *G) { memset(vis,0,sizeof(vis)); BFS(G,G->start); for(int i= 0;i < G->vexnum;i++) if(!vis[i]) BFS(G,i); } int main() { int t; scanf("%d",&t); while(t--) { Graph *G; G = (Graph*)malloc(sizeof(Graph)); G = Creat_Graph(G); flag = 1; BFSTreavers(G); printf("\n"); } return 0; }