连通图的深度优先遍历

连通图的深度优先遍历（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索树的分支，直到不能再继续为止，然后回溯到前一个节点，继续搜索下一个分支。具体步骤如下：

1. 从图中任意一个顶点开始遍历，将该顶点标记为已访问。
2. 访问该顶点的所有未被访问的邻居顶点，并将其标记为已访问。
3. 对于每个已访问的邻居顶点，重复步骤2，直到所有邻居顶点都被访问过。
4. 回溯到前一个节点，重复步骤2和步骤3，直到所有顶点都被访问过。

下面是一个连通图的深度优先遍历的Python实现：

# 定义一个图类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.adj = [[] for i in range(vertices)]  # 邻接表

    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    # DFS遍历
    def DFS(self, v, visited):
        visited[v] = True
        print(v, end=' ')

        for i in self.adj[v]:
            if not visited[i]:
                self.DFS(i, visited)

    # 对每个未被访问的顶点进行DFS遍历
    def DFS_traversal(self):
        visited = [False] * self.V

        for i in range(self.V):
            if not visited[i]:
                self.DFS(i, visited)