图的深度遍历

图的深度遍历

Time Limit: 1000MS Memory limit: 65536K

题目描述

请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。

输入

输入第一行为整数n（0 < n < 100），表示数据的组数。 对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m条边，k个顶点。 下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

输出

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。

示例输入

1 4 4 0 1 0 2 0 3 2 3

示例输出

0 1 2 3

#include <stdio.h> #include <stdlib.h> #include <string.h> #include<queue> #define INF = 0x3f3f3f3f #define MAX 100 using namespace std; typedef struct arcnode { int adj; } arcnode, adjmatrix[110][110]; typedef struct { adjmatrix a; int vn; int an; } MG; int i, j; int create(MG &g, int n, int m) { int v1, v2; g.vn = n; g.an = m; for(i=0; i<g.vn; i++) for(j=0; j<g.vn; j++) g.a[i][j].adj = 0; for(i=0; i<g.an; i++) { scanf("%d %d", &v1, &v2); g.a[v1][v2].adj = 1; g.a[v2][v1] = g.a[v1][v2]; } return 1; } int v[110]; void dfs(MG &g, int i) { int j; //若不在函数内定义则无法回溯 v[i] = 1; for(j=0; j<g.vn; j++) { if(g.a[i][j].adj==1&&!v[j]) { printf(" %d", j); dfs(g, j); } } } int main() { int t; int n, m; MG g; scanf("%d", &t); while(t--) { memset(v, 0, sizeof(v)); scanf("%d %d", &n, &m); create(g, n, m); printf("0");//为了控制格式 dfs(g, 0); if(t!=0) printf("\n"); } }

#include <stdio.h> #include <stdlib.h> #include <queue> #include <string.h> using namespace std; int a[110][110]; int v[110]; int b[110]; int n, m; int k; void dfs(int i) { int j; v[i] = 1; b[k++] = i; for(j=0; j<n; j++) { if(a[i][j]==1&&!v[j]) { dfs(j); } } } int main() { int i, j, t, v2, v1; scanf("%d", &t); while(t--) { k = 0; memset(v, 0, sizeof(v)); scanf("%d %d", &n, &m); for(i=0; i<n; i++) for(j=0; j<n; j++) a[i][j] = 0; while(m--) { scanf("%d %d", &v1, &v2); a[v1][v2] = a[v2][v1] = 1; } dfs(0); for(i=0; i<k; i++) { if(i!=k-1) printf("%d ", b[i]); else printf("%d\n", b[i]); } } }