本文主要是介绍NOJ 1047 图的深度优先遍历序列 (DFS + 宣传NOJ)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
图的深度优先遍历序列
总提交 : 1083 测试通过 : 327
题目描述
图(graph)是数据结构 G=(V,E)，其中V是G中结点的有限非空集合,结点的偶对称为边(edge)；E是G中边的有限集合。设V={0,1,2,……,n-1}，图中的结点又称为顶点(vertex)，有向图(directed graph)指图中代表边的偶对是有序的，用<u，v>代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。无向图(undirected graph)指图中代表边的偶对是无序的，在无向图中边(u，v )和(v，u)是同一条边。
输入边构成无向图，求以顶点0为起点的深度优先遍历序列。
输入
第一行为两个整数n、e，表示图顶点数和边数。以下e行每行两个整数，表示一条边的起点、终点，保证不重复、不失败。1≤n≤20，0≤e≤190
输出
前面n行输出无向图的邻接矩阵，最后一行输出以顶点0为起点的深度优先遍历序列，对于任一起点，首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个空格。
样例输入
4 5
0 1
0 3
1 2
1 3
2 3
样例输出
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
0 1 2 3
#include <cstdio>
#include <cstring>
int map[25][25];
bool vis[25];
int n, e;void DFS(int a)
{vis[a] = true;printf("%d ", a);for(int i = 0; i < n; i++)if(map[a][i] && !vis[i])DFS(i);
}int main()
{int x, y;scanf("%d %d", &n, &e);memset(map, 0, sizeof(map));memset(vis, false, sizeof(vis));for(int i = 0; i < e; i++){scanf("%d %d", &x, &y);map[x][y] = 1;map[y][x] = 1;}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++)printf("%d ", map[i][j]);printf("\n");}for(int i = 0; i < n; i++)if(!vis[i])DFS(i);printf("\n");
}
这篇关于NOJ 1047 图的深度优先遍历序列 (DFS + 宣传NOJ)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
