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

1、*問(wèn)題描述： 建立圖的存儲(chǔ)結(jié)構(gòu)(圖的類(lèi)型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)， 學(xué)生可以任選兩種類(lèi)型)，能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ) 結(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和無(wú)向圖G2的鄰接矩陣分別為 M1和M2:M1=廠(chǎng) 0 1 0 1 n| 1 0 1 0 | 1 0 0 1 |L 0 0 0 0M2=廠(chǎng) 0 1 1 1 n1 0 1 01 1 0 1L

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

3、如下：type adjmatrix=array1.vnum,1.vnumof adj; 利用鄰接矩陣很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊 (或弧) 相聯(lián)，并容易 求得各個(gè)頂點(diǎn)的度。對(duì)于無(wú)向圖，頂點(diǎn) Vi 的度是鄰接矩陣中第 i 行元素之和，即nnD(Vi戸刀 Ai,j(或刀 Ai,j)j=1i=1對(duì)于有向圖，頂點(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 = g ,否則

4、。其中Wij為<Vi,Vj>或(Vi,Vj)上的權(quán)值。相應(yīng)地，網(wǎng)的鄰接矩陣表示的類(lèi)型 定義應(yīng)作如下的修改：adj:weightype ; weightype 為權(quán)類(lèi)型 圖 5-6 列出一個(gè)網(wǎng)和它的鄰接矩陣。ig3gg|Igg51g|ggggg|g 3 2 2 g(a)網(wǎng)(b)鄰接矩陣圖 5-6 網(wǎng)及其鄰接矩陣對(duì)無(wú)向圖或無(wú)向網(wǎng)絡(luò)， 由于其鄰接矩陣是對(duì)稱(chēng)的， 故可采用壓縮存貯的方法， 僅存貯下三角或上三角中的元素(但不含對(duì)角線(xiàn)上的元素)即可。顯然，鄰接矩陣 表示法的空間復(fù)雜度0(n2)。無(wú)向網(wǎng)鄰接矩陣的建立方法是：首先將矩陣A的每個(gè)元素都初始化成。然后，讀入邊及權(quán)值(i,j,wij),

5、將A的相應(yīng)元素置成 Wij。2、圖的遍歷：*深度優(yōu)先搜索深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的先根遍歷， 是樹(shù)的先根遍歷的推廣。假設(shè)初始 狀態(tài)是圖中所有的頂點(diǎn)未曾被訪(fǎng)問(wèn)，則深度優(yōu)先遍歷可從圖的某個(gè)頂點(diǎn) V出發(fā), 訪(fǎng)問(wèn)此頂點(diǎn)，然后依次從V的未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖， 直至圖中 所有和V有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，貝U另選 圖中的一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。以圖7.13(a)中無(wú)向圖G4為例，深度優(yōu)先遍歷圖的過(guò)程如圖 7.13(b)所示。 假設(shè)從頂點(diǎn)Vi出發(fā)進(jìn)行搜索，在訪(fǎng)問(wèn)了頂點(diǎn) Vi后，選擇鄰接點(diǎn)口。因?yàn)閂2未曾 訪(fǎng)問(wèn)，則從W出發(fā)進(jìn)

6、行搜索。依次類(lèi)推，接著從 V4,V8,V5出發(fā)進(jìn)行搜索。在訪(fǎng)問(wèn) 了 V5之后，由于V5的鄰接點(diǎn)已都被訪(fǎng)問(wèn)，貝U搜索回到 匕 由于同樣的理由，搜 索繼續(xù)回到V4，V2直至Vi，此時(shí)由于Vi的另一個(gè)鄰接點(diǎn)為被訪(fǎng)問(wèn)，則搜索又從 Vi到V3,再繼續(xù)進(jìn)行下去。由此得到頂點(diǎn)的訪(fǎng)問(wèn)序列為：ViVT V 4V8V5V3V6V7一 一顯然，這是一個(gè)遞歸的過(guò)程。為了在遍歷過(guò)程中便于區(qū)別頂點(diǎn)是否已被訪(fǎng)問(wèn)， 需附設(shè)訪(fǎng)問(wèn)標(biāo)志數(shù)組vistedO.n-i,其初值為0，一但某個(gè)頂點(diǎn)被訪(fǎng)問(wèn)，則其相應(yīng)的分量置為i。*廣度優(yōu)先搜索假設(shè)從圖中某頂點(diǎn)V出發(fā)，在訪(fǎng)問(wèn)了 V之后一次訪(fǎng)問(wèn)V的各個(gè)未曾訪(fǎng)問(wèn)的擴(kuò) 大鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出

7、發(fā)依次訪(fǎng)問(wèn)他們的鄰接點(diǎn)，并使“先被訪(fǎng)問(wèn)的鄰接點(diǎn)”先于“后被訪(fǎng)問(wèn)的鄰接點(diǎn)”被訪(fǎng)問(wèn)，直至圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的 鄰接點(diǎn)都被訪(fǎng)問(wèn)到。若圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂 點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中的頂點(diǎn)都被訪(fǎng)問(wèn)為止。 換句話(huà)說(shuō)，廣度優(yōu) 先遍歷圖的過(guò)程就是以V為起始點(diǎn)，有遠(yuǎn)至近，依次訪(fǎng)問(wèn)和V有路徑相通且路徑 長(zhǎng)度為1、2,的頂點(diǎn)。 例如，對(duì)圖G4進(jìn)行廣度優(yōu)先搜索遍歷的過(guò)程如圖 7.13(3)所示，首先訪(fǎng)問(wèn)v1和v1的鄰接點(diǎn)v2和v3,然后依次訪(fǎng)問(wèn)v2的鄰接點(diǎn)v4 和v5及v3的鄰接點(diǎn)v6和v7,最后訪(fǎng)問(wèn)v4的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接 點(diǎn)均已被訪(fǎng)問(wèn)，并且圖中所有頂點(diǎn)都被訪(fǎng)

8、問(wèn)，由此完成了圖的遍歷。得到的頂點(diǎn) 訪(fǎng)問(wèn)序列為VV V3-* V* VV6* -和深度優(yōu)先搜索類(lèi)似，在遍歷的過(guò)程中也需要一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組。并且，為了順次訪(fǎng)問(wèn)路徑長(zhǎng)度為 2、3、，的頂點(diǎn)，需附設(shè)隊(duì)列以存儲(chǔ)已被訪(fǎng)問(wèn)的路徑長(zhǎng) 度為1、2,的頂點(diǎn)。2、圖的輸出圖的鄰接矩陣是一個(gè)二維數(shù)組，運(yùn)用 for語(yǔ)句的嵌套依次輸出。i = i+1主程序流程圖圖的構(gòu)造流程圖1、無(wú)向圖鄰接矩陣的建立算法如下：procedure build-graph;建立無(wú)向圖的鄰接矩陣beg infor i:=1 to n do read(G.vertexi) ；讀入 n 個(gè)頂點(diǎn)的信息for i:=1 to n do for j:=

9、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.arcsij = G.arcsii 置對(duì)稱(chēng)弧end；該算法的執(zhí)行時(shí)間是 0( n+n2+e),其中消耗在鄰接矩陣初始化操作上的時(shí)間 是0(n2),而e<n2，所以上述算法的時(shí)間復(fù)雜度是 0(n2)。2、無(wú)向網(wǎng)鄰接矩陣的建立算法如下：procedure build-graph; 建立無(wú)向網(wǎng)的鄰接矩陣 beginfor i:=1 to n do read(G.vertexi)；讀入 n 個(gè)頂

10、點(diǎn)的信息 for i:=1 to n dofor j:=1 to e doG.arcsij=maxint ；將鄰接矩陣的每個(gè)元素初始化成 maxi nt計(jì)算機(jī)內(nèi)用最大事數(shù) maxi nt表示 for k:=1 to e do e 為邊的數(shù)目 read(i,j,w) 讀入邊 <i,j> 和權(quán)G.arcsij:=w;G.arcsij:=we nd ;該算法的執(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： i = 1 to n do 按要求訪(fǎng)問(wèn)鄰接點(diǎn) end當(dāng)用二維數(shù)組表示鄰接矩陣作圖的存儲(chǔ)結(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： i = 1 to n do if.if .end二維數(shù)組表示鄰接矩陣作圖的存儲(chǔ)結(jié)構(gòu)，其中 n 為圖中頂點(diǎn)數(shù) ,查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為 O(n2)/* Graph.h */#include <stdio.h>#incl

12、ude <malloc.h>#include <conio.h>#include <stdlib.h> #include <string.h> #define ERROR 0#define OK 1#define MAX_VERTEX_NUM 2/0定義最大值#define INFINITY 32768 / 定義極大值#define MAX_INFO 20 typedefint VrType; / 定義新的類(lèi)型 typedefint InfoType;typedefchar VertexType;typedefenumDG,DN,UDG,UDNG

13、raphKind/;/ 有向圖, 有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng) typedefstruct ArcCell/ 鄰接矩陣表示法的各個(gè)數(shù)據(jù)結(jié)構(gòu)VrType adj; / 頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖，用或表示相鄰否；對(duì)帶權(quán)圖，則 為權(quán)值類(lèi)型。InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedefstructVertexType vertexMAX_VERTEX_NUM; / 頂點(diǎn)向量AdjMatrix arcs; / 鄰接矩陣int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧 （ 邊）

14、數(shù)GraphKind kind; / 圖的種類(lèi)標(biāo)志 MGraph;typedefstruct/ 設(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 D

15、isplay(MGraph G);/* Graph.cpp */#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)造無(wú)向圖int i,j,k,IncInfo;/i , j , k為計(jì)數(shù)器，lnclnfo為標(biāo)志符char ch; / 用

16、于吃掉多余的字符VertexType v1,v2; / 用于放置輸入的弧的兩個(gè)頂點(diǎn)printf("請(qǐng)輸入無(wú)向圖G的頂點(diǎn)數(shù),邊數(shù),弧是否含相關(guān)信息(是：，否：)：n");scanf( "%d,%d,%d",&G.vexnum,&G.arcnum,&lnclnfo);ch=getchar(); / 用于吃掉回車(chē)printf("請(qǐng)輸入個(gè)頂點(diǎn)的值(1個(gè)字符，空格隔開(kāi)):n" ,G.vexnum);for (i=0;i<G.vexnum;+i) / 構(gòu)造頂點(diǎn)向量scanf( "%c",&

17、G.vertexi);ch=getchar();printf("請(qǐng)輸入條邊的頂點(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;/ adj,infoG.=NULL;for (k=0;k<G.arcnum;+k)scanf( "%c %c",&v1,&v2); ch=getchar(); / ch 吃掉回車(chē)符 i=LocateVertex(G,v1); j=

18、LocateVertex(G,v2);if (IncInfo)scanf( "%d",&G.);G.arcsij.adj=G.arcsji.adj=1;/ 置<v1,v2> 的對(duì)稱(chēng)弧<v2,v1>/CreateUDGvoid CreateUDN(MGraph &G) / 采用數(shù)組 ( 鄰接矩陣 )表示法 , 構(gòu)造無(wú)向網(wǎng)int i,j,k,w,IncInfo;/i , j , k為計(jì)數(shù)器，w用于放置權(quán)值，lnclnfo為標(biāo)志符:nchar ch; / 用于吃掉多余的字符 VertexType v1,v2;/ 用于放

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

20、quot;請(qǐng)輸入條邊的頂點(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,infofor (k=0;k<G.arcnum;+k)scanf( "%c %c",&v1,&v2);ch=getchar();/ ch 吃掉回車(chē)符printf("請(qǐng)輸入該邊的權(quán)值 : " );scanf( "%d",&

21、w); ch=getchar();i=LocateVertex(G,v1);j=LocateVertex(G,v2);G.arcsij.adj=w;if (IncInfo)scanf( "%d",&G.);G.arcsij=G.arcsji; / 置 <v1,v2> 的對(duì)稱(chēng)弧 <v2,v1> /CreateUDN void DepthFirstSearch1(MGraph G)/ 無(wú)向圖、無(wú)向網(wǎng)深度優(yōu)先遍歷int i,j,k,visited20,t=1,a=1; /i,j,k 為計(jì)數(shù)器， visited20 為標(biāo)志 符用

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

23、.arcsij.adj!=INFINITY&&visitedj=0)printf( "%c " ,G.vertexj); visitedj=1;p.elem1k=i;p.top=k; k+;i+;a+;t+;break ;if (j=G.vexnum) / 當(dāng)在某一行無(wú)法找到合適值時(shí)， 輸出棧內(nèi)的值， 返回上一行 重新開(kāi)始循環(huán)i=p.elem1p.top;p.top-; k-;if (t=G.vexnum) break ; / 當(dāng)全部的定點(diǎn)都打印出來(lái)了就退出循環(huán)printf( "n" );void BreadthFirstSearch1(

24、MGraph G)/ 無(wú)向圖、無(wú)向網(wǎng)廣度優(yōu)先遍歷int i,j,k,visited20,t=1; /i,j 為計(jì)數(shù)器， visited20 為標(biāo)志符用于 表示是否已經(jīng)訪(fǎng)問(wèn)過(guò)SeqStack p;for (i=0;i<G.vexnum;+i) / 初始化標(biāo)志符visitedi=0;visited0=1; / 規(guī)定以第一個(gè)字符開(kāi)始遍歷printf(" 廣度優(yōu)先遍歷開(kāi)始： n" );k=0;i=0;printf( "%c " ,G.vertex0);while (i<G.vexnum)for (j=0;j<G.vexnum;+j) / 不斷以

25、行循環(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+;/ 換行，重新開(kāi)始循環(huán)if (t=G.vexnum) break ;printf("n" );int CreateGraph(MGraph &G) / 構(gòu)造圖printf( "請(qǐng)輸入要構(gòu)造的圖的類(lèi)型 ( 有向圖:0, 有向網(wǎng) :1, 無(wú)向圖:2, 無(wú)向 網(wǎng) :3):n" );scan