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

1、*問題描述：建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。1、鄰接矩陣表示法:設G=(V,E)是一個圖，其中V=V1,V2,V3,Vn。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、一個對稱矩陣，例如 M2。用鄰接矩陣表示法來表示一個具有n個頂點的圖時，除了用鄰接矩陣中的n*n個元素存儲頂點間相鄰關系外，往往還需要另設一個向量存儲n個頂點的信息。因此其類型定義如下：VertexType vertexMAX_VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當前頂點數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標志 若圖中每個頂點只含一個編號i(1ivnum)，則只需一個二維數(shù)組表示圖的鄰接矩陣。此時存儲結構可簡單說明如下： type adjmatrix=array1.vnum,

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

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

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

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

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

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

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

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

11、化標志數(shù)組while （i<n）for：i1 to n do按要求訪問鄰接點end當用二維數(shù)組表示鄰接矩陣作圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2)，其中n為圖中頂點數(shù)。4、圖的廣度優(yōu)先遍歷算法分析beginfor i:=1 to n do(visitedi)初始化標志數(shù)組while （i<n）for：i1 to n doif.if.end二維數(shù)組表示鄰接矩陣作圖的存儲結構，其中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 /鄰接矩陣表示法的各個數(shù)據(jù)結構 VrType adj; / 頂點關系類型。對無權圖，用或表示相鄰否；對帶權圖，則為權值類型。 InfoType *info; / 該弧相關信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vertexMAX_VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當前頂點數(shù)和弧(邊)數(shù) GraphKind kind; / 圖的種類標志

14、MGraph;typedef struct/設置棧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)/用于返回輸弧端點所表示的數(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ù)組(鄰接矩陣)表示法,構造無向圖 int i,j,k,IncInfo; /i，j，k為計數(shù)器,IncInfo為標志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置輸入的弧的兩個頂

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

17、t;請輸入%d條邊的頂點頂點(以空格作為間隔): 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ù)組(鄰接矩陣)表示法,構造無向網(wǎng) int i,j,k,w,IncInfo; /i，j，k為計數(shù)器，w用于放置權值,IncInfo為標志符 char ch; /用于吃掉多余的字符 VertexType v1,v2; /用于放置輸入的弧的兩個頂點 printf("請輸入無向圖G的頂點數(shù),邊數(shù),

19、弧是否含相關信息（是：，否：）:n "); scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo); ch=getchar(); /用于吃掉回車 printf("請輸入%d個頂點的值(1個字符，空格隔開):n",G.vexnum); for(i=0;i<G.vexnum;+i) / 構造頂點向量 scanf("%c",&G.vertexi);ch=getchar(); printf("請輸入%d條邊的頂點頂點(以空格作為間隔): 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("請輸入該邊的權值: "); 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為計數(shù)器，visited20為標志符用于表示是否已經(jīng)訪問過 SeqStack p; for(i=0;i&l

22、t;G.vexnum;+i) /初始化標志符 visitedi=0; visited0=1; /規(guī)定以第一個字符開始遍歷 printf("深度優(yōu)先遍歷開始：n"); k=0;i=0; printf("%c ",G.vertex0); while(i<G.vexnum) /不斷以行循環(huán)在遇到符合條件時打印，每打印出一個就讓t加，把合適的值用棧來表示，把指針指向新的項 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) /當在某一行無法找到合適值時，輸出棧內(nèi)的值，返回上一行重新開始循環(huán) i=p.elem1p.top; p.top-; k-; if(t=G.vexnum)break; /當全部的定點都打印出來了就退出循環(huán) printf("n");void BreadthFirstSearch1(MGraph G) /無向圖、無向網(wǎng)廣度優(yōu)先遍歷int i,j,k,visited20

24、,t=1; /i,j為計數(shù)器，visited20為標志符用于表示是否已經(jīng)訪問過 SeqStack p; for(i=0;i<G.vexnum;+i) /初始化標志符 visitedi=0; visited0=1; /規(guī)定以第一個字符開始遍歷 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)在遇到符合條件時打印，每打印出一個就讓t加，把指針指向新的項 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) /構造圖printf("請輸入要構造的圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3):n");scanf