2023計算機考研初試在即，在最后階段建議各位同學(xué)將知識點再系統(tǒng)復(fù)習(xí)一遍，以免有所遺漏！2022計算機考研數(shù)據(jù)結(jié)構(gòu)第五單元知識點包含圖、圖的存儲結(jié)構(gòu)、圖的遍歷等內(nèi)容。高頓考研為大家整理了2022計算機考研數(shù)據(jù)結(jié)構(gòu)第五單元知識點的詳細(xì)內(nèi)容，供大家參考復(fù)習(xí)！
圖
圖是一種非線性結(jié)構(gòu)。在圖中，每個結(jié)點可以有任意個前驅(qū)、任意個后繼。
相關(guān)術(shù)語：
頂點：圖中的結(jié)點常稱為頂點。
邊：結(jié)點的偶對。
有向圖：若代表一條邊的偶對是有序的，則稱其為有向圖。用〈u,v〉表示有向邊。
無向圖：若代表一條邊的偶對是無序的，則稱其為無向圖。用(u,v)表示無向邊。
完全圖：一個圖有最多的邊數(shù)，無向完全圖有n(n-1)/2條邊，有向完全圖有n(n-1)條邊。
簡單路徑：一條路徑上的所有頂點，除起始頂點和終止頂點可以相同外，其余頂點各不相同。
回路：是一條簡單路徑，其起始頂點和終止頂點相同。
連通圖：無向圖中，若兩個頂點u和v之間存在一條從u到v的路徑，則稱u和v是連通的。若圖中任意一對頂點都是連通的。
強連通圖：有向圖中，若任意一對頂點u和v間存在一條從u到v的路徑和一條從v到u的路徑。
連通分量：無向圖的極大連通子圖。
強連通分量：有向圖的極大強連通子圖。
度：在無向圖中，與某個頂點相關(guān)聯(lián)的邊的數(shù)目。
入度：在有向圖中，以某個頂點為頭(始點)的邊的數(shù)目。
出度：在有向圖中，以某個頂點為尾(終點)的邊的數(shù)目。
有向圖的根：恰有一個頂點入度為0，其余頂點入度為1，該頂點稱為有向圖的根。
網(wǎng)：帶權(quán)值的圖。
相關(guān)運算：
Exist(u,v)：如果圖中存在邊，則函數(shù)返回true，否則返回false。
Insert(u,v,w)：向圖中添加權(quán)為w的邊，若插入成功，則函數(shù)返回Success;若圖中已存在邊，則函數(shù)返回Duplicate;其它情況函數(shù)返回Failure。
Remove(u,v)：從圖中刪除邊，若圖中不存在邊，則函數(shù)返回NotPresent;若圖中存在邊，則從圖中刪除此邊，函數(shù)返回Success;其它情況函數(shù)返回Failure。
Vertices()：函數(shù)返回圖中頂點數(shù)目。
圖的存儲結(jié)構(gòu)
(1)鄰接矩陣
a<u><u>=0：主對角線元素都是0;
a<u>[v]=w：
若?E，則w=1，或w=w(i,j)(帶權(quán)圖);
若?E，則w=noEdge，其中，noEdge=0(不帶權(quán)圖);noEdge=INF(帶權(quán)圖)。
(2)鄰接表
在鄰接表中，為圖的每個頂點u建立了一個單鏈表，鏈表中的每個結(jié)點代表一條邊，稱為邊結(jié)點。這樣，頂點u的單鏈表記錄了鄰接自u的全部頂點。每個單鏈表相當(dāng)于鄰接矩陣的一行。
圖的遍歷
(1)深度優(yōu)先遍歷
a.訪問頂點v，并對v做已訪問標(biāo)記;
b.依次從v的未訪問的鄰接點出發(fā)，對圖作深度優(yōu)先搜索。
圖中所有頂點，以及在遍歷時經(jīng)過的邊(即從已訪問的頂點到達(dá)未訪問頂點的邊)構(gòu)成的子圖，稱為圖的深度優(yōu)先搜索生成樹(或生成森林)。
(2)廣度優(yōu)先遍歷
a.訪問頂點v，并對v做已訪問標(biāo)記;
b.依次訪問v的各個未訪問過的鄰接點;
c.再依次訪問分別于這些鄰接點相鄰接且未訪問過的頂點。
圖中所有頂點以及在遍歷時經(jīng)過的邊(即從已訪問的頂點到達(dá)未訪問頂點的邊)構(gòu)成的子圖稱為圖的廣度優(yōu)先搜索生成樹(或生成森林)。
算法見書P166
拓?fù)渑判?/strong>
拓?fù)渑判颍簩⒂邢驁D中的頂點排成一個拓?fù)湫蛄械倪^程。
拓?fù)湫蛄校河邢驁D中的一個頂點序列，對圖中任意兩個頂點i和j，若i是j的前驅(qū)結(jié)點，則在線性序列中i先于j。
AOV網(wǎng)：以頂點表示活動，有向邊表示活動之間的領(lǐng)先關(guān)系的有向圖。
注意：拓?fù)湫蛄胁皇俏ㄒ坏?
可以用拓?fù)渑判虻姆椒▉頊y試有向圖是否存在回路，若經(jīng)過拓?fù)渑判蚝笏许旤c都已列出，則不存在回路。
排序步驟：
a.任選一個入度為零的頂點，并輸出之;
b.從圖中刪除該頂點及其所有出邊;
c.重復(fù)步驟1、2，直到所有頂點都已輸出，或者直到剩下的圖中再也沒有入度為零的頂點為止，后者表示圖中包含有向回路。
最小代價生成樹
無向連通圖的生成樹是一個極小連通子圖，它包括圖中全部頂點，并且有盡可能少的邊。
無向連通網(wǎng)絡(luò)的最小代價生成樹是所有生成樹中邊的權(quán)值之和最小的。
(1)普里姆算法：
首先，從n個頂點中任選一個頂點v加入到原來為空的生成樹中;然后，重復(fù)執(zhí)行下列操作：從一個頂點在生成樹中，而另一個頂點不在生成樹中的那些邊中，選取一條權(quán)值最小的邊，并將這條邊以及它所關(guān)聯(lián)的目前還不在生成樹中的那個頂點加入到生成樹中。當(dāng)生成樹中的頂點數(shù)達(dá)到n時，整個構(gòu)造過程結(jié)束。
(2)克魯斯卡爾算法
單源最短路徑
邊的權(quán)值之和最小的路徑稱為最短路徑，并稱v(x)為這條最短路徑的源點，v(i)為終點。
迪杰斯特拉算法：
按最短路徑長度值由小到大的次序，逐步求得每一條最短路徑。
關(guān)鍵路徑
關(guān)鍵路徑：在無回路的有向網(wǎng)絡(luò)中，假設(shè)只有一個入度為0的頂點(稱為源點)和一個出度為0的頂點(稱為匯點)，則從源點到匯點之間的最長的路徑稱為關(guān)鍵路徑。
AOE網(wǎng)：以頂點代表事件，有向邊表示活動，有向邊上的權(quán)表示一向活動所需的時間。注意AOV網(wǎng)和AOE網(wǎng)的區(qū)別
關(guān)鍵活動：對整個工程的最短完成時間有影響的活動。
求關(guān)鍵路徑的算法：(見書P174)
a.計算每個事件可能的最早發(fā)生時間
b.計算每個事件允許的最遲發(fā)生時間
c.輸出關(guān)鍵活動