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