sdut oj2107图的深度遍历(DFS)

题目链接：点击打开链接

图的深度遍历

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 <bits/stdc++.h> #include <algorithm> using namespace std; int mp[110][110];///地图，用矩阵的方式实现 int vis[110];///标记，看该点是否已经遍历过 int edgenum,vexnum; void DFS(int n) { if(n == 0) printf("%d",n); else printf(" %d",n); vis[n] = 1; for(int j = 0;j < vexnum;j++) { if(!vis[j] && mp[n][j]) DFS(j); } } int main() { int t; int u,v; scanf("%d",&t); while(t--) { memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); scanf("%d%d",&vexnum,&edgenum); for(int i = 0;i < edgenum;i++) { scanf("%d%d",&u,&v); mp[u][v] = mp[v][u] = 1; } DFS(0); printf("\n"); } return 0; }

 标准写法：

#include <bits/stdc++.h> using namespace std; #define maxsize 110 int f; bool vis[maxsize]; typedef int element; typedef struct { element vex[maxsize]; element arc[maxsize][maxsize]; int vexnum,arcnum; } Graph; Graph *Creat_Graph() { int u,v; Graph *G; G = (Graph *)malloc(sizeof(Graph)); scanf("%d%d",&G->vexnum,&G->arcnum); for(int i = 0; i < G->vexnum; i++) G->vex[i] = i; for(int i = 0; i < G->vexnum; i++) for(int j = 0; j < G->vexnum; j++) G->arc[i][j] = 0; for(int i = 0; i < G->arcnum; i++) { scanf("%d%d",&u,&v); G->arc[u][v] = G->arc[v][u] = 1; } return G; } void DFS(Graph *G,int n) { vis[n] = true; printf(f ? "%d" : " %d",G->vex[n]); f = 0; for(int i = 0; i < G->vexnum; i++) { if(G->arc[n][i]&&!vis[i]) DFS(G,i); } } void DFSTraverse(Graph *G) { for(int i = 0; i < G->vexnum; i++) vis[i] = false; for(int i = 0; i < G->vexnum; i++) { if(!vis[i]) DFS(G,i); } } int main() { int t; scanf("%d",&t); while(t--) { Graph *G; G = Creat_Graph(); f = 1; DFSTraverse(G); printf("\n"); } return 0; }