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

圖（★★）

【考法分析】

1、本知識(shí)點(diǎn)的主要考查形式有：判斷給出的關(guān)于圖的概念、特性的描述是否正確；或根據(jù)圖的鄰接矩陣、鄰接表，指出相關(guān)圖、圖的特點(diǎn)、圖的遍歷；根據(jù)圖示，指出遍歷順序、拓?fù)湫蛄小?/p>

【要點(diǎn)分析】

1、完全圖

在無(wú)向圖中，若每對(duì)頂點(diǎn)之間都有一條邊相連，則稱該圖為完全圖（complete graph）。

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

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

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

4、圖的遍歷：

5、圖的拓?fù)渑判颍和負(fù)渑判蚴菍OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列的過(guò)程，并且該序列滿足：若在AOV網(wǎng)點(diǎn)中從頂點(diǎn)Vi到Vj有一條路徑，則在該線性序列中，頂點(diǎn)Vi必然在頂點(diǎn)Vj之前。

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

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

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

（3）選擇R2到R1最短（代價(jià)最?。┑穆窂剑瑫r(shí)將對(duì)應(yīng)頂點(diǎn)從R1刪除并放到集合R2中。

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

【備考點(diǎn)撥】

1、掌握?qǐng)D的相關(guān)概念；

2、掌握?qǐng)D的存儲(chǔ)；

3、掌握?qǐng)D的遍歷；

4、掌握?qǐng)D的拓?fù)湫蛄星笕。?/p>

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