鄰接矩陣表示圖-深度-廣度優(yōu)先遍歷

1、*問題描述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。1、鄰接矩陣表示法:設(shè)G=(V,E)是一個(gè)圖，其中V=V1,V2,V3,Vn。G的鄰接矩陣是一個(gè)他有下述性質(zhì)的n階方陣： 1，若(Vi,Vj)E 或<Vi,Vj>E； Ai,j=0， 反之圖5-2中有向圖G1和無向圖G2的鄰接矩陣分別為 M1和 M2:M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 M2= 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 注意無向圖的鄰接是

2、一個(gè)對稱矩陣，例如 M2。用鄰接矩陣表示法來表示一個(gè)具有n個(gè)頂點(diǎn)的圖時(shí)，除了用鄰接矩陣中的n*n個(gè)元素存儲頂點(diǎn)間相鄰關(guān)系外，往往還需要另設(shè)一個(gè)向量存儲n個(gè)頂點(diǎn)的信息。因此其類型定義如下：VertexType vertexMAX_VERTEX_NUM; / 頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志 若圖中每個(gè)頂點(diǎn)只含一個(gè)編號i(1ivnum)，則只需一個(gè)二維數(shù)組表示圖的鄰接矩陣。此時(shí)存儲結(jié)構(gòu)可簡單說明如下： type adjmatrix=array1.vnum,

3、1.vnumof adj;利用鄰接矩陣很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊（或?。┫嗦?lián)，并容易求得各個(gè)頂點(diǎn)的度。對于無向圖，頂點(diǎn)Vi的度是鄰接矩陣中第i行元素之和，即nnD(Vi)Ai,j （或Ai,j） j=1 i=1對于有向圖，頂點(diǎn)Vi的出度OD(Vi)為鄰接矩陣第i行元素之和，頂點(diǎn)Vi的入度ID(Vi)為第i列元素之和。即 nnOD(Vi)Ai,j， OD(Vi)Aj,i） j=1j=1用鄰接矩陣也可以表示帶權(quán)圖，只要令Wij, 若<Vi,Vj>或(Vi,Vj)Ai,j , 否則。其中Wij為<Vi,Vj>或(Vi,Vj)上的權(quán)值。相應(yīng)地，網(wǎng)的鄰接矩陣表示的類型定義

4、應(yīng)作如下的修改： adj:weightype ; weightype為權(quán)類型圖5-6列出一個(gè)網(wǎng)和它的鄰接矩陣。 (a)網(wǎng)(b)鄰接矩陣圖5-6 網(wǎng)及其鄰接矩陣對無向圖或無向網(wǎng)絡(luò)，由于其鄰接矩陣是對稱的，故可采用壓縮存貯的方法，僅存貯下三角或上三角中的元素(但不含對角線上的元素)即可。顯然，鄰接矩陣表示法的空間復(fù)雜度O(n2)。無向網(wǎng)鄰接矩陣的建立方法是：首先將矩陣A的每個(gè)元素都初始化成。然后，讀入邊及權(quán)值(i,j,wij),將A的相應(yīng)元素置成Wij。2、圖的遍歷：*深度優(yōu)先搜索深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有的頂點(diǎn)未曾被訪問，則深度優(yōu)先遍歷可從圖

5、的某個(gè)頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)，然后依次從V的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中的一個(gè)未被訪問的頂點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。以圖7.13(a)中無向圖G4為例，深度優(yōu)先遍歷圖的過程如圖7.13(b)所示。假設(shè)從頂點(diǎn)V1出發(fā)進(jìn)行搜索，在訪問了頂點(diǎn)V1后，選擇鄰接點(diǎn)V2。因?yàn)閂2未曾訪問，則從V2出發(fā)進(jìn)行搜索。依次類推，接著從V4,V8,V5出發(fā)進(jìn)行搜索。在訪問了V5之后，由于V5的鄰接點(diǎn)已都被訪問，則搜索回到V8。由于同樣的理由，搜索繼續(xù)回到V4，V2直至V1，此時(shí)由于V1的另一個(gè)鄰接點(diǎn)為被

6、訪問，則搜索又從V1到V3，再繼續(xù)進(jìn)行下去。由此得到頂點(diǎn)的訪問序列為：V1 V2 V4 V8 V5 V3 V6 V7顯然，這是一個(gè)遞歸的過程。為了在遍歷過程中便于區(qū)別頂點(diǎn)是否已被訪問，需附設(shè)訪問標(biāo)志數(shù)組visted0.n-1,其初值為0，一但某個(gè)頂點(diǎn)被訪問，則其相應(yīng)的分量置為1。*廣度優(yōu)先搜索 假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后一次訪問v的各個(gè)未曾訪問的擴(kuò)大鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問他們的鄰接點(diǎn)，并使“先被訪問的鄰接點(diǎn)”先于“后被訪問的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直

7、到圖中的頂點(diǎn)都被訪問為止。換句話說，廣度優(yōu)先遍歷圖的過程就是以v為起始點(diǎn)，有遠(yuǎn)至近，依次訪問和v有路徑相通且路徑長度為1、2的頂點(diǎn)。例如，對圖G4進(jìn)行廣度優(yōu)先搜索遍歷的過程如圖7.13（3）所示，首先訪問v1和v1的鄰接點(diǎn)v2和v3，然后依次訪問v2的鄰接點(diǎn)v4和v5及v3的鄰接點(diǎn)v6和v7，最后訪問v4的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都被訪問，由此完成了圖的遍歷。得到的頂點(diǎn)訪問序列為 V1 V2 V3 V4 V5 V6 V7 V8和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個(gè)訪問標(biāo)志數(shù)組。并且，為了順次訪問路徑長度為2、3、的頂點(diǎn)，需附設(shè)隊(duì)列以存儲已被訪問的路徑長

8、度為1、2的頂點(diǎn)。2、圖的輸出 圖的鄰接矩陣是一個(gè)二維數(shù)組，運(yùn)用for語句的嵌套依次輸出。開始開始輸入vexnum，arcnumIncInfo選擇圖的類型構(gòu)造圖ii+1輸入頂點(diǎn)i<vexnumY深度遍歷廣度遍歷jj+1N初始化鄰接矩陣i<vexnum結(jié)束Yj<vexnumNYii+1N主程序流程圖k<arcnumkk+1輸入弧的信息設(shè)置鄰接矩陣YN結(jié)束圖的構(gòu)造流程圖1、無向圖鄰接矩陣的建立算法如下：procedure build-graph; 建立無向圖的鄰接矩陣beginfor i:=1 to n do read(G.vertexi)； 讀入n個(gè)頂點(diǎn)的信息for i:

9、=1 to n dofor j:=1 to e doG.arcsij =0；將鄰接矩陣的每個(gè)元素初始化成0 for k:=1 to e do e為邊的數(shù)目 read(i,j,w) 讀入邊<i,j>和權(quán)G.arcsij:=wG.arcsijG.arcsii置對稱弧 end；該算法的執(zhí)行時(shí)間是O(n+n2+e),其中消耗在鄰接矩陣初始化操作上的時(shí)間是O(n2),而e<n2，所以上述算法的時(shí)間復(fù)雜度是O(n2)。 2、無向網(wǎng)鄰接矩陣的建立算法如下：procedure build-graph; 建立無向網(wǎng)的鄰接矩陣beginfor i:=1 to n do read(G.vertex

10、i)； 讀入n個(gè)頂點(diǎn)的信息for i:=1 to n dofor j:=1 to e doG.arcsij =maxint；將鄰接矩陣的每個(gè)元素初始化成maxint,計(jì)算機(jī)內(nèi)用最大事數(shù)maxint表示for k:=1 to e do e為邊的數(shù)目 read(i,j,w) 讀入邊<i,j>和權(quán)G.arcsij:=w; G.arcsij:=w end；該算法的執(zhí)行時(shí)間是O(n+n2+e),其中消耗在鄰接矩陣初始化操作上的時(shí)間是O(n2),而e<n2，所以上述算法的時(shí)間復(fù)雜度是O(n2)。3、圖的深度優(yōu)先遍歷算法分析beginfor i:=1 to n do(visitedi)初始

11、化標(biāo)志數(shù)組while （i<n）for：i1 to n do按要求訪問鄰接點(diǎn)end當(dāng)用二維數(shù)組表示鄰接矩陣作圖的存儲結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)，其中n為圖中頂點(diǎn)數(shù)。4、圖的廣度優(yōu)先遍歷算法分析beginfor i:=1 to n do(visitedi)初始化標(biāo)志數(shù)組while （i<n）for：i1 to n doif.if.end二維數(shù)組表示鄰接矩陣作圖的存儲結(jié)構(gòu)，其中n為圖中頂點(diǎn)數(shù),查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)。/* Graph.h */#include<stdio.h> #include<malloc.h> #inc

12、lude<conio.h> #include<stdlib.h> #include<string.h>#define ERROR 0#define OK 1#define MAX_VERTEX_NUM 20 /定義最大值#define INFINITY 32768 /定義極大值#define MAX_INFO 20typedef int VrType; /定義新的類型typedef int InfoType;typedef char VertexType;typedef enum DG,DN,UDG,UDNGraphKind;/有向圖,有向網(wǎng),無向圖,無向網(wǎng)

13、typedef struct ArcCell /鄰接矩陣表示法的各個(gè)數(shù)據(jù)結(jié)構(gòu) VrType adj; / 頂點(diǎn)關(guān)系類型。對無權(quán)圖，用或表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vertexMAX_VERTEX_NUM; / 頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標(biāo)志

14、MGraph;typedef struct/設(shè)置棧int elem1MAX_VERTEX_NUM;int top;SeqStack;int LocateVertex(MGraph G,VertexType v);void CreateUDG(MGraph &G);void CreateUDN(MGraph &G); void DepthFirstSearch1(MGraph G);void BreadthFirstSearch1(MGraph G);int CreateGraph(MGraph &G);void Display(MGraph G);/* Graph.cp

15、p */#include"Graph.h"int LocateVertex(MGraph G,VertexType v)/用于返回輸弧端點(diǎn)所表示的數(shù)值int j=0,k;for(k=0;k<G.vexnum;+k)if(G.vertexk=v)j=k;break;return(j);void CreateUDG(MGraph &G) / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向圖 int i,j,k,IncInfo; /i，j，k為計(jì)數(shù)器,IncInfo為標(biāo)志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置輸入的弧的兩個(gè)頂

16、點(diǎn) printf("請輸入無向圖G的頂點(diǎn)數(shù),邊數(shù),弧是否含相關(guān)信息（是：，否：）: n"); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); /用于吃掉回車 printf("請輸入%d個(gè)頂點(diǎn)的值(1個(gè)字符，空格隔開):n",G.vexnum); for(i=0;i<G.vexnum;+i) / 構(gòu)造頂點(diǎn)向量 scanf("%c",&G.vertexi);ch=getchar(); printf(&quo

17、t;請輸入%d條邊的頂點(diǎn)頂點(diǎn)(以空格作為間隔): n",G.arcnum); for(i=0;i<G.vexnum;+i) / 初始化鄰接矩陣 for(j=0;j<G.vexnum;+j) G.arcsij.adj=0; G.=NULL; / adj,info for(k=0;k<G.arcnum;+k) scanf("%c %c",&v1,&v2); ch=getchar();/ ch吃掉回車符 i=LocateVertex(G,v1); j=LocateVertex(G,v2); if(IncInfo)s

18、canf("%d",&G.); G.arcsij.adj=G.arcsji.adj=1; / 置<v1,v2>的對稱弧<v2,v1> /CreateUDG void CreateUDN(MGraph &G) / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng) int i,j,k,w,IncInfo; /i，j，k為計(jì)數(shù)器，w用于放置權(quán)值,IncInfo為標(biāo)志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置輸入的弧的兩個(gè)頂點(diǎn) printf("請輸入無向圖G的頂點(diǎn)數(shù),邊數(shù),

19、弧是否含相關(guān)信息（是：，否：）:n "); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); /用于吃掉回車 printf("請輸入%d個(gè)頂點(diǎn)的值(1個(gè)字符，空格隔開):n",G.vexnum); for(i=0;i<G.vexnum;+i) / 構(gòu)造頂點(diǎn)向量 scanf("%c",&G.vertexi);ch=getchar(); printf("請輸入%d條邊的頂點(diǎn)頂點(diǎn)(以空格作為間隔): n&quo

20、t;,G.arcnum); for(i=0;i<G.vexnum;+i) / 初始化鄰接矩陣 for(j=0;j<G.vexnum;+j) G.arcsij.adj=0; G.=NULL; /adj,info for(k=0;k<G.arcnum;+k) scanf("%c %c",&v1,&v2); ch=getchar();/ ch吃掉回車符 printf("請輸入該邊的權(quán)值: "); scanf("%d",&w); ch=getchar(); i=LocateVer

21、tex(G,v1); j=LocateVertex(G,v2); G.arcsij.adj=w; if(IncInfo)scanf("%d",&G.); G.arcsij=G.arcsji; / 置<v1,v2>的對稱弧<v2,v1> /CreateUDNvoid DepthFirstSearch1(MGraph G) /無向圖、無向網(wǎng)深度優(yōu)先遍歷int i,j,k,visited20,t=1,a=1; /i,j,k為計(jì)數(shù)器，visited20為標(biāo)志符用于表示是否已經(jīng)訪問過 SeqStack p; for(i=0;i&l

22、t;G.vexnum;+i) /初始化標(biāo)志符 visitedi=0; visited0=1; /規(guī)定以第一個(gè)字符開始遍歷 printf("深度優(yōu)先遍歷開始：n"); k=0;i=0; printf("%c ",G.vertex0); while(i<G.vexnum) /不斷以行循環(huán)在遇到符合條件時(shí)打印，每打印出一個(gè)就讓t加，把合適的值用棧來表示，把指針指向新的項(xiàng) for(j=0;j<G.vexnum;+j) if(G.arcsij.adj!=0&&G.arcsij.adj!=INFINITY&&visited

23、j=0) printf("%c ",G.vertexj); visitedj=1; p.elem1k=i; p.top=k; k+;i+;a+;t+; break; if(j=G.vexnum) /當(dāng)在某一行無法找到合適值時(shí)，輸出棧內(nèi)的值，返回上一行重新開始循環(huán) i=p.elem1p.top; p.top-; k-; if(t=G.vexnum)break; /當(dāng)全部的定點(diǎn)都打印出來了就退出循環(huán) printf("n");void BreadthFirstSearch1(MGraph G) /無向圖、無向網(wǎng)廣度優(yōu)先遍歷int i,j,k,visited20

24、,t=1; /i,j為計(jì)數(shù)器，visited20為標(biāo)志符用于表示是否已經(jīng)訪問過 SeqStack p; for(i=0;i<G.vexnum;+i) /初始化標(biāo)志符 visitedi=0; visited0=1; /規(guī)定以第一個(gè)字符開始遍歷 printf("廣度優(yōu)先遍歷開始：n"); k=0;i=0; printf("%c ",G.vertex0); while(i<G.vexnum) for(j=0;j<G.vexnum;+j)/不斷以行循環(huán)在遇到符合條件時(shí)打印，每打印出一個(gè)就讓t加，把指針指向新的項(xiàng) if(G.arcsij.adj!=0&&G.arcsij.adj!=INFINITY&&visitedj=0) printf("%c ",G.vertexj); visitedj=1; p.elem1k=i; p.top=k; k+; t+; i+; /換行，重新開始循環(huán) if(t=G.vexnum)break; printf("n");int CreateGraph(MGraph &G) /構(gòu)造圖printf("請輸入要構(gòu)造的圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3):n");scanf