有向图连通性判断算法伪代码

在有向图中判断两个顶点是否连通，常用的是深度优先搜索 (Depth First Search, DFS) 或广度优先搜索 (Breadth First Search, BFS) 算法。以下是使用DFS的简单伪代码：

function isConnected(digraph G, startVertex):
    visited = set() // 存放已访问过的顶点
    stack = [startVertex] // 初始化栈

    while stack:
        vertex = stack.pop() // 弹出栈顶节点
        if vertex not in visited:
            visited.add(vertex)
            for neighbor in digraph[vertex]: // 遍历该节点的所有邻居
                if neighbor not in visited:
                    stack.append(neighbor) // 将未访问的邻居压入栈
                    return False  # 如果发现未访问的节点，说明不是连通的

    return True  // 如果遍历完所有节点都没有返回False，表示连通

相关问题

判断一个无向图是否是连通图，若不是连通的，输出图中连通分量的个数 要求:档中包含伪代码、可编辑可执行的实际高级语言代码

判断一个无向图是否是连通图，通常可以采用深度优先搜索（DFS）或者广度优先搜索（BFS）算法。这里给出一个基于Python的简单示例，使用BFS法：

# 使用邻接列表表示无向图
def is_connected(graph, start_node):
    visited = set([start_node])
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    # 如果所有节点都被访问过，则返回True，表示连通；否则返回False
    return len(visited) == len(graph)

def count_components(graph):
    components = {}
    for node in graph:
        if node not in components:
            components[node] = set([node])

        # 对每个未标记过的节点进行DFS
        if node not in components[graph[node]]:
            dfs_graph(graph, node, components)
    
    # 返回连通分量的数量
    return len(components.values())

def dfs_graph(graph, current_node, components):
    stack = [current_node]
    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if neighbor not in components[current_node]:
                components[current_node].add(neighbor)
                stack.append(neighbor)

# 使用例子：
# 假设 graph 是一个字典，键是节点，值是一个包含该节点邻居的列表
graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1], 4: [2]}
if is_connected(graph, 0):  # 判断整个图是否连通
    print("图是连通的")
else:
    component_count = count_components(graph)
    print(f"图有{component_count}个连通分量")

这个代码首先检查整个图是否通过起点`start_node`连通，然后如果图不连通，会递归地找出所有的连通分量。注意，实际应用中需要考虑输入数据的有效性和错误处理。