判断无向图连通性 拓扑排序

### 无向图的连通性判断方法

对于无向图来说，连通性的概念是指是否存在一条路径可以从任一顶点到达另一个顶点。为了验证这一点，可以采用广度优先搜索(BFS)或深度优先搜索(DFS)[^5]。

#### 广度优先搜索 (BFS)

通过选取任意一个起始节点并执行一次完整的BFS遍历操作，如果能够访问到所有的其它节点，则说明此图为连通图；反之则不是完全连通的。具体做法如下：

1. 初始化一个布尔类型的数组`visited[]`用于记录哪些节点已经被访问过；
2. 设定初始状态为全部未访问(`false`)；
3. 随机挑选一个起点v作为当前层唯一的活跃节点加入队列Q中，并将其标记为已访问；
4. 当队列不为空时循环取出第一个元素u，依次检查与其相连但尚未被探索过的邻居w们：
- 将它们设为已访问并将之压入队尾等待后续处理。
5. 若最终仍有部分节点处于从未触及的状态即表明整个网络并非单一整体而是由若干独立组件构成。

from collections import deque

def bfs(graph, start_vertex):
    visited = set()
    queue = deque([start_vertex])
    
    while queue:
        vertex = queue.popleft()
        
        if vertex not in visited:
            visited.add(vertex)
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    
    return len(visited), visited

需要注意的是，在实际应用过程中应当考虑输入数据的形式（如邻接矩阵还是列表），上述伪代码假设传入参数graph是以字典形式存储的邻接表结构[^4]。

然而，当提到拓扑排序时，这通常适用于有向无环图(DAG)，而非一般的无向图。因此针对无向图讨论拓扑排序并不恰当，除非先转换成相应的DAG模型或是寻找特定场景下的类比解释[^1]。