| 用广度优先搜索求割点和块的算法研究 |
| |
| 引用本文： | 许光汉. 用广度优先搜索求割点和块的算法研究[J]. 北京航空航天大学学报, 1991, 0(2): 87-95 |
| |
| 作者姓名： | 许光汉 |
| |
| 作者单位： | 北京航空航天大学计算机科学与工程系 |
| |
| 摘 要： | 本文在作者以前研究的基础上,进一步提出子树径和独立子树径的概念,深刻分析了在广度优先搜索下简单连通无向图的结构特征,并给出判断割点和块的准则,为设计用广度优先搜索寻找割点和块的有效算法提供了理论依据。
|
| 关 键 词： | 割点 块 广度优先搜索 子树径 |
A STUDY OF THE ALGORITHM FOR FINDING CUT-VERTEX AND BLOCK USING BREADTH-FIRST SEARCH |
| |
| Xu Guanghan. A STUDY OF THE ALGORITHM FOR FINDING CUT-VERTEX AND BLOCK USING BREADTH-FIRST SEARCH[J]. Journal of Beijing University of Aeronautics and Astronautics, 1991, 0(2): 87-95 |
| |
| Authors: | Xu Guanghan |
| |
| Affiliation: | Dept. of computer Sci. and Eng. |
| |
| Abstract: | The concepts of subtree path and independent subtree path are presented. It profoundly anal- yses the structure characteristics of simple connected, undirected graph under breadth-first searching,and several criterions that judge cut-vertex and block are given. These works provide theoretical basis for designing efficient algorithm which seek cut-vertex and block using breadth-first search. |
| |
| Keywords: | cut-vertex block breadth-first search subtree path independent subtree path. |
| 本文献已被 CNKI 维普 等数据库收录！ |
