图的深度遍历

2019-11-08 01:39:32

字体：大中小

来源：转载

供稿：网友

PRoblem Description 请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。 Input 输入第一行为整数n（0 < n < 100），表示数据的组数。对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m条边，k个顶点。下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。 Output 输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。 Example Input

1 4 4 0 1 0 2 0 3 2 3

Example Output

0 1 2 3

#include <stdio.h>#include <string.h>int a[105][105];int book[105];int n,k,m,i;void dfs(int i){ if(i==0) printf("%d", i); else printf(" %d",i); book[i]=1; int j; for(j=0;j<k;j++) { if(!book[j]&&a[i][j]==1) dfs(j); }}int main(){ int u,v; scanf("%d",&n); while(n--) { memset(a,0,sizeof(a)); memset(book,0,sizeof(book)); scanf("%d%d",&k,&m); for(i=0;i<m;i++) { scanf("%d%d",&u,&v); a[u][v]=a[v][u]=1; } for(i=0;i<k;i++) { if(!book[i]) dfs(i); } printf("/n"); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 152KBSubmit time: 2017-02-17 09:57:55****************************************************/

上一篇：PowerShell文件系统（二）访问文件和目录

下一篇：LeetCode 73. Set Matrix Zeroes