1、第七章圖表，圖是多對(duì)多結(jié)構(gòu)關(guān)系，每個(gè)要素可以有零個(gè)或更多的直接趨勢(shì)。零個(gè)或多個(gè)直接后繼。1，PPT學(xué)習(xí)通信，確定重點(diǎn):圖的兩種遍歷方法：定義遍歷，深度優(yōu)先搜索遍歷，廣度優(yōu)先搜索遍歷算法；圖的遍歷算法決定了圖的連通性和圖的生成樹(shù)。用Prim、Kruskal算法求圖的最小生成樹(shù)；用Dijkstra算法求解單源最短路徑問(wèn)題。使用Floyd算法查找所有頂點(diǎn)之間的最短路徑問(wèn)題。使用AOV網(wǎng)絡(luò)排序拓?fù)涫褂肁OE網(wǎng)絡(luò)查找關(guān)鍵路徑問(wèn)題手掌夾點(diǎn):掌握?qǐng)D形的定義和術(shù)語(yǔ)。圖表中的各種存儲(chǔ)結(jié)構(gòu)及其配置算法，以及解決實(shí)際問(wèn)題的效率。2，PPT學(xué)習(xí)通信，7.3地物中的橫向，7.3地物中的橫向：從地物中的一個(gè)頂點(diǎn)開(kāi)始訪問(wèn)地

2、物中的所有頂點(diǎn)，每個(gè)頂點(diǎn)僅訪問(wèn)一次。圖形結(jié)構(gòu)的遍歷復(fù)雜性：(1)圖形結(jié)構(gòu)沒(méi)有“自然”的第一個(gè)節(jié)點(diǎn)，圖形的任何頂點(diǎn)都可以是第一個(gè)訪問(wèn)的節(jié)點(diǎn)(2)。由于非連接圖形只能訪問(wèn)從一個(gè)頂點(diǎn)開(kāi)始的連接組件中的所有頂點(diǎn)，因此，還必須考慮選擇下一個(gè)起點(diǎn)以訪問(wèn)圖形的其馀連接組件(3)。如果存在循環(huán)，然后訪問(wèn)頂點(diǎn)，則可以沿循環(huán)返回到該頂點(diǎn)。防止重復(fù)訪問(wèn)的方法(4)圖結(jié)構(gòu)中一個(gè)頂點(diǎn)與多個(gè)其他頂點(diǎn)相鄰的方法，考慮訪問(wèn)這些頂點(diǎn)后如何選擇下一個(gè)要訪問(wèn)的頂點(diǎn)的問(wèn)題，3，PPT學(xué)習(xí)交流，圖的遍歷方法有深度優(yōu)先遍歷和寬度優(yōu)先遍歷。7.3.1深度優(yōu)先搜索(1)從圖中的頂點(diǎn)之一V0開(kāi)始訪問(wèn)此頂點(diǎn)；(2)從V0未訪問(wèn)的相鄰點(diǎn)開(kāi)始，深度

3、首先通過(guò)圖表，直到訪問(wèn)了圖形中與V0關(guān)聯(lián)的所有頂點(diǎn)。如果地物中仍有無(wú)法訪問(wèn)的頂點(diǎn)，請(qǐng)選擇其他地物無(wú)法訪問(wèn)的頂點(diǎn)作為起點(diǎn)，然后重復(fù)此過(guò)程，直到地物中的所有頂點(diǎn)都被訪問(wèn)。4，PPT學(xué)習(xí)交流，如果圖形的存儲(chǔ)結(jié)構(gòu)是相鄰表，則訪問(wèn)相鄰點(diǎn)的順序不是唯一的，深度優(yōu)先級(jí)也不是唯一的，將，V0，V1，V3，V4，V7，V2，V5，V6，圖形G從v 0開(kāi)始的深度優(yōu)先級(jí)序列(將存儲(chǔ)結(jié)構(gòu)設(shè)置為相鄰矩陣)visit(v)；/* v訪問(wèn)第二個(gè)頂點(diǎn)*/for (w=FirstAdjVex(G，v)；w；W=NextAdjVex(G，v，w)if(！Visitedw) DFS(G，w)；/* v尚未訪問(wèn)的相鄰頂點(diǎn)w遞歸調(diào)用DFS*/，輔助陣列：int visitedMax _ Vertex _ Num訪問(wèn)標(biāo)志數(shù)組，全局變量，最初所有組件為0，visitedv=1表示頂點(diǎn)v已訪問(wèn)。visited，深度優(yōu)先遍歷算法：7.3通過(guò)圖，6，PPT學(xué)習(xí)交換，通過(guò)7.3圖，在相鄰表存儲(chǔ)結(jié)構(gòu)中深度優(yōu)先搜索：v