華中科技大學研究生考試軟件工程答案數據結構“名詞解釋”部分數據結構與算法分析(編輯修改稿)
2024-12-23 00:06 本頁面
【文章內容簡介】 算法 — 在頂點集合中逐漸歸并當前權值最小的邊。 9. Prim 算法 —— 在當前最小邊集合 中逐漸歸并相關的頂點。 10. 如果一個有向圖恰有一個頂點的入度為 0，其余頂點的入度均為 1，則是一棵 有向樹 。一個 有向圖的生成森林 由若干棵有向樹組成，含有圖中全部頂點，但只有足以構成若干棵不相交的有向樹的弧。 11. 圖的存儲結構 有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。 12. 圖的遍歷 ：指從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。 13. 通常有兩條遍歷圖的路徑： 1） 深度優(yōu)先搜索 ：類似于樹的先序遍歷，假設從圖中某頂點 v出發(fā)，在訪問了 v 之后依次從 v 的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和 v有路徑相通的頂點 都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點做為起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。 2） 廣度優(yōu)先搜索 ：類似于村的層序遍歷，假設從圖中某頂點 v出發(fā)，在訪問了 v 之后依次訪問它們的鄰接點，并使先被訪問的頂點的鄰接點先于后訪問的頂點的鄰接點，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。 14. 假若在刪去頂點 v以及和 v相關聯的各邊之后，將圖的一個連通分量分割成兩個或 兩個以上的邊通分量，則稱頂點 v為該圖的一個 關節(jié)點 。一個沒有關節(jié)點的圖稱為重 連通圖 。若在連通圖上至少刪去 k 個頂點才能破壞圖的連通性，則稱此圖的 連通度 為 k。 15. 對于無向圖來說，若深度優(yōu)先搜索過程中遇到回邊，則必定存在環(huán)，而對于有向圖來說，這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點的弧。 16. 拓撲排序 (Topological Sort)：指由某個集合上的一個偏序得到該集合上的一個全序。 17. AOV網 ：指用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向圖稱為頂點表示活動的網。 AOV網 (Activity On Vertices)—用頂點表示活動的網絡 。 若用有向圖表示一個工程，在圖中用頂點表示活動，用?。从邢蜻叄┍硎净顒娱g的優(yōu)先關系。 Vi 必須先于活動 Vj 進行。則這樣的有向圖叫做用頂點表示活動的網絡，簡稱 AOV。 18. AOE網 ： 在帶權有向無環(huán)網中， 用有向邊表示一個工程中的活動，用邊上權值表示活動持續(xù)時間，用頂點表示事件，則這樣的有向圖叫做用邊表示活動的網絡，簡稱 AOE。常用于大型工程的計劃管理。 19. 在正常的情況（無環(huán)）下，網中只有一個入度為零的點，稱做 源點 和一個出度為零的4 點，稱為 匯點 。 20. 關鍵路徑 ： AOE 網中有 些活動可以并行進行，所以完工的最短時間是從開始點到完成點的最長路徑的長度（即沿途各活動持續(xù)時間之和）。路徑長度最長的路徑叫做關鍵路徑 ， 關鍵路徑上的所有活動 （ l(i) = e(i)的活動 ） 都是 關鍵活動 。 21. 最早發(fā)生時間 ： 假設開始點是 V1，從 V1 到 Vi 的最長路徑長度叫做事件 Vi 的最早發(fā)生時間 [ e(i) ] 。 22. 最遲開始時間 ： 不推遲整個工程完成的前提下，活動 ai最遲必須開始進行的時間 [ l(i) ] 。 23. Dijkstra（迪杰斯特拉）算法 ： 先找出從源點 v0到各終點 vk 的直達路徑（ v0,vk），即通過一條弧到達的路 徑。從這些路徑中找出一條長度最短的路徑（ v0,u） ,然后對其余各條路徑進行適當調整：若在圖中存在?。?u,vk），且（ v0,u） +（ u,vk） （ v0,vk） ， 則以路
環(huán)評公示相關推薦
鄂ICP備17016276號-1