6-3-1圖的鄰接矩陣存儲結(jié)構(gòu)及實(shí)現(xiàn)-數(shù)據(jù)結(jié)構(gòu)-從概念到Java實(shí)現(xiàn)-王紅梅-清華大學(xué)出版社

6-3-1圖的鄰接矩陣存儲結(jié)構(gòu)及實(shí)現(xiàn)v第六章圖圖的存儲結(jié)構(gòu)圖是否可以采用順序存儲結(jié)構(gòu)？在圖中，任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊）無法通過存儲位置表示這種任意的邏輯關(guān)系圖無法采用順序存儲結(jié)構(gòu)如何存儲圖呢？圖是由頂點(diǎn)和邊組成分別考慮如何存儲頂點(diǎn)如何存儲邊圖的鄰接矩陣存儲結(jié)構(gòu)講什么？鄰接矩陣的實(shí)現(xiàn)——建立鄰接矩陣的實(shí)現(xiàn)——深度優(yōu)先遍歷鄰接矩陣的實(shí)現(xiàn)——廣度優(yōu)先遍歷存儲思想設(shè)G＝(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它鄰接矩陣也稱數(shù)組表示法，其基本思想是：一維數(shù)組：存儲圖中頂點(diǎn)的信息二維數(shù)組（鄰接矩陣）：存儲圖中各頂點(diǎn)之間的鄰接關(guān)系存儲示意圖v0v3v2v1v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3無向圖的鄰接矩陣有什么特點(diǎn)？對稱矩陣如何求頂點(diǎn)v

的度？第v行（或第v列）非零元素的個(gè)數(shù)如何判斷頂點(diǎn)i和

j之間是否存在邊？if(edge[i][j]==1)0123存儲示意圖v0v3v2v1如何求頂點(diǎn)i的所有鄰接點(diǎn)？掃描第i

行for(j=0;j<n;j++)if(edge[i][j]==1)

頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn)v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v30123存儲示意圖有向圖的鄰接矩陣一定不對稱嗎？頂點(diǎn)間存在方向相反的弧如何求頂點(diǎn)v

的出度？第v行非零元素的個(gè)數(shù)v0v3v2v1如何求頂點(diǎn)v

的入度？第v列非零元素的個(gè)數(shù)v0v1v2v3vertex=01011010

1

0000

000edge=v0

v1

v2

v3v0v1v2v30123v0v1v2v3vertex=05

∞

2

508

7

∞

80∞2

7

∞0edge=v0

v1

v2

v3v0v1v2v3v0v3v2v12785網(wǎng)圖的鄰接矩陣可定義為：arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他存儲示意圖01231.圖的鄰接矩陣采用數(shù)組方式進(jìn)行存儲，因此屬于順序存儲結(jié)構(gòu)。正確錯誤AB提交單選題5分2.無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的。正確錯誤AB提交單選題5分3.用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與圖的邊數(shù)無關(guān)。正確錯誤AB提交單選題5分4.圖采用鄰接矩陣存儲，查找某頂點(diǎn)的所有鄰接點(diǎn)，時(shí)間復(fù)雜度是（）。O(1)O(n)O(n+e)D.O(n2)ABCD提交單選題5分5.對于圖6-4所示有向圖，畫出鄰接矩陣存儲示意圖。作答正常使用主觀題需2.0以上版本雨課堂主觀題10分鄰接矩陣的類定義publicinterfaceBinaryTreeInterface<T>{publicvoidDFS(intstartIndex);

//圖的深度優(yōu)先遍歷

publicvoidBFS(intstartIndex);

//圖的廣度優(yōu)先遍歷}publicclassMGraph<T>implementsGraphInterface<T>{protectedintvertices_num; //圖的頂點(diǎn)數(shù)

protectedintedge_num; //圖的邊數(shù)

protectedT[]vertices;//一維數(shù)組存儲圖頂點(diǎn)

protectedint[][]adjMatrix;//二維數(shù)組實(shí)現(xiàn)鄰接矩陣

boolean[]visited; //訪問標(biāo)志數(shù)組 //成員函數(shù)實(shí)現(xiàn)圖接口函數(shù)}圖的抽象數(shù)據(jù)類型定義？ADTGraphDataModel…Operation

initGraph

：圖的初始化

DFT：深度優(yōu)先遍歷圖BFT：廣度優(yōu)先遍歷圖endADT建立一個(gè)圖的函數(shù)原型是什么？initGraph

輸入：n

個(gè)頂點(diǎn)

e

條邊

功能：圖的建立

輸出：構(gòu)造一個(gè)含有

n

個(gè)頂點(diǎn)

e

條邊的圖構(gòu)造函數(shù)v0v3v2v1v0v1v2v3a=v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v344vertexNumedgeNum構(gòu)造函數(shù)做什么？偽代碼算法：initGraph輸入：頂點(diǎn)的數(shù)據(jù)a[n]，頂點(diǎn)個(gè)數(shù)n，邊的個(gè)數(shù)e輸出：圖的鄰接矩陣1.存儲圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.將頂點(diǎn)信息存儲在一維數(shù)組vertex中；3.初始化鄰接矩陣edge；4.依次輸入每條邊并存儲在鄰接矩陣edge中：4.1輸入邊依附的兩個(gè)頂點(diǎn)的編號

i

和

j；4.2將edge[i][j]和edge[j][i]的值置為

1；算法描述publicinitGraph(T[]init_vertices,intn,inte){if(n==0)thrownewGraphException("無頂點(diǎn)，圖構(gòu)造失敗。");vertices_num=n; //初始化頂點(diǎn)個(gè)數(shù)this.edge_num=e; //初始化邊個(gè)數(shù)this.vertices=(T[])newObject[vertices_num]; //定義頂點(diǎn)數(shù)組this.adjMatrix=newint[vertices_num][vertices_num];//鄰接矩陣分配空間for(inti=0;i<n;i++){vertices[i]=init_vertices[i];} //初始化頂點(diǎn)數(shù)組

if(edge_num>0){ //初始化鄰接矩陣Scannerreader=newScanner(System.in);for(inti=1;i<=e;i++){System.out.println("輸入第"+i+"條邊第1個(gè)頂點(diǎn)信息");intvertex1=reader.nextInt();System.out.println("輸入第"+i+"條邊第2個(gè)頂點(diǎn)信息");intvertex2=reader.nextInt();adjMatrix[vertex1][vertex2]=1;adjMatrix[vertex2][vertex1]=1;}

}}深度遍歷算法：DFT輸入：頂點(diǎn)的編號v輸出：圖的深度優(yōu)先遍歷序列1.訪問頂點(diǎn)v;修改標(biāo)志visited[v]=1;2.j=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)；3.while(j存在)3.1if(j未被訪問)從頂點(diǎn)j出發(fā)遞歸執(zhí)行該算法;3.2j=頂點(diǎn)v的下一個(gè)鄰接點(diǎn);如何在鄰接矩陣中求某頂點(diǎn)的鄰接點(diǎn)？深度遍歷publicvoidDFT(intstartIndex){ visited=newboolean[vertices_num]; //初始化訪問標(biāo)志數(shù)組 iteratorDFT(startIndex);}privatevoiditeratorDFT(intstartIndex){ //深度優(yōu)先遍歷遞歸算法System.out.print(vertices[startIndex].toString()+""); //輸出訪問頂點(diǎn)visited[startIndex]=true; //標(biāo)識頂點(diǎn)已被訪問過for(inti=0;i<vertices_num;i++){if(adjMatrix[startIndex][i]==1&&!visited[i])iteratorDFT(i);}}0101101101001100v0

v1

v2

v3v0v1v2v3v0v1v2v30123算法：BFT輸入：頂點(diǎn)的編號v輸出：圖的廣度優(yōu)先遍歷序列1.隊(duì)列Q初始化;2.訪問頂點(diǎn)v;修改標(biāo)志visited[v]=1;頂點(diǎn)v入隊(duì)列Q;3.while(隊(duì)列Q非空)3.1i=隊(duì)列Q的隊(duì)頭元素出隊(duì);3.2j=頂點(diǎn)v的第一個(gè)鄰接點(diǎn);3.3while(j存在)3.3.1如果j未被訪問，則

訪問頂點(diǎn)j;修改標(biāo)志visited[j]=1;頂點(diǎn)j入隊(duì)列Q；3.3.2j=頂點(diǎn)i的下一個(gè)鄰接點(diǎn)；廣度遍歷如何在鄰接矩陣中求某頂點(diǎn)的鄰接點(diǎn)？廣度遍歷publicvoidBFT(intstartIndex){

visited=newboolean[vertices_num]; //初始化訪問標(biāo)志數(shù)組

//工作隊(duì)列初始化QueueInterface<Integer>queue=newCircularQueue<Integer>(vertic