前向星的深度优先搜索

Grade 100 Open Time Friday, 24 July 2020, 10:55 AM
Discount 0.8 Time Discount Friday, 24 July 2020, 10:55 AM
Allow late Yes Close Time Friday, 24 July 2020, 10:55 AM
Input file dfs.in Output file dfs.out

【题目描述】

深度优先搜索法(DFS):想象一只老鼠,在一座不见天日的迷宫内,老鼠在入口处进去,要从出口出来。那老鼠会怎么走?当然是这样的:老鼠如果遇到直路,就一直往前走,如果遇到分叉路口,就任意选择其中的一个继续往下走,如果遇到死胡同,就退回到最近的一个分叉路口,选择另一条道路再走下去,如果遇到了出口,老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样:按照某种条件往前试探搜索,如果前进中遭到失败(正如老鼠遇到死胡同),则退回头另选通路继续搜索(用堆栈实现),直到找到条件的目标为止。

输入一个图,试DFS输出访问顺序

【输入格式】

第一行两个数n,m,表示n个结点数和m条边

随后m行,每行两个数x,y,表示x和y有边相连。

【输出格式】

输出n行,依次为DFS访问的结点顺序

【输入样例】

8 10

1 2

1 3

2 4

2 5

3 6

3 7

4 8

5 8

6 8

7 8

【输出样例】

1

3

7

8

6

5

2

4