图的深度遍历

2019-11-08 00:57:05

字体：大中小

来源：转载

供稿：网友

blablabla: Depth-First-Search 深度优先，无回溯的DFS就是一条路走到黑的孤独= = thought: 简单模板。。。 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 <bits/stdc++.h>#include <stdio.h>using namespace std;bool book[110];bool a[1100][1100];int sum,k,m;void dfs(int cur){ if(sum==0) { printf("%d",cur); } else { printf(" %d",cur); } sum++; if(sum==k) return ; for(int i=0; i<k; i++ ) { if(a[cur][i]==1&&book[i]==0) { book[i]=1; dfs(i); } }}int main(){ int n; while(scanf("%d",&n)!=EOF) { while(n--) { sum=0; memset(a,0,sizeof(a)); memset(book,0,sizeof(book)); scanf("%d%d/n",&k,&m); for(int i=0; i<m; i++) { int u,v; scanf("%d%d",&u,&v); a[u][v]=a[v][u]=1; } book[0]=1; dfs(0); printf("/n"); } } return 0;}

上一篇：ubuntu Redis 数据库远程访问服务

下一篇：93. Restore IP Addresses -Medium