无向图的连通性判别【深度优先搜索 (DFS)】从任一顶点开始，访问该顶点及其所有邻接点

# 1. 介绍

在本章中，我们将介绍无向图的连通性判别问题以及深度优先搜索（DFS）算法的概述。让我们逐步深入了解这些概念。

# 2. 深度优先搜索（DFS）算法原理

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在这一章节中，我们将深入探讨DFS算法的原理和实现方式。

#### 2.1 DFS 算法的基本思想
DFS算法从图的某个顶点开始，沿着一条路径不断往下探索，直到不能再继续为止，然后回退到上一个未探索的节点继续探索。具体来说，DFS会优先往深度方向搜索，直到已访问到的节点不能再继续深入为止，然后回溯到上一个节点，尝试探索其他路径。

#### 2.2 DFS 的递归实现
DFS算法可以通过递归的方式实现。伪代码如下：

def dfs_recursive(graph, v, visited):
    visited[v] = True
    # 对当前节点v的邻居节点进行遍历
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

在递归实现中，我们标记当前节点为已访问，并递归调用DFS函数来访问其邻居节点，直到所有相邻节点都被访问完为止。

#### 2.3 DFS 的迭代实现（使用栈）
除了递归方式，DFS还可以通过显式地使用栈来实现。伪代码如下：

def dfs_iterative(graph, start):
    stack = [start]
    visited = set()
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            # 遍历当前节点的邻居节点
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

在迭代实现中，我们使用一个栈来保存待访问的节点。从初始节点开始，不断将未访问的邻居节点入栈，直到所有节点都被访问完为止。

通过递归和迭代方式实现的DFS可以帮助我们在无向图中进行深度优先搜索，从而实现连通性判别等功能。

# 3. 从任一顶点开始的连通性判别

在无向图中，判断其连通性是一个非常重要的问题。连通性指的是图中任意两个顶点之间是否存在路径。通过深度优先搜索（DFS）算法，我们可以有效地对无向图的连通性进行判别。

#### 3.1 如何从单个顶点开始对无向图进行连通性判别？

在无向图中，我们可以从任意一个顶点开始，利用DFS算法，来遍历图中所有可达的顶点。如果遍历结束后，所有的顶点都被访问到了，那么这个图就是连通的；否则，如果有未被访问到的顶点，则说明这个图不是连通的。