数据结构关节点指的是什么

Question

如题所述

Answer 1

数据结构关节点指的是在数据结构的某图中，如果删除顶点V以及V相关的边后，图的一个连通分量分割为两个或两个以上的连通分量的顶点V。

关节点是指在数据结构的某图中，如果删除顶点V以及V相关的边后，图的一个连通分量分割为两个或两个以上的连通分量，则称顶点V为该图的一个关节点。一个没有关节点的连通图称为重连通图。利用深度优先搜索便可以求的图的关节点，由此可判别图是否重连通。

特性：

（1）若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在连接不同子树顶点的边，若删除此节点，则树便成为森林。

（2）若生成树中某个非叶子节点V，其某棵子树与V的祖先节点无连接，则V为关节点。因为删去v，则其子树和图的其它部分被分割开来。