【数据结构和算法笔记】：找非强连通图的所有连通分量
·
●连通分量：图的极大连通子图
●强连通图：有向图中任意两个顶点都存在路径
●强连通图的连通分量是其本身
●非强连通图的连通分量不止一个
下面求一个非强连通图的所有连通分量
方法：
（1）随便找一个有向环
（2）拓展该有向环：如果某个顶点到环中的任一顶点有路径，并且该环中的任一顶点到这个顶点也有路径，则加入这个顶点
（3）最后剩下的部分就是图的连通分量
理解：
①如果在环中存在某个顶点，到待拓展顶点有路径，根据环的定义：环中任意两点都存在路径 可知，环中的所有顶点到待拓展顶点都有路径
②如果待拓展顶点到环中的某个顶点有路径，同理，根据环的定义，待拓展顶点到环中所有顶点都有路径
根据①②，可知环中所有顶点到待拓展顶点都有路径，且待拓展顶点到环中所有顶点都有路径，
根据环的定义，拓展顶点加入环中后，所得的图仍是一个环
更多推荐
1
0- 0
已为社区贡献2条内容
所有评论(0)