1、實(shí)驗(yàn)5、圖及其應(yīng)用 6課時(shí)實(shí)驗(yàn)5、圖及其應(yīng)用圖的邏輯結(jié)構(gòu)圖的存儲結(jié)構(gòu)實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)步驟代碼分析選做實(shí)驗(yàn)圖的邏輯結(jié)構(gòu)圖中任意兩個(gè)數(shù)據(jù)元素間都可能有聯(lián)系，這樣的邏輯結(jié)構(gòu)反應(yīng)了多對多的聯(lián)系。一些基本概念要掌握：網(wǎng)絡(luò)、帶權(quán)圖連通圖、強(qiáng)連通圖路徑、簡單路徑、回路生成樹、最小生成樹圖的存儲結(jié)構(gòu)圖是多對多的聯(lián)系，每個(gè)結(jié)點(diǎn)都有未知數(shù)量的直接前趨和直接后繼結(jié)點(diǎn)?？梢杂枚S數(shù)組來表示一個(gè)圖，再將二維數(shù)組存儲成一個(gè)一維數(shù)組的形式。圖的鄰接矩陣就是這樣的表示方法。圖的存儲結(jié)構(gòu)圖的鏈?zhǔn)酱鎯?，有鄰接表、鄰接多重表、十字鏈表等。?shù)據(jù)結(jié)構(gòu)教材中著重于鄰接表的鏈?zhǔn)酱鎯Ρ硎拘问健τ谟邢驁D而言，還分成鄰接表和逆鄰接表兩種?；局R

2、圖的鄰接表結(jié)構(gòu)體類型表示形式：表結(jié)點(diǎn)typedef struct ArcNodeVexIndex adjvex;/指向該弧頂點(diǎn)的位置struct ArcNode * next;/next arcArcInfoType value;/infomation about this arcArcNode;基本知識圖的鄰接表結(jié)構(gòu)體類型表示形式：表頭結(jié)點(diǎn)：typedef struct VNodeVertexInfoType value;ArcNode * firstarc;VNode;基本知識圖的鄰接表表示方法中，把所有結(jié)點(diǎn)分別存在表頭結(jié)點(diǎn)數(shù)組中。每個(gè)結(jié)點(diǎn)的鄰接點(diǎn)，再存儲在以這個(gè)頭結(jié)點(diǎn)為首結(jié)點(diǎn)的鏈表中。有

3、向圖的逆鄰接表存儲的方式也是類似的。上面的兩個(gè)結(jié)構(gòu)體類型，就反映出了這個(gè)特點(diǎn)。最后，可以通過表頭結(jié)點(diǎn)的數(shù)組來訪問圖中的所有的結(jié)點(diǎn)。VNode verticesMAX_VERTEX_NUM+1; 實(shí)驗(yàn)內(nèi)容掌握鄰接表存儲方式以及鄰接矩陣存儲方式。 在鄰接表的基礎(chǔ)上實(shí)現(xiàn)圖的深度優(yōu)先遍歷與廣度優(yōu)先遍歷操作。編寫最短路徑算法，并對輸入的圖進(jìn)行驗(yàn)證。實(shí)驗(yàn)步驟創(chuàng)建圖數(shù)據(jù)結(jié)構(gòu)所對應(yīng)的類。 分別實(shí)現(xiàn)圖的如下操作：CreateGraph ( ) DestoryGraph ( )LocateVertex ( value )GetVertex ( v )FirstAdjVertex ( v ) NextAdjVertex ( v,w) InsertVertex ( u ) DeleteVertex( v)InsertArc(v,w,value)DeleteArc(v,w) DFSTraverse()BFSTraverse()進(jìn)度安排第一周：了解實(shí)驗(yàn)內(nèi)容，圖結(jié)構(gòu)的定義，將文件的內(nèi)容讀取并存放到結(jié)構(gòu)中。第二周：圖的基本操作的實(shí)現(xiàn)第三周：最短路徑算法的實(shí)現(xiàn)第四周：完成實(shí)驗(yàn)實(shí)驗(yàn)代碼以下是一個(gè)實(shí)例：7 10北京西安鄭州徐州成都廣州上海北京 西安 2553北京 鄭州 695北京 徐州 704徐州 上海 651鄭州 徐州 34