上海
摘要：
1，無向圖的連通性介紹
2，并查集判斷無向圖的連通性
3，F(xiàn)loyd算法判斷無向圖的連通性
1，無向圖的連通性介紹
在無向圖中，若任意一對頂點(diǎn)(x,y)，存在從 x 到 y 的路徑，則該無向圖是連通的，如下圖所示，左邊的是連通圖，右邊的不是。
在有向圖中，圖的連通性分為強(qiáng)連通圖，單向連通圖和弱連通圖。
1，強(qiáng)連通圖：在有向圖中，若任意一對頂點(diǎn)(x,y)，都存在從 x 到 y 和 y 到 x 的路徑，也就是任意兩點(diǎn)相互可達(dá)，則該圖就是強(qiáng)連通圖。
2，單向連通圖：在有向圖中，若任意一對頂點(diǎn)(x,y)，存在從 x 到 y 或者 y 到 x 的路徑，則該圖就是單向連通圖，要注意這里的任意兩個字。
3，弱連通圖：如果有向圖的底圖（不考慮邊的方向）是連通的，則該有向圖就是若連通圖。
一般情況下討論圖的連通性主要是無向圖，而對于有向圖我們一般討論比較多的是強(qiáng)連通分量。計(jì)算有向圖的強(qiáng)連通分量可以使用kosaraju算法和Tarjan算法，其中Tarjan算法還可以計(jì)算圖的割點(diǎn)和割邊（如果存在割點(diǎn)和割邊），這些在后面我們都會介紹。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
小宇宙雙色球
