判断一个无向图是否是连通图,若不是连通的,输出图中连通分量的个数 要求:包含伪代码、可编辑可执行的实际高级语言代码
时间: 2024-09-30 17:05:45 浏览: 31
判断无向图是否连通以及计算连通分量的个数通常通过深度优先搜索 (Depth First Search, DFS) 或广度优先搜索 (Breadth First Search, BFS) 来实现。这里提供一个基于DFS的简单算法:
伪代码:
```
function isConnected(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
for neighbor in graph[vertex]:
stack.append(neighbor)
return len(visited) == len(set(graph.keys()))
function countConnectedComponents(graph):
components_count = 0
for vertex in graph:
if vertex not in visited: // 假设我们已经有一个 visited 集合来跟踪已访问过的节点
if isConnected(graph, vertex):
components_count += 1
return components_count
```
实际的 Python 代码示例(使用邻接列表表示图):
```python
def dfs(graph, current, visited=None):
if visited is None:
visited = set()
visited.add(current)
for neighbor in graph[current]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
def connected_components(graph):
components = []
for vertex in graph:
if vertex not in visited_set: # 初始化 visited_set
component = dfs(graph, vertex)
components.append(component)
return len(components)
# 使用示例:
graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []} # 这是一个简单的无向图表示
components_count = connected_components(graph)
if components_count > 1:
print(f"图不连通,有 {components_count} 个连通分量")
else:
print("图是连通的")
```
阅读全文