數(shù)據(jù)結(jié)構(gòu)（Java語言） 課件 項目八 圖-某職院校園導航

項目八圖---某職院校園導航目錄項目八5123

典型工作任務8.1圖的項目需求分析典型工作任務8.2圖的數(shù)據(jù)結(jié)構(gòu)設(shè)計典型工作任務8.3圖軟件代碼設(shè)計典型工作任務8.4圖軟件測試執(zhí)行典型工作任務8.5圖軟件文檔編寫46典型工作任務8.6圖項目驗收交付知識目標掌握圖的常用概念和術(shù)語掌握圖鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)及算法掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法理解圖的連通理解關(guān)鍵路徑計算理解最短路徑問題的解決方法技能目標能進行需求功能分析會進行圖的算法分析及編程能用圖的知識編程解決問題能進行軟件測試及功能調(diào)整能編寫格式規(guī)范的軟件文檔思政目標了解自己的學校，熟悉校園路線樹立在學校里處處皆可學習、處處是學習之地的信念以最短路徑即節(jié)約的理念規(guī)劃出行學以致用養(yǎng)成嚴謹求實的學習習慣總體要求設(shè)計一個某職院導航程序，為來訪來校參觀者提供各種信息查詢服務，如圖8-1所示。圖8-1校園導航功能模塊圖典型工作任務8.1圖的項目需求分析（1）設(shè)計學校的校園平面圖。選取若干個有代表性的建筑物抽象成一個無向帶權(quán)圖（無向網(wǎng)），以圖中頂點表示校內(nèi)各建筑物，邊上的權(quán)值表示兩建筑物之間的距離。（2）存放建筑物編號、名稱、簡介等信息供用戶查詢。（3）為來訪者提供圖中任意建筑物相關(guān)信息的查詢。（4）為來訪客人提供圖中任意建筑物之間的問路查詢。（5）可以為校園平面圖增加或刪除建筑物或邊，修改兩個建筑物之間的距離（即邊上的權(quán)值）等。典型工作任務8.1圖的項目需求分析8.2.1圖的定義

在圖中的數(shù)據(jù)元素通常稱為頂點，圖（Graph）是由頂點集合（Vertex）及頂點之間的關(guān)系集合（Edge）組成的一種數(shù)據(jù)結(jié)構(gòu)。記為G=（V，E）。

無向圖有向圖G1=(V1,E1)，其中V1={A,B,C,D,E}，E1={(A,B),(A,C),(B,D),(C,E),(D,E)}G2=(V2,E2)，其中V2={A,B,C,D},E2={<A,B>,<A,D>,<B,D>,<D,C>,<C,A>}典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

1.無向圖和有向圖

在圖中，根據(jù)頂點之間的關(guān)系是否有方向性可將圖分為有向圖和無向圖。對于無向圖，頂點的關(guān)系為無向邊，用圓括號表示，如（x，y）。對于有向圖來說，頂點間的關(guān)系稱為有向邊，用尖括號表示，如<x，y>。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計沒有方向性，（x，y）和（y，x）是等價的，是同一條邊。表示從頂點x發(fā)向頂點y的邊，x為始點，y為終點。

2.完全圖、稀疏圖、稠密圖、網(wǎng)無向圖中邊的取值范圍：0≤e≤n(n-1)/2。（用n表示圖中頂點數(shù)目，用e

表示邊的數(shù)目。且不考慮頂點到其自身的邊。）完全圖：有

n(n-1)/2條邊的無向圖（即：每兩個頂點之間都存在著一條邊)稱為完全圖。

有向圖中弧的取值范圍：0≤e≤n(n-1)。（用n表示圖中頂點數(shù)目，用e表示弧的數(shù)目。且不考慮頂點到其自身的弧。）有向完全圖：有n(n-1)條弧的有向圖（即：每兩個頂點之間都存在著方向相反的兩條弧）稱為有向完全圖。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

2.完全圖、稀疏圖、稠密圖、網(wǎng)

無向圖中邊的取值范圍：0≤e≤n(n-1)/2。（用n表示圖中頂點數(shù)目，用e

表示邊的數(shù)目。且不考慮頂點到其自身的邊。）完全圖：有

n(n-1)/2條邊的無向圖（即：每兩個頂點之間都存在著一條邊)稱為完全圖。

有向圖中弧的取值范圍：0≤e≤n(n-1)。（用n表示圖中頂點數(shù)目，用e表示弧的數(shù)目。且不考慮頂點到其自身的弧。）有向完全圖：有n(n-1)條弧的有向圖（即：每兩個頂點之間都存在著方向相反的兩條弧）稱為有向完全圖。

無向完全圖有向完全圖網(wǎng)典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計稀疏圖：含有很少條邊或弧的圖。

稠密圖：含有很多條邊或弧的接近完全圖的圖。

權(quán)：與圖的邊或弧相關(guān)的數(shù)，權(quán)值可以是距離，時間，價格等。網(wǎng)：

帶權(quán)的圖。

子圖若有兩個圖G1和G2，其中G1=(V1，E1)，G2=(V2，E2)，且滿足如下條件：V2

V1,E2E1即V2為V1的子集，E2

為E1的子集，則稱圖G2為圖G1的子圖。

圖G圖G的兩個子圖

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計4.鄰接點和度對于無向圖，假若頂點v和頂點w之間存在一條邊，則稱頂點v和w互為鄰接點。和頂點v關(guān)聯(lián)的邊的數(shù)目定義為v的度。記為ID(V)。ID(C=)3TD(V)=ID(V)+OD(V)ID(A)=2ID(C)=2OD(C)=1TD(C)=3對于有向圖，由于弧有方向性，則有入度和出度之分。頂點的出度是以頂點v為弧尾的弧的數(shù)目，記為OD(V)。頂點的入度是以頂點v為弧頭的弧的數(shù)目，記為ID(V)。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計5．路徑、簡單路徑、簡單回路路徑長度：圖中兩個頂點之間的路徑為兩個頂點之間的頂點序列，路徑上所含邊的數(shù)目。簡單路徑：若序列中第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)，序列中頂點不重復出現(xiàn)的路徑。簡單回路：若序列中除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路。6.連通圖、連通分量、強連通圖、強連通分量連通：從頂點v

到

v′有路徑，則說

v

和

v′是連通的。連通圖：圖中任意兩個頂點都是連通的。

非連通圖：圖中并非任意兩個頂點都是連通的。

連通分量：無向圖的極大連通子圖。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

連通圖G1

非連通圖G2

圖G2的兩個連通分量典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計強連通圖：有向圖的任意兩個頂點之間都存在一條有向路徑。強連通分量：有向圖中極大的強連通子圖

強連通圖G1非強連通圖G2

圖G2的3個強連通分量典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計強連通圖：有向圖的任意兩個頂點之間都存在一條有向路徑。強連通分量：有向圖中極大的強連通子圖

強連通圖G1非強連通圖G2

圖G2的3個強連通分量典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計8.2.2圖的存儲結(jié)構(gòu)

1.鄰接矩陣用兩個數(shù)組來表示圖，一個一維數(shù)組，存儲圖中頂點的信息，一個數(shù)二維數(shù)組，即矩陣，存儲頂點之間相鄰的信息，也就是邊（或弧）的信息。設(shè)圖G=（V，E），有n個頂點，則其所對應的鄰接矩陣A是按如下定義的一個二維數(shù)組：

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計無向圖的鄰接矩陣一定是對稱矩陣第i行（或第i列）非零元素個數(shù)恰好是第i個頂點的度TD(Vi)

無向網(wǎng)

有向圖的鄰接矩陣不一定對稱第i行非零元素的個數(shù)恰好是第i個頂點的出度OD(Vi)，第i列非零元素的個數(shù)正好是第i個頂點的入度ID（Vi）。

有向網(wǎng)

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計若G是網(wǎng)，則鄰接矩陣可定義為：

無向網(wǎng)

有向網(wǎng)

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計使用Java語言編寫無向圖的鄰接矩陣的程序

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計importjava.io.*;publicclasstestwt{publicstaticvoidmain(Stringargs[])throwsIOException{int[][]data={{1,2},{2,1},{1,5},{5,1},//無向圖各邊的起點值及終點值{2,3},{3,2},{2,4},{4,2},{3,4},{4,3},{3,5},{5,3},{4,5},{5,4}};intarr[][]=newint[6][6];//聲明矩陣arrinti,j,k,tmpi,tmpj;for(i=0;i<6;i++)//將矩陣清零 for(j=0;j<6;j++) arr[i][j]=0;

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計for(i=0;i<14;i++)//讀取圖形數(shù)據(jù) for(j=0;j<6;j++)//填入arr矩陣 for(k=0;k<6;k++) { tmpi=data[i][0];//tmpi為起始頂點 tmpj=data[i][1];//tmpj為終止頂點 arr[tmpi][tmpj]=1;//有邊的點填入1 } System.out.print("無向圖鄰接矩陣：\n"); for(i=1;i<6;i++) { for(j=1;j<6;j++) System.out.print("["+arr[i][j]+"]");//打印矩陣內(nèi)容System.out.print("\n"); }}}使用Java語言編寫有向圖的鄰接矩陣的程序

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計importjava.io.*;publicclasstestyt{publicstaticvoidmain(Stringargs[])throwsIOException{ intarr[][]=newint[5][5];//聲明矩陣arr inti,j,tmpi,tmpj; int[][]data={{1,2},{2,1},{2,3},{2,4},{4,3}};//有向圖各邊的起點值及終點值 for(i=0;i<5;i++)//將矩陣清零 for(j=0;j<5;j++) arr[i][j]=0;

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計for(i=0;i<5;i++)//讀取圖中數(shù)據(jù) for(j=0;j<5;j++)//填入arr矩陣 { tmpi=data[i][0];//tmpi為起始頂點 tmpj=data[i][1];//tmpj為終止頂點 arr[tmpi][tmpj]=1;//有邊的點填入1 } System.out.print("有向圖鄰接矩陣：\n"); for(i=1;i<5;i++) { for(j=1;j<5;j++) System.out.print("["+arr[i][j]+"]");//打印矩陣內(nèi)容 System.out.print("\n"); }}}1.鄰接表無向圖的鄰接表具有如下性質(zhì)：(1)第i個鏈表中結(jié)點的數(shù)目為第i個頂點的度。(2)所有鏈表中結(jié)點的數(shù)目的一半為圖中邊的數(shù)目。(3)占用的存儲單元數(shù)目為n＋2e。（n為頂點數(shù)，e為邊數(shù)）

無向圖無向圖的鄰接表典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

有向圖有圖的鄰接表-出邊表有向圖的逆鄰接表-入邊表典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計使用Java語言編寫無向圖的鄰接表的程序

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計importjava.io.*;classNode//定義結(jié)點{ intx; Nodenext; publicNode(intx) { this.x=x; this.next=null; }}classGraphLink{ publicNodefirst; publicNodelast;

publicbooleanisEmpty()//判斷是否為空 { returnfirst==null; }

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計publicvoidprint()//打印輸出 { Nodecurrent=first; while(current!=null) { System.out.print("["+current.x+"]"); current=current.next; } System.out.println(); } publicvoidinsert(intx)//添加{NodenewNode=newNode(x); if(this.isEmpty()) { first=newNode; last=newNode; } else { last.next=newNode; last=newNode; } }}

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計publicclasstestljb{ publicstaticvoidmain(Stringargs[])throwsIOException{//圖形數(shù)組聲明 intData[][]={{1,2},{2,1},{1,4},{4,1},{1,5},{5,1},{2,3},{3,2},{3,4},{4,3},{4,5},{5,4}}; intDataNum; inti,j; System.out.println("圖形(a)的鄰接表內(nèi)容："); GraphLinkHead[]=newGraphLink[6]; for(i=1;i<6;i++) { Head[i]=newGraphLink(); System.out.print("頂點"+i+"=>"); for(j=0;j<12;j++) { if(Data[j][0]==i) { DataNum=Data[j][1];Head[i].insert(DataNum); } }Head[i].print(); }

} }8.2.3圖的深度優(yōu)先和廣度優(yōu)先遍歷算法從圖的任意指定頂點出發(fā)，依照某種規(guī)則去訪問圖中所有頂點，且每個頂點僅被訪問一次，這一過程叫做圖的遍歷。1.深度優(yōu)先遍歷（DFS）（1）首先訪問出發(fā)點V；（2）然后依次從V出發(fā)搜索V的每個鄰接點W，若W未曾訪問過，則以W為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索遍歷，直至圖中所有和源點V有路徑相通的頂點（也稱為從源點可達的頂點）均已被訪問為止；（3）若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

無向圖深度優(yōu)先遍歷過程從頂點V1出發(fā)深度優(yōu)先遍歷的序列為：V1、V2、V4、V8、V5、V3、V6、V7還可以是：V1、V2、V5、V8、V4、V3、V7、V6V1、V3、V7、V6、V2、V5、V8、V4

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計2.廣度優(yōu)先遍歷（DFS）

廣度優(yōu)先遍歷（BFS，Breadth-FirstSearch）類似于樹的按層次遍歷。設(shè)圖G初態(tài)是所有的頂點均未訪問過，在G中任選一頂點V為源點，則廣度優(yōu)先遍歷過程為：（1）首先訪問出發(fā)點V；(2)接著依次訪問頂點V的所有鄰接點V1，V2，…，Vt；(3)然后再依次訪問頂點V1，V2，……，Vt的所有鄰接點；(4)如此類推，直至圖中所有的頂點都被訪問到。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計

從頂點V出發(fā)廣度優(yōu)先遍歷的序列為：V，W1，W2，W8，W7，W3，W5，W6，W4V，W2，W8，W1，W3，W5，W7，W4，W6V，W1，W8，W2，W7，W3，W5，W6，W4典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計8.2.4圖形的最短路

有向圖形G=(V,

E),G中每一個邊都有一一個比例常數(shù)W（Weight）與之對應，如果想求G圖形中某一個頂點V0到其他頂點的最少w總和之值，這類問題就稱為最短路徑問題。

1.單點對全部頂點

頂點到多個頂點通常使用Dijkstra算法求得，Dijkstra算法如下:

假設(shè)S=(Vi|Vi∈V}，且Vi在已發(fā)現(xiàn)的最短路徑中，其中V0∈S是起點。

假設(shè)w?S，定義Dist(w)是從V0到w的最短路徑，這條路徑除了w外必屬于S，且有下列特性：①如果u是目前所找到最短路徑的下一個節(jié)點，則u必屬于V-S集合中最小花費成本的邊；②若u被選中，將u加入S集合中，則會產(chǎn)生目前由V0到u的最短路徑，對于w?S，DIST(w)被改變成DIST(w)被改變成<-

Min{DIST(w),DIST(u)+COST(u，w)}

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計8.2.4圖形的最短路首先由頂點5開始，找出頂點5到各點間最小的距離，到達不了以∞表示，步驟如下：步驟1：D[0]=∞,D[1]=12,D[2]=∞,D[3]=20,D[4]=14。在其中找出值最小的頂點，加入S集合中：D[1]。步驟2：D[0]=∞,D[1]=12,D[2]=18,D[3]=20,D[4]=14。D[4]最小，加入S集合中。步驟3：D[0]=26,D[1]=12,D[2]=18,D[3]=20,D[4]=14。D[2]最小，加入S集合中。步驟4：D[0]=26,D[1]=12,D[2]=18,D[3]=20,D[4]=14。D[3]最小，加入S集合中。步驟5：加入最后一個頂點即可得到下表8-1所示。

表8-1頂點5到其他頂點的距離

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計步驟S012345選擇15∞12∞20140125,1∞121820140435,1,426121820140245,1,4,226121820140355,1,4,2,3261218201400由頂點5到其他各頂點的最短距離如下：頂點5到頂點0:26頂點5到頂點1:12頂點5到頂點2:18頂點5到頂點3:20頂點5到頂點4:14

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計使用Java語言編寫Dijkstra算法的程序

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//圖形的相鄰矩陣類聲明classAdjacency{finalintINFINITE=99999;publicint[][]Graph_Matrix;//構(gòu)造函數(shù)publicAdjacency(int[][]Weight_Path,intnumber){inti,j;intStart_Point,End_Point;Graph_Matrix=newint[number][number];for(i=1;i<number;i++)for(j=1;j<number;j++)if(i!=j)Graph_Matrix[i][j]=INFINITE;elseGraph_Matrix[i][j]=0;for(i=0;i<Weight_Path.length;i++){Start_Point=Weight_Path[i][0];End_Point=Weight_Path[i][1];Graph_Matrix[Start_Point][End_Point]=Weight_Path[i][2];}}

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//顯示圖形的方法publicvoidprintGraph_Matrix(){for(inti=1;i<Graph_Matrix.length;i++){for(intj=1;j<Graph_Matrix[i].length;j++)if(Graph_Matrix[i][j]==INFINITE)System.out.print("*");else{if(Graph_Matrix[i][j]==0)System.out.print("");System.out.print(Graph_Matrix[i][j]+"");}System.out.println();}}}//Dijkstra算法類classDijkstraextendsAdjacency{privateint[]cost;privateint[]selected;

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//構(gòu)造函數(shù)publicDijkstra(int[][]Weight_Path,intnumber){super(Weight_Path,number);cost=newint[number];selected=newint[number];for(inti=1;i<number;i++)selected[i]=0;}//單點對全部頂點最短距離publicvoidshortestPath(intsource){intshortest_distance;intshortest_vertex=1;inti,j;for(i=1;i<Graph_Matrix.length;i++)cost[i]=Graph_Matrix[source][i];selected[source]=1;cost[source]=0;for(i=1;i<Graph_Matrix.length-1;i++){shortest_distance=INFINITE;for(j=1;j<Graph_Matrix.length;j++)if(shortest_distance>cost[j]&&selected[j]==0){shortest_vertex=j;shortest_distance=cost[j];}

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計selected[shortest_vertex]=1;for(j=1;j<Graph_Matrix.length;j++){if(selected[j]==0&&cost[shortest_vertex]+Graph_Matrix[shortest_vertex][j]<cost[j]){cost[j]=cost[shortest_vertex]+Graph_Matrix[shortest_vertex][j];}}}System.out.println("==================================");System.out.println("頂點1到各頂點最短距離的最終結(jié)果");System.out.println("==================================");for(j=1;j<Graph_Matrix.length;j++)System.out.println("頂點1到頂點"+j+"的最短距離="+cost[j]);}}

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//主類publicclasstestDijkstra{//主程序publicstaticvoidmain(String[]args){intWeight_Path[][]={{1,2,15},{2,3,22},{2,4,28},{3,5,68},{4,5,20},{4,6,92},{5,6,68}};Dijkstraobject=newDijkstra(Weight_Path,7);System.out.println("==================================");System.out.println("此范例圖形的相鄰矩陣如下:");System.out.println("==================================");object.printGraph_Matrix();object.shortestPath(1);}}2.頂點兩兩之間的最短距離由于Dijkstra的方法只能求出某一點到其他頂點的最短距離，如果要求出圖形中任兩點甚至所有頂點間最短的距離，就必須使用Floyd算法。Floyd算法定義：1.Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k]+Ak-1[k][j]},k≥1k表示經(jīng)過的頂點，Ak[i][j]為從頂點i到j的經(jīng)過k頂點的最短路徑。2.A0[i][j]=COST[i][j](即A0便等于COST)3.A0為頂點i到j之間的直線距離。4.An[I,j]代表i到j的最短距離，即An便是我們所要求的最短路徑成本矩陣。這樣看起來似乎覺得Floyd算法相當復雜，我們將以實例說明它的算法，例如試以Floyd算法求得以下圖各頂點之間的最短距離。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計使用Java語言編寫Floyd算法。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//圖形的相鄰矩陣類聲明

classAdjacency{finalintINFINITE=99999;publicint[][]Graph_Matrix;//構(gòu)造函數(shù)publicAdjacency(int[][]Weight_Path,intnumber){inti,j;intStart_Point,End_Point;Graph_Matrix=newint[number][number];for(i=1;i<number;i++)for(j=1;j<number;j++)if(i!=j)Graph_Matrix[i][j]=INFINITE;elseGraph_Matrix[i][j]=0;for(i=0;i<Weight_Path.length;i++){Start_Point=Weight_Path[i][0];End_Point=Weight_Path[i][1];Graph_Matrix[Start_Point][End_Point]=Weight_Path[i][2];}}使用Java語言編寫Floyd算法。

典型工作任務8.2圖數(shù)據(jù)結(jié)構(gòu)設(shè)計//顯示圖形的方法publicvoidprintGraph_Matrix(){for(inti=1;i<Graph_Matrix.length;i++){for(intj=1;j<Graph_Matrix[i].length;j++)if(Graph_Matrix[i][j]==INFINITE)System.out.print("*");else{if(Graph_Matrix[i][j]==0)System.out.print("");System.out.print(Graph_Matrix[i][j]+"");}System.out.println();}}}//Floyd算法類classFloydextendsAdjacency{privateint[][]cost;privateintcapcity;