如何判断有向图的连通性? |
| |
作者姓名: | 罗光宣 任琼英 |
| |
摘 要: | (一)问题 2000年第24期擂台赛的问题是有向图的连通性判断。 对一个有向图,忽略所有有向边的方向性而得到对应的一个无向图,如果该无向图是连通的,即其中任意两点有通路相连,则称原有向图是弱连通的:如果在原有向图中任意两点间至少有一点至另一点的通路,则称该图是单向连通的:而如果原图任两点之间一定既有甲至乙,也有乙至甲的通路,即有双向通路,则称该图是强连通的。 例如,图1是一个非弱连通非单向连通与非强连通图:图
|
关 键 词: | 有向图 连通性 程序设计 |
本文献已被 CNKI 维普 等数据库收录! |
|