為幫助考生備考軟考軟件設(shè)計師考試，希賽小編為大家整理了2022下半年軟件設(shè)計師知識點：圖，相信對大家備考會有幫助。

圖（★★）

【考法分析】

1、本知識點的主要考查形式有：判斷給出的關(guān)于圖的概念、特性的描述是否正確；或根據(jù)圖的鄰接矩陣、鄰接表，指出相關(guān)圖、圖的特點、圖的遍歷；根據(jù)圖示，指出遍歷順序、拓撲序列。

【要點分析】

1、完全圖

在無向圖中，若每對頂點之間都有一條邊相連，則稱該圖為完全圖（complete graph）。

在有向圖中，若每對頂點之間都有二條有向邊相互連接，則稱該圖為完全圖。

2、圖的鄰接矩陣表示：用一個n階方陣R來存放圖中各結(jié)點的關(guān)聯(lián)信息，其矩陣元素Rij定義為：

3、圖的鄰接表表示：首先把每個頂點的鄰接頂點用鏈表示出來，然后用一個一維數(shù)組來順序存儲上面每個鏈表的頭指針。

4、圖的遍歷：

5、圖的拓撲排序：拓撲排序是將AOV網(wǎng)中的所有頂點排成一個線性序列的過程，并且該序列滿足：若在AOV網(wǎng)點中從頂點Vi到Vj有一條路徑，則在該線性序列中，頂點Vi必然在頂點Vj之前。

6、最小生成樹，是該圖的極小聯(lián)通子圖。普里姆算法構(gòu)造最小生成樹過程：

（1）去掉所有的連線，將所有頂點放到集合R1中，作為未處理結(jié)點集合，另新建集合R2存放已處理結(jié)點。

（2）選擇入度為0的頂點作為起點，放到集合R2中；

（3）選擇R2到R1最短（代價最?。┑穆窂?，同時將對應(yīng)頂點從R1刪除并放到集合R2中。

（4）重復(fù)步驟3直到R1為空。

【備考點撥】

1、掌握圖的相關(guān)概念；

2、掌握圖的存儲；

3、掌握圖的遍歷；

4、掌握圖的拓撲序列求取；

5、了解最小生成樹的構(gòu)造。