lecture5-圖的遍歷及強(qiáng)連通分支-文庫吧資料
2025-07-30 12:35本頁面
【正文】 and C′ be distinct strongly connected ponents in directed graph G = (V, E). Suppose that there is an edge (u, v) ∈ E, where u ∈ C and v ∈ C′. Then f (C) f(C′). 21 推論 ? 推論 ： Let C and C′ be distinct strongly connected ponents in directed graph G = (V, E). Suppose that there is an edge (u, v) ∈ ET, where u ∈ C and v ∈ C′. Then f(C) f(C′). ? 推論 ：若 f(C) f(C′)，則(u, v) 不屬于 ET。所以這一次得到的生成樹就構(gòu)成 SCC。 ? （ 2）第二次在 GT上進(jìn)行 DFS，并按 f[u]的降序，意味著從上一次的生成樹的樹根出發(fā)。 18 SCC算法有效性分析 ? （ 1）第一次在 G上進(jìn)行 DFS，得到一個(gè)生成森林，由若干棵生成樹組成。 ? 問題：圖 G中，若節(jié)點(diǎn) u可達(dá) v1,v2,…,vk ，且 v1,v2,…,vk 可達(dá) u，則 u和 v1,v2,…,vk 構(gòu)成一個(gè)強(qiáng)連通分支。 15 強(qiáng)連通分支 ? Strongly connected ponent ? 在尋找 SCC時(shí)，用到了圖 G的轉(zhuǎn)置，其定義為： GT
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1