第二節(jié)圖的存儲結(jié)構(gòu)當(dāng)前講授對于具有n個頂點(diǎn)的圖，最常采用的存儲方法有鄰接矩陣存儲方法與鄰接表存儲方法。一、鄰接矩陣表示法1、鄰接矩陣設(shè)G=（V，E）是具有n個頂點(diǎn)的圖，則G的鄰接矩陣是具有如下定義的n階方陣：【例】2、采用鄰接矩陣存儲方法具有以下特點(diǎn)：①無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或者下）三角形陣的元素即可。②不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣（特別是對于稀疏圖），于是可以采用三元組表的方法存儲鄰接矩陣。③對于無向圖，鄰接矩陣的第i行（或者第i列）非零元素（或者非∞元素）的個數(shù)正好是第i個頂點(diǎn)的度D（Vi）。④對于有向圖，鄰接矩陣的第i行（或者第i列）非零元素（或者非∞元素）的個數(shù)正好是第i個頂點(diǎn)的出度OD（Vi）（或者入度ID（Vi））。⑤對于無向圖，鄰接矩陣的所有非零元素（或者非∞元素）的個數(shù)正好是邊數(shù)的2倍。⑥對于有向圖，鄰接矩陣的所有非零元素（或者非∞元素）的個數(shù)正好等于弧數(shù)。⑦一個圖的鄰接矩陣表示是唯一的?！菊骖}選解】（例題?填空題）若無向圖G中有n個頂點(diǎn)m條邊，采用鄰接矩陣存儲，則該矩陣中非0元素的個數(shù)為___________。隱藏答案【答案】2m【解析】對于無向圖，鄰接矩陣的所有非零元素的個數(shù)正好是邊數(shù)的2倍。3、鄰接矩陣表示的存儲結(jié)構(gòu)定義#defineMaxVertexNum50//最大頂點(diǎn)數(shù)typedefStruct{vertexTvpevexs[MaxVertexNum]；//頂點(diǎn)數(shù)組，類型假定為char型Adjmstrixarcs[MaxVertexNum][MaxVertexNum]；//鄰接矩陣，假定為int型}MGraph；4、建立一個無向網(wǎng)的算法【算法描述】VoidCreateMGraph(MGraph*G，intn，inte){//采用鄰接矩陣表示法構(gòu)造無向網(wǎng)G，n、e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)inti，j，k，w；scanf("%d，%d"，&n，&e)；//讀入頂點(diǎn)數(shù)和邊數(shù)for(i=0；i<n；i++)//輸入頂點(diǎn)信息scanf("%c"，&G->vexs[i])；for(i=0；i<n；i++)for(j=0；j<n；j++)G->arcs[i][j]=INT_MAX；//初始化鄰接矩陣元素為無窮大，一般填32767for(k=0；k<e；k++)//讀入e條邊，建立鄰接矩陣//讀入一條邊的兩端頂點(diǎn)序號i、j及邊上的權(quán)W{scanf("%d，%d，%d"，&i，&j，&w)；G->arcs[i][j]=w；G->arcs[j][i]=w；//置矩陣對稱元素權(quán)值｝｝算法的時間復(fù)雜度O(n2)二、鄰接表表示法1、鄰接表對于具有n個頂點(diǎn)的圖建立n個線性鏈表。每一個鏈表最前面都分別設(shè)置一個稱之為頂點(diǎn)表結(jié)點(diǎn)，n個頂點(diǎn)構(gòu)成一個數(shù)組結(jié)構(gòu)。第i個鏈表中的每一個鏈結(jié)點(diǎn)稱之為邊表結(jié)點(diǎn)?！纠?、采用鄰接表存儲方法具有以下特點(diǎn)：①一個圖的鄰接表表示法不唯一，這是因?yàn)猷徑颖碇懈鹘Y(jié)點(diǎn)的鏈接次序取決于建立鄰接表的算法（前插法還是后插法建鏈表）及邊的輸入次序。②對于無向圖，若它有n個頂點(diǎn)，e條邊，則其鄰接表中需要2e+n個結(jié)點(diǎn)。其中有2e個邊表結(jié)點(diǎn)，n個頂點(diǎn)表結(jié)點(diǎn)。邊表結(jié)點(diǎn)的個數(shù)一定是偶數(shù)，為邊數(shù)的2倍。③對于有向圖，若它有n個頂點(diǎn)，e條邊，則其鄰接表中需要e+n個結(jié)點(diǎn)。其中有e個邊表結(jié)點(diǎn)，n個頂點(diǎn)表結(jié)點(diǎn)。④對于無向圖，第i個鏈表中的邊表結(jié)點(diǎn)的數(shù)目是第i個頂點(diǎn)的度。⑤對于有向圖，第i個鏈表中的邊表結(jié)點(diǎn)的數(shù)目是第i個頂點(diǎn)的出度。在其逆鄰接表中，第i個鏈表中的邊表結(jié)點(diǎn)的數(shù)目是第i個頂點(diǎn)的入度。3、圖的鄰接表存儲結(jié)構(gòu)定義#defineMaxVertexNum20typedefcharVertexType；typedefstructnode//邊表結(jié)點(diǎn)類型｛intadjvexj//頂點(diǎn)的序號structnode*next；//指向下一條邊的指針｝EdgeNode；typedefstructvnode//頂點(diǎn)表結(jié)點(diǎn)｛VertexTypevertex；//頂點(diǎn)域EdgeNode*link；//邊表頭指針｝VNode，Adjlist[MaxVertexNum]；//鄰接表typedefAdjlistALGraph；//定義為圖類型4、無向圖鄰接表的建表算法：voidCreateGraph(ALGraphGL，intn，inte){//n為頂點(diǎn)數(shù)，e為圖的邊數(shù)inti，j，k；EdgeNode*p；for(i=0；i<n；i++)//建立頂點(diǎn)表{GL[i].vertex=getchar()；//讀入頂點(diǎn)信息GL[i].1ink=NULL；//邊表頭指針置空｝for(k=0；k<e；k++)//采用頭插法建立每個頂點(diǎn)的鄰接表{scanf("%d，%d"，&i，&j)；//讀入邊(vi，vj)的頂點(diǎn)序號p=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成新的邊表結(jié)點(diǎn)p->adjvex=j；//將鄰接點(diǎn)序號j賦給新結(jié)點(diǎn)的鄰接點(diǎn)域p->next=GL[i].1ink；GL[i].1ink=p；//將新結(jié)點(diǎn)插入到頂點(diǎn)vi的邊表頭部p=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成新的邊表結(jié)點(diǎn)p->adj.vex=i；//將鄰接點(diǎn)序號i賦給新結(jié)點(diǎn)的鄰接點(diǎn)域p->next=