南阳高质量建设大城市网站,装饰网站建设网,app订制,wordpress顶部菜单怎么删题目描述 给定一个无向连通图#xff0c;顶点编号从0到n-1#xff0c;用广度优先搜索(BFS)遍历#xff0c;输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点#xff0c;节点编号小的优先遍历#xff09;输入 输入第一行为整数n#xff08;0 n 100#xf… 题目描述
给定一个无向连通图顶点编号从0到n-1用广度优先搜索(BFS)遍历输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点节点编号小的优先遍历输入
输入第一行为整数n0 n 100表示数据的组数。 对于每组数据第一行是三个整数kmt0k1000m(k-1)*k/20 tk表示有m条边k个顶点t为遍历的起始顶点。 下面的m行每行是空格隔开的两个整数uv表示一条连接uv顶点的无向边。输出
输出有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 iostream #includecstdio #includecstdlib #includecstring #includequeue #define max 100 using namespace std; queueintq;//将访问过的节点保存到队列 typedef int element; typedef struct arcnode//表结点结构 { element adj;//该弧所指向的顶点的位置 arcnode *next;//指向下一条弧的指针 }arcnode; typedef struct vnode//头结点结构 { element data;//顶点信息 arcnode *first;;//指向第一条依附该顶点的弧的指针 }vnode,adjlist[max]; typedef struct //图的结构 { adjlist a; int vn,an;//图的当前顶点数和弧数 }ALG; element k;//初始顶点 element i,j; element create(ALG g) { element v1,v2; arcnode *p; scanf(%d%d%d,g.vn,g.an,k); for(i0;ig.vn;i) g.a[i].firstNULL; for(i0;ig.an;i) { scanf(%d%d,v1,v2); pnew arcnode; p-adjv2; p-nextg.a[v1].first;//逆序建立链表 g.a[v1].firstp; //无向图的对称性 pnew arcnode; p-adjv1; p-nextg.a[v2].first; g.a[v2].firstp; } return 1; } element v[110];//当前要访问的节点 void bfs(ALG g,element k) { arcnode *p; memset(v,0,sizeof(v));//标记数组的初始化 v[k]1; q.push(k); printf(%d,k); while(!q.empty()) { iq.front(); q.pop(); pg.a[i].first; { while(p)//依次搜索vi的邻接点vj(p-adj相当于j) { if(!v[p-adj]) { v[p-adj]1; q.push(p-adj); printf( %d,p-adj); } pp-next; } } } } void Swap(ALG g)//保证(同一个结点的同层邻接点节点编号小的优先遍历 { element t; arcnode *p,*q; for(i0;ig.vn;i) for(pg.a[i].first;p;pp-next) for(qp-next;q;qq-next) if(p-adjq-adj) { tp-adj; p-adjq-adj; q-adjt; } } element main() { element n; ALG g; scanf(%d,n); while(n--) { create(g);//构建邻接表 Swap(g);//邻接表排序 bfs(g,k);//广度优先遍历 printf(\n); } return 0; } #includeiostream #includequeue #includecstdio #includecstring using namespace std; int map[110][110],vis[110]; void bfs(int t,int n) { queueintq; int flag1; q.push(t); vis[t]1; while(!q.empty()) { int pq.front(); q.pop(); if(flag) {flag0;printf(%d,p);} else printf( %d,p); for(int i0;in;i) {if(!vis[i]map[i][p]) {q.push(i); vis[i]1;} } } } int main() { int T; cinT; while(T--) { memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); int n,m,t; cinnmt; while(m--) { int v,u; cinuv; map[u][v]map[v][u]1; } bfs(t,n); } } #includecstring #includealgorithm #includecstdio #includequeue #includeiostream using namespace std; struct node {int u,v; node *next; }*head[22]; int vis[22],flag1; void add(int u,int v)//顺序建表 {node *pnew node; p-vv; p-nexthead[u]; head[u]p; } int n,k,m; //int b[110],x[110]; void bfs(int t) { int p; queueintq; q.push(t); vis[t]1; flag1; while(!q.empty()) { pq.front(); q.pop(); if(flag) {flag0,printf(%d,p);} else printf( %d,p); for(node *hhead[p];h;hh-next) { if(vis[h-v]0) { q.push(h-v); vis[h-v]1; } } } } int main() { int i; int u,v,t; cinn; while(n--) { cinkmt; memset(head,NULL,sizeof(head)); memset(vis,0,sizeof(vis)); for(i0;im;i) {cinuv; add(u,v); add(v,u); } for(int i0;im;i) { node *p,*q; for(phead[i];p;pp-next)//对邻接链表排序 { for(qp-next;q;qq-next) { if(p-vq-v) swap(p-v,q-v); } } } bfs(t); printf(\n); } }
