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