割顶点(或关节点)是指在无向连通图中,删除该顶点及其相关边后,会使得原图变为非连通图的顶点。下面是一个使用深度优先搜索(DFS)算法来找出割顶点的代码示例:
def articulation_points(graph):
num_nodes = len(graph)
visited = [False] * num_nodes
parent = [-1] * num_nodes
low = [float('inf')] * num_nodes
discovery = [float('inf')] * num_nodes
is_articulation = [False] * num_nodes
time = 0
def dfs(node, visited, parent, low, discovery, is_articulation):
nonlocal time
children = 0
visited[node] = True
discovery[node] = time
low[node] = time
time += 1
for neighbor in graph[node]:
if not visited[neighbor]:
parent[neighbor] = node
children += 1
dfs(neighbor, visited, parent, low, discovery, is_articulation)
low[node] = min(low[node], low[neighbor])
if parent[node] == -1 and children > 1:
is_articulation[node] = True
if parent[node] != -1 and low[neighbor] >= discovery[node]:
is_articulation[node] = True
elif neighbor != parent[node]:
low[node] = min(low[node], discovery[neighbor])
for node in range(num_nodes):
if not visited[node]:
dfs(node, visited, parent, low, discovery, is_articulation)
result = []
for node in range(num_nodes):
if is_articulation[node]:
result.append(node)
return result
该代码首先使用DFS遍历图中的每个连通分量,对于每个顶点,记录其发现时间(discovery)、最早可达祖先的发现时间(low)、访问状态(visited)、父节点(parent)和是否为割顶点(is_articulation)。在DFS遍历中,如果发现一个顶点是割顶点,则将is_articulation[node]置为True。最后,返回所有割顶点的列表。
使用示例:
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3, 5],
3: [2, 4],
4: [3],
5: [2, 6, 8],
6: [5, 7],
7: [6, 8],
8: [5, 7]
}
result = articulation_points(graph)
print(result) # 输出:[2, 5]
在上述示例中,图中的割顶点为2和5。