判断一个无向图是否是连通图,若不是连通的,输出图中连通分量的个数 要求:档中包含伪代码、可编辑可执行的实际高级语言代码
时间: 2024-09-30 14:05:38 浏览: 30
判断一个无向图是否为连通图的方法
判断一个无向图是否是连通图,通常可以采用深度优先搜索(DFS)或者广度优先搜索(BFS)算法。这里给出一个基于Python的简单示例,使用BFS法:
```python
# 使用邻接列表表示无向图
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`连通,然后如果图不连通,会递归地找出所有的连通分量。注意,实际应用中需要考虑输入数据的有效性和错误处理。
阅读全文