图里的强连通成分是什么意思?求直白的解释
1个回答
对于有向图$G$,如果存在一个子图$\hat G$,对于$\hat G$中的任何顶点$v_1, v_2$,总存在一条路径从$v_1$到$v_2$,同时也存在一条路径从$v_2$到$v_1$,那么我们就说$\hat G$是$G$的强连通子图或者强连通分量。
上面就是一个有向图。$\{a, b, e\}$是强连通的,$\{c,d,h\}$是一个强连通分量,$\{f,g\}$是一个强连通分量。
SofaSofa数据科学社区DS面试题库 DS面经图里的强连通成分是什么意思?求直白的解释
对于有向图$G$,如果存在一个子图$\hat G$,对于$\hat G$中的任何顶点$v_1, v_2$,总存在一条路径从$v_1$到$v_2$,同时也存在一条路径从$v_2$到$v_1$,那么我们就说$\hat G$是$G$的强连通子图或者强连通分量。
上面就是一个有向图。$\{a, b, e\}$是强连通的,$\{c,d,h\}$是一个强连通分量,$\{f,g\}$是一个强连通分量。
SofaSofa数据科学社区DS面试题库 DS面经