數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)總結(jié)-資料下載頁(yè)
2025-04-17 01:46本頁(yè)面
【正文】 方向相反的兩條邊，即有n(n1)條邊，稱(chēng)完全有向圖。權(quán)：與圖的邊或弧相關(guān)的數(shù)，這些數(shù)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)網(wǎng)：帶權(quán)的圖度：在無(wú)向圖中是頂點(diǎn)邊的數(shù)目；在有向圖中，頂點(diǎn)的度=入度+出度入度： 有向圖中頂點(diǎn)入邊的數(shù)目出度：有向圖中頂點(diǎn)出邊的數(shù)目路徑：從頂點(diǎn)V 到頂點(diǎn)V挼囊187。個(gè)頂點(diǎn)系列回路：一條路徑上的前后兩個(gè)端點(diǎn)相同鄰接點(diǎn)：無(wú)向圖中一條邊(Vi,Vj)的兩個(gè)端點(diǎn)Vi,Vj路徑長(zhǎng)度：路徑上經(jīng)過(guò)的邊的數(shù)目簡(jiǎn)單路徑：一條路徑上除了前后端點(diǎn)可以相同外，所有頂點(diǎn)均不相同簡(jiǎn)單回路：前后兩端點(diǎn)相同的簡(jiǎn)單路徑連通圖： 無(wú)向圖中任意兩個(gè)頂點(diǎn)都連通。如果一個(gè)圖有n 個(gè)頂點(diǎn)和小于n1 條邊，則是非連通圖。連通分量：無(wú)向圖的極大連通子圖；任何連通圖的連通分量只有一個(gè)，即其本身；非連通圖有多個(gè)連通分量。強(qiáng)連通圖： 有向圖中任意兩個(gè)頂點(diǎn)都連通強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖；任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其本身；非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。生成樹(shù)： 在一個(gè)連通圖G 中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G?,V(G?)=V(G) E(G?)∈E(G), 若邊集E（G?）中的邊將圖中所有的頂點(diǎn)連通又不形成回路，則稱(chēng)子圖G?是圖G 的一棵生成樹(shù)。一棵有n 個(gè)頂點(diǎn)的生成樹(shù)有且僅有n1條邊，但有n1 條邊的圖不一定是生成樹(shù)。如果它多于n1 條邊，則一定有環(huán)。最小生成樹(shù)：具有權(quán)最小的生成樹(shù)有向樹(shù)：一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1。鄰接矩陣（Adjacency Matrix）的存儲(chǔ)結(jié)構(gòu)，就是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系。鄰接表(Adjacency List)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類(lèi)似于樹(shù)的孩子鏈表表示法。就是對(duì)于圖G 中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi 的頂點(diǎn)vj 鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi 的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。圖的遍歷：從圖中某個(gè)頂點(diǎn)出發(fā)訪(fǎng)遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次過(guò)程。深度優(yōu)先搜索：從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)，然后依次從V0 的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0 有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到，若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。廣度優(yōu)先搜索：從圖中的某個(gè)頂點(diǎn)V0 出發(fā)，并在訪(fǎng)問(wèn)此頂點(diǎn)之后依次訪(fǎng)問(wèn)V0 的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪(fǎng)問(wèn)的先后次序依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0 有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn),則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。最小生成樹(shù)算法：（1）Prim 算法：Prim 算法構(gòu)造最小生成樹(shù)的過(guò)程為：在所有撈湟桓齠サ227。已經(jīng)落在生成樹(shù)上，而另一個(gè)頂點(diǎn)尚未落在生成樹(shù)上?的邊中取一條權(quán)值為最小的邊，逐條加在生成樹(shù)上，直至生成樹(shù)中含有n1 條邊為止。（2）Kruskal 算法：Kruskal 算法構(gòu)造最小生成樹(shù)的過(guò)程為：先構(gòu)造一個(gè)只含n 個(gè)頂點(diǎn)、而邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹(shù)上的根結(jié)點(diǎn)，之后，從網(wǎng)的邊集E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù)，則將其加入子圖，即把兩棵樹(shù)合成一棵樹(shù)，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類(lèi)推，直到森林中只有一棵樹(shù)，也即子圖中含有n1 條邊為止。有向無(wú)環(huán)圖（directed acycling graph）：一個(gè)無(wú)環(huán)的有向圖簡(jiǎn)稱(chēng)DAG 圖。有向無(wú)環(huán)圖是描述一項(xiàng)工程進(jìn)行過(guò)程的有效工具。主要進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。拓?fù)渑判驅(qū)嶋H上是對(duì)鄰接表表示的圖進(jìn)行遍歷的過(guò)程。AOV 網(wǎng)（Activity On Vertex Network）：頂點(diǎn)表示活動(dòng)的網(wǎng)，即用頂點(diǎn)表活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖。AOE 網(wǎng)（Activity On Edge Network）：是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間，可以用來(lái)估算工程的完成時(shí)間。關(guān)鍵路徑：AOE 網(wǎng)中帶權(quán)路徑最長(zhǎng)的路徑。AOV 網(wǎng)的拓?fù)渑判颍涸陧旤c(diǎn)活動(dòng)網(wǎng)AOV 網(wǎng)中，若不存在回路，則所有活動(dòng)可排列成一個(gè)線(xiàn)性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，該序列叫拓?fù)湫蛄?，由AOV 網(wǎng)構(gòu)造拓?fù)湫蛄械倪^(guò)程叫做拓?fù)渑判?。AOV 網(wǎng)拓?fù)湫蛄胁皇俏ㄒ坏?。拓?fù)渑判虻乃惴ǎ哼x一個(gè)入度為0 的頂點(diǎn)輸出，并將其所有后繼頂點(diǎn)的入度?1，重復(fù)這兩步直至輸出所有頂點(diǎn)，或找不到入度為0 的頂點(diǎn)為止，為便于查找入度為0 的頂點(diǎn)，算法中利用頂點(diǎn)的入度域建立一個(gè)存放入度為0 的頂點(diǎn)的棧。__
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1