【文章內(nèi)容簡介】 二、鄰接表 鄰接表存儲的基本思想：對于圖的每個頂點 vi， 將所有鄰接于 vi的頂點鏈成一個單鏈表，稱為頂點 vi的 邊表 （對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維 數(shù)組構(gòu)成了 頂點表 。 圖的存儲結(jié)構(gòu)及實現(xiàn) 圖的鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度？ 如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？ 假設(shè)圖 G有 n個頂點 e條邊，則存儲該圖需要 O(n2) 。 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點 。 data firstarc adjvex nextarc 頭 (頂點 )結(jié)點 表 (邊 )結(jié)點 vertex： 數(shù)據(jù)域 ， 存放頂點信息 。 firstedge： 指針域 ， 指向邊表中第一個結(jié)點 。 adjvex： 鄰接點域 ， 邊的終點在頂點表中的下標 。 next： 指針域 ， 指向邊表中的下一個結(jié)點 。 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 Typedef struct ArcNode { int adjvex。 ArcNode *nextarc。 } ArcNode。 Typedef struct VNode { Vertextype data。 ArcNode *firstarc。 }VNode， AdjList[N]； //N為圖的最大頂點數(shù) 定義鄰接表的結(jié)點 圖的存儲結(jié)構(gòu)及實現(xiàn) data firstarc adjvex nextarc 表（邊）結(jié)點 頭（頂點）結(jié)點 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 typedef struct { AdjList vertices。 int vexnum, arum。 int kind。 // 圖的種類標志 } ALGraph。 圖的結(jié)構(gòu)定義 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 Data firstarc 圖的存儲結(jié)構(gòu)及實現(xiàn) V1 V3 V4 V2 無向圖的鄰接表 表（邊）結(jié)點表示什么？ 每個表（邊）結(jié)點對應(yīng)圖中的一條邊，鄰接表的空間復(fù)雜度為 O(n+e)。 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 Data firstarc 圖的存儲結(jié)構(gòu)及實現(xiàn) V1 V3 V4 V2 無向圖的鄰接表 如何求頂點 i 的度？ 頂點 i的邊鏈表中結(jié)點的個數(shù)。 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 如何判斷頂點 i 和頂點 j 之間是否存在邊 ? 測試頂點 i 的邊鏈表中是否存在終點為 j 的結(jié)點。 圖的存儲結(jié)構(gòu)及實現(xiàn) 1 0 3 ∧ 2 3 ∧ 1 ∧ 0 1 ∧ V1 V2 V3 V4 0 1 2 3 Data firstarc V1 V3 V4 V2 無向圖的鄰接表 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 圖的存儲結(jié)構(gòu)及實現(xiàn) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 3 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 data firstarc ∧ 如何求頂點 i 的出度？ 頂點 i 的出邊鏈表中結(jié)點的個數(shù) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 圖的存儲結(jié)構(gòu)及實現(xiàn) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 3 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 data firstarc ∧ 如何求頂點 i 的入度？ 各頂點的出邊鏈表中以頂點 i 為終點的結(jié)點個數(shù)。 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 圖的存儲結(jié)構(gòu)及實現(xiàn) 有向圖的逆向鄰接表 V1 V2 V3 V4 如何求頂點 i 的入度？ 頂點 i的入邊鏈表中的結(jié)點個數(shù) 3 0 ∧ 0 ∧ 2 ∧ V1 V2 V3 V4 0 1 2 3 data firstarc ∧ 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 圖的存儲結(jié)構(gòu)及實現(xiàn) 有向圖的鄰接表 V1 V2 V3 V4 1 2 ∧ 3 ∧ 0 ∧ V1 V2 V3 V4 0 1 2 3 Data firstarc ∧ 如何求頂點 i 的所有鄰接點？ 遍歷頂點 i 的邊鏈表，該邊鏈表中的所有終點都是頂點 i 的鄰接點。 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 圖的存儲結(jié)構(gòu)及實現(xiàn) 網(wǎng)圖的鄰接表 V1 V2 V3 V4 2 7 8 5 2 1 V1 V2 V3 V4 0 1 2 3 Data firstarc ∧ 5 2 ∧ 8 3 ∧ 7 0 ∧ 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 鄰接表中圖的基本操作 ——構(gòu)造函數(shù) 1. 確定圖的頂點個數(shù)和邊的個數(shù)； 2. 輸入頂點信息 ， 初始化該頂點的邊表； 3. 依次輸入邊的信息并存儲在邊表中； 輸入邊所依附的兩個頂點的序號 i和 j； 生成鄰接點序號為 j的邊表結(jié)點 s； 將結(jié)點 s插入到第 i個邊表的頭部； 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 優(yōu)點： 在邊稀疏的情況下，用鄰接表比鄰接矩陣節(jié)省存儲空間，當和邊相關(guān)的信息較多時更是如此。 缺點： 在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點之間是否有邊或弧相連則需搜索兩個鏈表，不及鄰接矩陣方便。 N個頂點， e條邊的無向圖，鄰接表需要 n個頭結(jié)點 和 2e個表結(jié)點。 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 三、十字鏈表 有向圖的另一種鏈式存儲結(jié)構(gòu) 鄰接表 圖的存儲結(jié)構(gòu)及實現(xiàn) 逆鄰接表 將鄰接表與逆鄰接表合二為一 ?為什么要合并？ V1 V2 V3 V4 1 2 ∧ 3 ∧ 0 v1 v2 v3 v4 ∧ 0 1 2 3 1 ∧ 3 ∧ 0 ∧ 2 ∧ v1 v2 v3 v4 0 1 2 3 0 3 ∧ 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 十字鏈表的結(jié)點結(jié)構(gòu) data firstin firstout 頂點結(jié)點 tailvex： 弧尾頂點在圖中的位置 ， 即在頂點表中的下標； headvex： 弧頭頂點在圖中的位置 ， 即在頂點表中的下標； headlink： 指向弧頭相同的下一條弧的指針； taillink： 指向弧尾相同的下一條弧的指針； Info :指向該弧的相關(guān)信息 。 圖的存儲結(jié)構(gòu)及實現(xiàn) data： 數(shù)據(jù)域，存放頂點信息； firstin： 指向該頂點的第一條入弧的指針； firstout： 指向該頂點的第一條出弧的指針 ； tailvex headvex headlink taillink 弧結(jié)點 info 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 3 0 3 1 ∧ V1 V2 V3 V4 2 3 ∧ 0 1 0 2 ∧ 圖的存儲結(jié)構(gòu)及實現(xiàn) 十字鏈表存儲有向圖 ∧ ∧ V1 V2 V3 V4 ∧ ∧ ∧ v3v4 v4v1 v1v2 v1v3 v4v2 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 typedef struct ArcBox { // 弧 的結(jié)構(gòu)表示 int tailvex, headvex。 InfoType *info。 struct ArcBox *hlink, *tlink。 } ArcBox。 typedef struct VexNode { // 頂點的結(jié)構(gòu)表示 VertexType data。 ArcBox *firstin, *firstout。 } VexNode。 有向圖的十字鏈表存儲表示 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 typedef struct { VexNode xlist[N]。 //N為最大頂點數(shù) // 頂點結(jié)點 (表頭向量 ) int vexnum, arum。 //有向圖的當前頂點數(shù)和弧數(shù) } OLGraph。 有向圖的結(jié)構(gòu)表示 (十字鏈表 ) 圖的存儲結(jié)構(gòu)及實現(xiàn) 有向圖十字鏈表結(jié)構(gòu)表示的優(yōu)點： 容易求得頂點的入度和出度 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 Status CreateDG(OLGraph amp。G) {// 算法 // 采用 十字鏈表表示法 ， 構(gòu)造有向圖 G（ =DG)。 scanf(amp。,amp。,amp。IncInfo)。 //輸入頂點和弧的個數(shù) for (i=0。 i。 i++ ) { scanf(amp。[i].data)。 [i].firstin=Null。 [i].firstout=Null。 } // 初始化指針 for (k=0。 k。 ++k ) { scanf(amp。v1,amp。v2)。 i=LocateVex(G,v1。j=LocateVex(g,v2)} p=(arcBox*) malloc(sizeof(ArcBox))。 *p={I,j,[j].firstin,[i].firstout,Null} [j].firstin=[i].firstout=p。 if (incinfo) Input(*pinfo)。 } }//createDG 采用十字鏈表法構(gòu)造有向圖的算法 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 四、無向圖的鄰接多重表存儲表示 頂點的結(jié)點結(jié)構(gòu) data firstedge 邊的結(jié)點結(jié)構(gòu) mark ivex ilink jvex jlink info 盡管鄰接表能很好的表示無向圖，但每條邊（ vi，vj）有兩個結(jié)點，分別在第 i個和第 j個鏈表中，給圖的操作帶來不便。 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 A B C D 0 1 2 1 0 2 0 3 3 1 ? ? ? ? 四、無向圖的鄰接多重表存儲表示 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 四、無向圖的鄰接多重表存儲表示 Typedef emnu {unvisited,visited} VisitIf。 typedef struct Ebox { VisitIf mark。 // 訪問標記 int ivex, jvex。 //該邊依附的兩個頂點的位置 struct EBox *ilink, *jlink。 InfoType *info。 // 該邊信息指針 } EBox。 邊的結(jié)構(gòu)表示 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版） 清華大學(xué)出版社 typedef struct { // 鄰接多重表 VexBox adjmulist[N]。 int vexnum, edgenum。 } AMLGraph。 頂點的結(jié)構(gòu)表示 typedef struct VexBox { VertexType data。 EBox *firstedge。 // 指向第一條依附該頂點的邊 } VexBox。 無向圖的結(jié)構(gòu)表示 圖的存儲結(jié)構(gòu)及實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C版）