（算法竞赛）图论+DFS深搜——图的dfs遍历1
题目描述
给定一个无向图，包含 n 个顶点（编号为 1 到 n）和 e 条边。要求从顶点 1 开始进行深度优先搜索（DFS），并按照访问顺序输出遍历结果。注意：当存在多个邻接点时，优先访问编号较小的顶点。
输入格式
第一行输入两个整数 n 和 e，表示顶点数和边数。
接下来 e 行，每行输入两个整数，表示一条边的两个顶点。
输出格式
输出一行，包含 DFS 的访问顺序，顶点编号用空格隔开。
解题思路
深度优先搜索（DFS）是一种用于遍历或搜索图的经典算法。其核心思想是尽可能深地访问图的节点，直到无法继续深入时回溯。本题的关键点在于：
图的存储：使用邻接矩阵存储图的结构，便于快速查询两个顶点之间是否存在边。
遍历顺序：当存在多个未访问的邻接点时，按顶点编号从小到大访问。
递归实现：通过递归隐式利用系统栈，简化代码逻辑。
代码解析
def dfs(x):
f[x] = 1 # 标记当前顶点已访问
print(x, end=' ') # 输出当前顶点
for i in range(1, n+1):
# 遍历所有顶点，检查是否为邻接点且未访问
if a[x][i] == 1 and f[i] == 0:
dfs(i) # 递归访问邻接点
# 初始化邻接矩阵和访问标记数组
a = [[0] * 20 for _ in range(20)]
f = [0] * 20
n, e = map(int, input().split())
# 读取边并填充邻接矩阵
for _ in range(e):
x, y = map(int, input().split())
a[x][y] = 1
a[y][x] = 1
dfs(1) # 从顶点1开始DFS代码逐段说明：
邻接矩阵初始化
a 是一个 20x20 的二维数组（题目顶点数最多为15），a[x][y] = 1 表示顶点 x 和 y 之间存在边。
DFS函数
f[x] = 1：标记顶点 x 已访问，避免重复访问。
循环遍历所有顶点（1 到 n），若顶点 i 是 x 的邻接点且未被访问，则递归调用 dfs(i)。
输入处理
读取边信息，并在邻接矩阵中双向标记（因为是无向图）。
示例分析
以样例输入为例：
4 4
1 2
1 3
1 4
2 4
邻接矩阵构建后，顶点1的邻接点为2、3、4。遍历顺序如下：
访问顶点1，输出 1。
按编号顺序检查邻接点：先访问顶点2，输出 2。
顶点2的邻接点为1和4，1已访问，访问4，输出 4。
顶点4的邻接点1和2均已访问，回溯到顶点2，再回溯到顶点1。
继续检查顶点1的下一个邻接点3，输出 3。
最终输出为 1 2 4 3，与样例一致。
总结
时间复杂度：邻接矩阵的DFS时间复杂度为 O(n²)，本题顶点数较小（n ≤ 15），完全可行。
空间复杂度：使用邻接矩阵存储图，空间复杂度为 O(n²)。
递归特点：代码简洁，但需注意递归深度。本题数据规模下无需担心栈溢出。
此解法严格遵循DFS的遍历规则，并通过编号顺序确保邻接点的访问顺序，适合初学者理解DFS的基本原理。