基于回路结点收缩的有向图强连通判定算法 |
| |
引用本文: | 何忠秀.基于回路结点收缩的有向图强连通判定算法[J].教育技术导刊,2008,7(8):59-60. |
| |
作者姓名: | 何忠秀 |
| |
作者单位: | 西华大学数学与计算机学院 |
| |
摘 要: | 介绍了一种将有向图中形成回路的结点进行收缩的方法来判断有向图是否连通。在有向图的邻接矩阵中,使用深度优先搜索(DFS)算法,找到一条回路后,将该回路中的结点收缩为一点,生成新的邻接矩阵,继续进行DFS搜索,直到没有回路。如果所有结点都收缩成一点,则该有向图是强连通的。
|
关 键 词: | 回路 结点收缩 强连通 |
本文献已被 CNKI 维普 等数据库收录! |
|