首页 > 代码库 > SDUT 2141 【TEST】数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历
SDUT 2141 【TEST】数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历
数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic Discuss
Problem Description
给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点,节点编号小的优先遍历)
Input
输入第一行为整数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顶点的无向边。
对于每组数据,第一行是三个整数k,m,t(0<k<100,0<m<(k-1)*k/2,0< t<k),表示有m条边,k个顶点,t为遍历的起始顶点。
下面的m行,每行是空格隔开的两个整数u,v,表示一条连接u,v顶点的无向边。
Output
输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示BFS的遍历结果。
Example Input
1 6 7 0 0 3 0 4 1 4 1 5 2 3 2 4 3 5
Example Output
0 3 4 2 5 1
Hint
以邻接矩阵作为存储结构。
DQE:
在图的正式实验开始前尝试一下,题目来自练习题,代码作为【尝试练习】可能不完全标准。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 5 using namespace std; /*【尝试练习】*/ 6 7 #define MVN 110 8 #define MW INT_MAX 9 10 typedef struct AdjMatrix 11 { 12 int x; 13 char *info; 14 }AM,adj[MVN][MVN]; 15 16 typedef struct MGraph 17 { 18 int vex[MVN]; 19 adj amp; 20 int vexnum,arcnum; 21 int k; 22 }MG; 23 24 void creat(MG &G) 25 { 26 int i,j,k; 27 for(k=0;k<G.vexnum;k++) 28 { 29 G.vex[k]=k; 30 } 31 for(i=0;i<G.vexnum;i++) 32 { 33 for(j=0;j<G.vexnum;j++) 34 { 35 G.amp[i][j].x=0; 36 } 37 } 38 for(k=0;k<G.arcnum;k++) 39 { 40 scanf("%d %d",&i,&j); 41 G.amp[i][j].x=1; 42 G.amp[j][i].x=1; 43 } 44 } 45 46 void BFS(MG &G) 47 { 48 int out[MVN]; 49 queue <int> Q; 50 int i=0,j,k,m=0; 51 bool visited[MVN]={false}; 52 for(i=0;i<G.vexnum;i++) 53 { 54 if(G.vex[i]==G.k) 55 break; 56 } 57 Q.push(G.vex[i]); 58 while(!Q.empty()) 59 { 60 int e; 61 e=Q.front(); 62 Q.pop(); 63 for(k=0;k<G.vexnum;k++) 64 { 65 if(G.vex[k]==e) 66 { 67 i=k; 68 break; 69 } 70 } 71 if(!visited[e]) 72 { 73 out[m++]=e; 74 visited[i]=true; 75 for(j=0;j<G.vexnum;j++) 76 { 77 if(G.amp[i][j].x==1) 78 Q.push(G.vex[j]); 79 } 80 } 81 } 82 for(k=0;k<G.vexnum-1;k++) 83 { 84 printf("%d ",out[k]); 85 } 86 printf("%d\n",out[G.vexnum-1]); 87 } 88 89 int main() 90 { 91 MG G; 92 int n; 93 scanf("%d",&n); 94 while(n--) 95 { 96 scanf("%d %d %d",&G.vexnum,&G.arcnum,&G.k); 97 creat(G); 98 BFS(G); 99 } 100 return 0; 101 } 102 103 /*************************************************** 104 User name: *** 105 Result: Accepted 106 Take time: 0ms 107 Take Memory: 172KB 108 Submit time: 2016-11-05 22:54:29 109 ****************************************************/
SDUT 2141 【TEST】数据结构实验图论一:基于邻接矩阵的广度优先搜索遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。