習(xí)題五參考答案

1、1.設(shè)一有向圖設(shè)一有向圖G=(VE)，其中，其中V=abcde，E=①請畫出該有向圖，并求各頂點(diǎn)的入度和出度。請畫出該有向圖，并求各頂點(diǎn)的入度和出度。②分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。③寫出相應(yīng)的鄰接矩陣表示。寫出相應(yīng)的鄰接矩陣表示。④寫出從頂點(diǎn)寫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。⑤畫出從頂點(diǎn)畫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先生成樹。開始的深度

2、優(yōu)先和廣度優(yōu)先生成樹。A:入度入度2出度出度2B:入度入度3出度出度1C：入度：入度1出度出度2D:入度入度2出度出度1E:入度入度1出度出度3總計總計入度入度9；出度；出度9abcdea01010b10000c01010d00001e11100從a點(diǎn)開始深度優(yōu)先序列點(diǎn)開始深度優(yōu)先序列abdec廣度優(yōu)先遍歷序列廣度優(yōu)先遍歷序列:abdec3.一個一個AOV網(wǎng)用鄰接矩陣表示，如圖網(wǎng)用鄰接矩陣表示，如圖731。用拓?fù)渑判蚯笤摗Ｓ猛負(fù)渑判蚯笤?/p>

3、AOV網(wǎng)的一個拓?fù)湫蛄校o網(wǎng)的一個拓?fù)湫蛄?，給出相應(yīng)的步驟。出相應(yīng)的步驟。(提示提示:先根據(jù)鄰接矩陣畫出有向圖先根據(jù)鄰接矩陣畫出有向圖然后寫出可能的一個拓?fù)湫蛄腥缓髮懗隹赡艿囊粋€拓?fù)湫蛄?相關(guān)知識相關(guān)知識:AOV網(wǎng):圖中頂點(diǎn)表示活動，有向邊表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為圖中頂點(diǎn)表示活動，有向邊表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動的網(wǎng)頂點(diǎn)表示活動的網(wǎng)(ActivityOnVertexwk，AOV網(wǎng))。?有向圖的拓