[工學(xué)]基本數(shù)據(jù)結(jié)構(gòu)-圖-wenkub
2022-10-31 18:29:54 本頁面
【正文】 5 6 2 8 5 4 6 9 4 7 ∧ 1 8 3 2 4 1 ∧ 2 2 5 2 6 2 4 3 ∧ 1 7 2 1 3 3 6 2 ∧ 1 4 6 6 3 2 ∧ 1 9 4 2 5 6 3 2 ∧ V1 V2 V3 V4 V5 V6 圖 1 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 ? 連通圖、 強(qiáng)連通 子圖 (分量 ) ? 無向圖的 生成樹 ? ...... 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 ? 頂點(diǎn) u,v間有邊， u,v互為 鄰接點(diǎn) 。 3. 理解求最小生成樹、拓?fù)渑判?、求關(guān)鍵路徑、求最短路徑等算法。 Engineering, Xidian University, China ACM/ICPC程序設(shè)計 基本數(shù)據(jù)結(jié)構(gòu) 及其在程序設(shè)計中的應(yīng)用 張淑平 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 非線性結(jié)構(gòu) ? 樹、二叉樹 ? 圖 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 ? 邊 (u,v)， 和頂點(diǎn) u和 v相關(guān)聯(lián) 。 Engineering, Xidian University, China 無向圖及其生成樹 V3 V2 V4 V1 V6 V5 V3 V2 V4 V1 V6 V5 V3 V2 V4 V1 V6 V5 無向圖 G 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 圖的算法 ? 基本算法 ? 遍歷算法 ? 求最小生成樹的算法 ? 求最短路徑的算法 ? 拓?fù)渑判蛩惴? ? 關(guān)鍵路徑求解算法 ? ...... ? 其他算法 ? 連通性問題及求解算法 ? 匹配問題及算法 ? 網(wǎng)絡(luò)流問題及算法 ? … 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 例 4：學(xué)校 網(wǎng)絡(luò) (續(xù) ) 4 3 1 As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the work. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 4 3 1 (a) (b) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 依此類推，直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問； (用隊列 ) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 there is no SPF in the work. At least two machines must fail before there are any pairs of available nodes which cannot municate. 1 3 4 5 2 1 3 4 5 2 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 例 5： SPF output The first work in the file should be identified as “Network 1”, the second as “Network 2”, etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subs that remain when that node fails. If the work has no SPF nodes, simply output the text “No SPF nodes” instead of a list of SPF nodes. Network 1 SPF node 3 leaves 2 subs Network 2 No SPF nodes Network 3 SPF node 2 leaves 2 subs SPF node 3 leaves 2 subs 1 3 4 5 2 1 3 4 5 2 1 3 4 5 2 6 關(guān)節(jié)點(diǎn)的特點(diǎn)： (1) 若深度優(yōu)先生成樹的根有兩棵或兩棵以上的子樹，則此根頂點(diǎn)必為關(guān)節(jié)點(diǎn)； (2) 若生成樹中某個非葉子結(jié)點(diǎn) v， 存在 v的某棵子樹的根及該子樹的其他結(jié)點(diǎn)均沒有指向 v的祖先的回邊，則 v是關(guān)節(jié)點(diǎn)。 Engineering, Xidian University, China ? 克魯斯卡爾算法求最小生成樹 V4 V1 V3 V2 V6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1