lecture5-圖的遍歷及強連通分支-在線瀏覽
2024-09-03 12:35本頁面
【正文】 u]存放節(jié)點 u的顏色信息。 ? ∏[u]存放節(jié)點 u的父節(jié)點。 4 廣度優(yōu)先搜索 ? Breadthfirst search 5 廣度優(yōu)先樹 ? 根據(jù) BFS算法中保存的信息可以構(gòu)造出一棵BFS生成樹。 ? （ 1）開始時，每個頂點都為白色；（ 2）搜索中被發(fā)現(xiàn)時即置為灰色；（ 3）結(jié)束時又被置為黑色（即當其鄰接表被完全檢索之后）。每個頂點 v有兩個時間戳：當頂點 v第一次被發(fā)現(xiàn)時（置為灰色），記錄下第一個時間戳 d[v]，當結(jié)束檢索 v的鄰接表（置為黑色）時，記錄下第二個時間戳 f[v]。對每一個頂點 u，有： ? d[u]f[u] 7 深度優(yōu)先搜索 ? Depthfirst search 8 深度優(yōu)先搜索 ? Depthfirst search 9 DFS的性質(zhì) ? 括號定理 10 深度優(yōu)先搜索 ? Depthfirst search 11 DFS— 邊的分類 ? 在圖 G上進行 DFS所產(chǎn)生的深度優(yōu)先森林，可以把圖的邊分為四種類型： ? （ 1） Tree edge，是 DFS森林中的邊。 ? （ 2） Back edge，在 DFS樹中，連接頂點 u到它的某一個祖先頂點 v的那些邊。 ? （ 3） Forward edge，是指 DFS樹中，連接頂點 u到它某個后裔 v的非樹邊 (u, v)。交叉邊也可在不同的 DFS樹的頂點之間。算法的核心思想在于對于每條邊 (u, v)，當該邊被第一次搜尋到時，即根據(jù)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1