#4169. 图的深搜遍历练习题

图的深搜遍历练习题

编程题:图的深度优先遍历 【题目描述】

给定一张有向图,图的顶点编号为 0 到 7,共包含若干条有向边。请使用深度优先搜索(DFS算法对图进行遍历,并输出所有访问顺序。

对所有编号从小到大的顶点进行尝试,如果某个顶点未被访问,就以它为根开始一次 DFS。

图的结构如下图所示(也见下方“图中边列表”):

【输入格式】 无输入。请直接在程序中定义图中边关系。

【输出格式】 输出所有顶点的 DFS 遍历顺序。用空格隔开。

adj[0].push_back(4);  // 0 → 4
adj[0].push_back(7);  // 0 → 7
adj[1].push_back(0);  // 1 → 0
adj[1].push_back(2);  // 1 → 2
adj[1].push_back(3);  // 1 → 3
// 2 无邻接点
adj[3].push_back(1);  // 3 → 1
adj[3].push_back(2);  // 3 → 2
adj[3].push_back(7);  // 3 → 7
adj[4].push_back(6);  // 4 → 6
adj[4].push_back(7);  // 4 → 7
adj[5].push_back(4);  // 5 → 4
adj[6].push_back(5);  // 6 → 5
adj[7].push_back(5);  // 7 → 5