數(shù)據(jù)結構(Java語言描述)：第6章 圖(Java版)

第六章圖教學內容6.1圖的概述6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑教學重點與難點重點：圖的概念；圖的存儲結構；圖的遍歷；最小生成樹；最短路徑；拓撲排序；關鍵路徑。難點：最小生成樹；最短路徑；關鍵路徑；圖的應用學習指南

圖是較線性表和樹更為復雜的數(shù)據(jù)結構，因此和線性表、樹不同，雖然在遍歷圖的同時可以對頂點或弧進行各種操作，但更多圖的應用問題如求最小生成樹等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們在計算機中的具體實現(xiàn)。這些算法乍一看都比較難，應多對照具體圖例的存儲結構進行學習。而圖遍歷的兩種搜索路徑和樹遍歷的兩種搜索路徑極為相似，應將兩者的算法對照學習以便提高學習的效益。教學內容6.1圖的概述6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑6.1.1圖的基本概念----圖由頂點（Vertex）集和邊(Edge）集組成，記為G＝（V，E）,其中V

是有窮非空集合，稱為頂點集，v

∈V稱為頂點。E

是有窮集合，稱為邊集，e∈E稱為邊.EACBD例如:G=(V,E)其中V={A,B,C,D,E}E={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}零圖：E是空集，此時圖只有頂點沒有邊6.1.1圖的基本概念---無向邊、無向圖無向邊e=(u,v)=(v,u),其中u,v

∈V,邊(u,v)與邊(v,u)是相同的。無向圖（UndirectedGraph)全部由無向邊構成的圖01342無向圖G1

例G1＝(V1,E1)V1={0,1,2,3,4}E1={(0,1),(1,2),(1,4),(2,3),(3,4)}6.1.1圖的基本概念---有向邊、有向圖例：G2＝(V2,E2)V2={v0,v1,v2,v3,v4}E2={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>,<v3,v4>}v0v1v2v3v4有向圖G2有向邊e=<u,v>,其中u,v

∈V，簡稱為弧（Arc）其中u為始點（InitialNode）或弧尾（Tail），v為終點（TerminalNode)或弧頭（Head）邊<u,v>與邊<v,u>是不同的有向圖（DirectedGraph)全部由有向邊構成的圖6.1.1圖的基本概念---權、網(wǎng)ABEFDC2102755無向網(wǎng)G3ABCD14764有向網(wǎng)G46.1.1圖的基本概念---權、網(wǎng)權（Weight）：在一個圖中，每條邊可以標上具有某種含義的數(shù)值，此數(shù)值稱為該邊上的權通常權是一個非負實數(shù)權可以表示從一個頂點到另一個頂點的距離、時間或代價等含義網(wǎng)（Network)邊上標識權的圖稱為網(wǎng)6.1.1圖的基本概念---完全圖完全無向圖中的每兩個頂點之間都存在著一條邊；完全有向圖中的每兩個頂點之間都存在著方向相反的兩條邊0132完全無向圖ACB完全有向圖

假設圖中有

n

個頂點，e

條邊，則完全無向圖含有

條邊；完全有向圖含有

條弧e=n(n-1)/2？e=n(n-1)？6.1.1圖的基本概念---稀疏圖、稠密圖

若邊或弧的個數(shù)

e<nlogn，則稱作稀疏圖，否則稱作稠密圖。6.1.1圖的基本概念---子圖子圖（Subgraph）設有兩個圖G＝(V,E)和G’＝(V’,E’)，若V’是V

的子集，即V

’?V

，并且E’是E

的子集，即E’?E

，則稱G’為G的子圖，記為G’?G。生成子圖（SpanningSubgraph)若G’為G的子圖，并且V

’＝

V

，則稱G’為G的生成子圖，即包含原圖中所有頂點的子圖。6.1.1圖的基本概念---子圖01342無向圖G100101342無向圖G1的生成子圖01342無向圖G1的生成子圖6.1.1圖的基本概念---鄰接點鄰接點（Adjacent）在一個無向圖中，若存在一條邊(u,v)，則稱頂點u與v互為鄰接點。邊(u,v)是頂點u和v關聯(lián)的邊，頂點u和v是邊(u,v)關聯(lián)的頂點。以頂點1為端點的3條邊是(0,1),(1,2),(1,4),頂點1的3個鄰接點分別為0,2,4；01342無向圖G16.1.1圖的基本概念---鄰接點鄰接點（Adjacent）在一個有向圖中,若存在一條弧<u,v>，則稱頂點u鄰接到v,頂點v鄰接自u?；?lt;u,v>和頂點u、v關聯(lián)。頂點v0有2條出邊<v0,v1>，<v0,v2>，1條入邊<v3,v0>,頂點v0鄰接到v1和v2，頂點v0鄰接自v3.v0v1v2v3v4有向圖G26.1.1圖的基本概念---頂點的度頂點的度（Degree）頂點的度是圖中與該頂點相關聯(lián)邊的數(shù)目，記為D(v)。若一個圖有n個頂點和e條邊，則該圖所有頂點的度之和與邊數(shù)滿足如下關系6.1.1圖的基本概念---無向圖頂點的度無向圖頂點的度(degree)定義為以該頂點為一個端點的邊的數(shù)目，即該頂點的邊的數(shù)目，記為D(v)。e=5；n=5D(0)=1;

D(1)=3;D(2)=2;

D(3)=2;

D(4)=2;01342無向圖G1=(1+3+2+2+2)/2=10/2=5=e6.1.1圖的基本概念---有向圖頂點的度有向圖頂點的度頂點v的入邊數(shù)目是該頂點的入度(InDegree)，記為ID(v)；頂點v的出邊數(shù)目是該頂點的出度(OutDegree)，記為OD(v)；頂點v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)6.1.1圖的基本概念---有向圖頂點的度v0v1v2v3v4有向圖G2e=5;n=5ID(v0)=1;OD(v0)=2;

D(v0)=3ID(v1)=1;OD(v1)=0;

D(v1)=1ID(v2)=1;OD(v2)=1;

D(v2)=2ID(v3)=1;OD(v3)=2;

D(v3)=3ID(v4)=1;OD(v4)=0;

D(v4)=1=(3+1+2+3+1)/2=10/2=5=e6.1.1圖的基本概念---路徑、回路路徑(Path)在一個圖中，路徑是從頂點u到頂點v所經(jīng)過的頂點序列，即(u=vi0,vi1,…,vim=v)。路徑長度是指該路徑上邊的數(shù)目?；芈罚?/p>

第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)。ABECF6.1.1圖的基本概念---路徑、回路初等路徑序列中頂點不重復出現(xiàn)的路徑稱為初等路徑初等回路

除了第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路ABECF6.1.1圖的基本概念---路徑、回路v0v1v2v3有向圖G5路徑(v0,v2,v3,

v0)是初等回路其路徑長度為3從頂點v0到頂點v1的一條路徑

(v0,v2,v3,

v1)是初等路徑，其路徑長度為3從頂點v0到頂點v1的另一條路徑(v0,v2,v3,

v0,

v1)不是初等路徑其路徑長度為46.1.1圖的基本概念---網(wǎng)中的路徑長度網(wǎng)中的路徑長度在網(wǎng)中，從始點到終點的路徑上各邊的權值之和，稱為路徑長度ABEFDC2102755無向圖G3從頂點A到頂點E的一條路徑：(A,B,D,E

)路徑長度為10+7+2=196.1.1圖的基本概念---連通圖和連通分量

若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEABLCMHEFKGIDJ連通圖非連通圖6.1.1圖的基本概念--強連通圖和強連通分量

若有向圖中任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。ABECF

否則，其各個極大強連通子圖稱作它的強連通分量。ABCF強連通圖非強連通圖

6.1.1圖的基本概念--生成樹

BACDFE3個連通分量6.1.1圖的基本概念---生成森林ACDEFHKBGIMLJ非邊通圖ACDEFHKBGIMLJ

對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。6.1.2圖的抽象數(shù)據(jù)類型描述1.基本操作（1）

1）創(chuàng)建一個圖

createGraph()

2）返回圖中的頂點數(shù)

getVexNum()

3）返回圖中的邊數(shù)

getArcNum()

4）給定頂點的位置v，返回其對應的頂點值，其中：0≤v<vexNum（vexNum為頂點數(shù)）

getVex(v)

5）給定頂點的值vex，返回其在圖中的位置，如果圖中不包含此頂點，則返回-1 locateVex(vex)6.1.2圖的抽象數(shù)據(jù)類型描述1.基本操作（2）

6）返回v的第一個鄰接點，若v沒有鄰接點，則返回-1，其中：0≤v<vexNum firstAdjVex(v)

7）返回v相對于w的下一個鄰接點，若w是v的最后一個鄰接點，則返回-1，

其中：0≤v,w<vexNum nextAdjVex(v,w)6.1.2圖的抽象數(shù)據(jù)類型描述2.線性表抽象數(shù)據(jù)類型的Java接口描述publicinterfaceIGraph{voidcreateGraph();intgetVexNum();intgetArcNum();ObjectgetVex(intv)intlocateVex(Objectvex)intfirstAdjVex(intv)intnextAdjVex(intv,intw)}教學內容6.1圖的概述6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑6.2圖的存儲結構圖的類型主要有四種：無向圖、有向圖、無向網(wǎng)和有向網(wǎng)?？梢杂妹杜e表示為publicenumGraphKind{UDG,//無向圖（UnDirectedGraph)DG, //有向圖（DirectedGraph)UDN,//無向網(wǎng)（UnDirectedNetwork)DN //有向網(wǎng)（DirectedNetwork)}一、圖的鄰接陣存儲表示二、圖的鄰接表存儲表示*三、有向圖的十字鏈表存儲表示*四、無向圖的鄰接多重表存儲表示6.2圖的存儲結構6.2.1鄰接陣

6.2.1鄰接矩陣01342

6.2.1鄰接矩陣v0v1v2v3v4

有向圖的鄰接矩陣不一定為對稱矩陣.每一行中“1”的個數(shù)為該頂點的出度；每一列中"1"的個數(shù)為該頂點的入度。6.2.1鄰接矩陣ABEFDC2102755網(wǎng)的鄰接矩陣(AdjacencyMatrix)6.2.1鄰接矩陣圖的鄰接矩陣類的描述：publicclassMGraphimplementsIGraph{ publicfinalstaticintINFINITY= Integer.MAX_VALUE;

//圖的種類標志 privateGraphKindkind; //圖的當前頂點數(shù)和邊數(shù) privateintvexNum,arcNum;

//頂點 privateObject[]vexs;

//鄰接矩陣 privateint[][]arcs;

}……6.2.1鄰接矩陣publicclassMGraphimplementsIgraph{

…… publicMGraph(){ this(null,0,0,null,null); } publicMGraph(GraphKindkind,intvexNum,intarcNum,Object[]vexs,int[][]arcs){ this.kind=kind; this.vexNum=vexNum; this.arcNum=arcNum; this.vexs=vexs; this.arcs=arcs; }

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

//創(chuàng)建圖 publicvoidcreateGraph()

{……}

//創(chuàng)建無向圖 privatevoidcreateUDG(){……}

//創(chuàng)建有向圖 privatevoidcreateDG(){……}

//創(chuàng)建無向網(wǎng) privatevoidcreateUDN()

{……}

//創(chuàng)建有向網(wǎng) privatevoidcreateDN(){……}

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

//返回頂點數(shù) publicintgetVexNum(){ returnvexNum; }

//返回邊數(shù) publicintgetArcNum(){ returnarcNum; }

//給定頂點的值vex，返回其在圖中的位置，如果圖中不包含此頂點，則返回-1 publicintlocateVex(Objectvex) {……}

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

//返回v表示結點的值，0<=v<vexNumpublicObjectgetVex(intv)throwsException{ if(v<0&&v>=vexNum) thrownewException("第"+v+"個頂點不存在!"); returnvexs[v];}publicGraphKindgetKind(){returnkind;}publicint[][]getArcs(){returnarcs;}publicObject[]getVexs(){returnvexs;}

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

//返回v的第一個鄰接點，若v沒有鄰接點則返回-1，0≤v<vexnum publicintfirstAdjVex(intv)throwsException {……}

//返回v相對于w的下一個鄰接點，若w是v的最后一個鄰接點，則返回-1，其中0≤v,w<vexNum publicintnextAdjVex(intv,intw)throwsException {……}}6.2.1鄰接矩陣無向網(wǎng)的創(chuàng)建算法createUDN()

操作要求：

輸入的圖的頂點、邊及權值構造無向網(wǎng)問題：

鄰接矩陣大小？

如何確定每一條邊？6.2.1鄰接矩陣無向網(wǎng)的創(chuàng)建算法createUDN()

算法處理步驟：

1、輸入頂點數(shù)和邊數(shù) 2、根據(jù)圖的頂點數(shù)構造鄰接矩陣 3、根據(jù)圖的邊數(shù)，確定輸入邊的數(shù)目 4、根據(jù)輸入每條邊的頂點在鄰接矩陣相應位置保存每條邊的權值6.2.1鄰接矩陣【算法6.2】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){

//初始化變量

Scannersc=newScanner(System.in); System.out.println("請分別輸入圖的頂點數(shù)、圖的邊數(shù):");

vexNum=sc.nextInt();

arcNum=sc.nextInt();

……}時間復雜度為O(1)//頂點數(shù)n//邊數(shù)e6.2.1鄰接矩陣【算法6.2】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){

……

//輸入圖中各頂點 vexs=newObject[vexNum]; System.out.println("請分別輸入圖的各個頂點:"); for(intv=0;v<vexNum;v++)//構造頂點向量

vexs[v]=sc.next(); ……}時間復雜度為O(n)6.2.1鄰接矩陣【算法6.2】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){ ……

//定義鄰接矩陣

arcs=newint[vexNum][vexNum];

//初始化鄰接矩陣 for(intv=0;v<vexNum;v++) for(intu=0;u<vexNum;u++) arcs[v][u]=INFINITY;//初始為無窮大 ……}時間復雜度為O(n2)6.2.1鄰接矩陣【算法6.2】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){ ……//輸入邊信息System.out.println("請輸入各個邊的兩個頂點及其權值:");for(intk=0;k<arcNum;k++){ intv=locateVex(sc.next());//頂點 intu=locateVex(sc.next());//頂點

arcs[v][u]=arcs[u][v]=sc.nextInt();//權值 }}//算法6.2結束

6.2.1鄰接矩陣

6.2.1鄰接矩陣頂點定位算法locateVex(vex)操作要求：

根據(jù)頂點信息vex，取得其在頂點數(shù)組中的位置，若圖中無此頂點，則返回-1問題：

如何確定查找？解決：

遍歷頂點數(shù)組即可6.2.1鄰接矩陣頂點定位算法locateVex(vex)操作要求：

根據(jù)頂點信息vex，取得其在頂點數(shù)組中的位置，若圖中無此頂點，則返回-1問題：

如何確定查找？解決：

遍歷頂點數(shù)組即可6.2.1鄰接矩陣【算法6.4】頂點定位算法publicintlocateVex(Objectvex){ //遍歷頂點數(shù)組 for(intv=0;v<vexNum;v++) if(vexs[v].equals(vex)) returnv; return-1;}//算法6.4結束時間復雜度為O(n)//找到，返回位置//未找到，返回-16.2.1鄰接矩陣查找第一個鄰接點的算法firstAdjVex(v)

操作要求：

返回v的第一個鄰接點，若v沒有鄰接點則返回-1，0≤v<vexnum問題：

如何確定鄰接點？6.2.1鄰接矩陣

6.2.1鄰接矩陣【算法6.5】查找第一個鄰接點的算法publicintfirstAdjVex(intv)throwsException{if(v<0&&v>=vexNum) thrownewException("第"+v+"個頂點不存在!");//遍歷鄰接矩陣第v行for(intj=0;j<vexNum;j++) if(arcs[v][j]!=0&&arcs[v][j]<INFINITY) returnj; return-1;}//算法6.5結束

6.2.1鄰接矩陣查找下一個鄰接點的算法nextAdjVex(v,w)

操作要求：

返回v相對于w的下一個鄰接點，若w是v的最后一個鄰接點，則返回-1，其中0≤v,w<vexNum問題：

如何確定鄰接點？6.2.1鄰接矩陣查找下一個鄰接點的算法nextAdjVex(v,w)

算法處理步驟： 1、

判斷插入位置是否正確 2、從鄰接矩陣第v行第W+1列開始遍歷，查找是否有非0、非無窮大值元素6.2.1鄰接矩陣【算法6.6】查找下一個鄰接點的算法publicintnextAdjVex(intv,intw)throwsException{ if(v<0&&v>=vexNum) thrownewException("第"+v+"個頂點不存在!"); //從w+1開始遍歷第v行 for(intj=w+1;j<vexNum;j++) if(arcs[v][j]!=0&&arcs[v][j]<INFINITY) returnj; return-1;}//算法6.6結束時間復雜度為O(n)6.2.2鄰接表

6.2.2鄰接表-無向圖無向圖對應的鄰接表某行上邊結點個數(shù)為該行表示結點的度0A141B0452C353D254E015F123BACDFE196.2.2鄰接表-無向網(wǎng)ABEFDC2927550A1B2C3D4E5F2732290232554237552545如果無向圖（網(wǎng)）中有e條邊，則對應鄰接表有2e個邊結點6.2.2鄰接表datafirstArcadjVexvaluenextArc頂點結點邊（或?。┙Y點頂點信息第一個鄰結點與頂點相鄰接的點在圖中的位置與邊相關的信息，一般為權值（若不帶權圖，可以沒有此項）指向頂點的下一個邊結點6.2.2鄰接表-有向圖

鄰接表：邊表表示所有以vi為始點的弧。012341423012ABCDEABECD在有向圖的鄰接表中不易找到指向該頂點的弧。有向圖對應的鄰接表某行上邊結點個數(shù)為該結點的出度6.2.2鄰接表-有向圖

逆鄰接表：邊表表示所有以vi為終點的弧。有向圖對應的逆鄰接表某行上邊結點個數(shù)為該結點的入度。ABECDABCDE3034200123416.2.2鄰接表-有向網(wǎng)ABCD147640A1B2C3D0624371124如果有向圖（網(wǎng)）中有e條邊，則對應鄰接表有e個邊結點6.2.2鄰接表鄰接表與鄰接矩陣比較：對于稀疏圖，鄰接表比鄰接矩陣節(jié)省存儲空間鄰接表上很容易找到任意一個頂點的鄰接點，但若要判定任意兩個鄰接點是否有邊相連，則需遍歷單鏈表，不如鄰接矩陣方便例1：給出下圖的鄰接表和鄰接矩陣：v4v1v2v3v501234134412

v1v2v3v4v5021302例2：給出以下有向圖的

1）鄰接矩陣

2）每個頂點的入/出度；

3）鄰接表及逆鄰接表

4）強連通分量2156436.2.2鄰接表-頂點結點類publicclassVNode{

privateObjectdata;//頂點信息

privateArcNodefirstArc;

//指向第一條依附于該頂點的弧publicVNode(){ this(null,null); } publicVNode(Objectdata){ this(data,null); } publicVNode(Objectdata,ArcNodefirstArc){ this.data=data; this.firstArc=firstArc; } ……}頂點結點datafirstArc6.2.2鄰接表-邊結點類圖的鄰接表存儲表示中的邊(或弧)結點類描述：publicclassArcNode{

//該弧所指向的頂點位置

privateintadjVex;

//邊(或弧)的權值 privateintvalue; //指向下一條弧 privateArcNodenextArc; ……}邊（或?。┙Y點adjVexvaluenextArc6.2.2鄰接表-邊結點類publicclassArcNode{

…… publicArcNode(){ this(-1,0,null); } publicArcNode(intadjVex){ this(adjVex,0,null); } publicArcNode(intadjVex,intvalue){ this(adjVex,value,null); }

……}6.2.2鄰接表-邊結點類publicclassArcNode{

…… publicArcNode(intadjVex,intvalue, ArcNodenextArc){ this.value=value; this.adjVex=adjVex; this.nextArc=nextArc; }

……}6.2.2鄰接表頂點定位算法locateVex(vex)操作要求：

給定頂點的值vex，返回其在圖中的位置，若圖中不包含此頂點，則返回-1問題：

如何確定查找？6.2.2鄰接表頂點定位算法locateVex(vex)算法處理步驟：

遍歷頂點數(shù)組即可

6.2.2鄰接表頂點定位算法publicintlocateVex(Objectvex){

//vexNum為頂點個數(shù)n

//vexs為存放圖中各頂點的數(shù)組 for(intv=0;v<vexNum;v++) if(vexs[v].getData().equals(vex)) returnv; return-1;}時間復雜度為O(n)6.2.2鄰接表無向網(wǎng)的創(chuàng)建算法createUDN()

操作要求：

輸入的圖的頂點、邊及權值構造無向網(wǎng)問題：

鄰接表大?。?/p>

如何生成每一條邊？6.2.2鄰接表無向網(wǎng)的創(chuàng)建算法createUDN()

算法處理步驟： 1、輸入頂點數(shù)和邊數(shù) 2、構造頂點向量 3、根據(jù)圖的邊數(shù)，確定輸入邊的數(shù)目 4、根據(jù)輸入的每條邊生成邊結點，并在相應位置插入邊結點

6.2.2鄰接表【算法6.7】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){

//初始化變量

Scannersc=newScanner(System.in); System.out.println("請分別輸入圖的頂點數(shù)、圖的邊數(shù):"); vexNum=sc.nextInt();//頂點數(shù)n arcNum=sc.nextInt();//邊數(shù)e

……}時間復雜度為O(1)6.2.2鄰接表【算法6.7】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){

……

//輸入圖中各頂點 vexs=newVNode[vexNum]; System.out.println("請分別輸入圖的各頂點:");

//構造頂點向量 for(intv=0;v<vexNum;v++) vexs[v]=newVNode(sc.next());

……}時間復雜度為O(n)6.2.2鄰接表【算法6.7】無向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){

……

//輸入圖中各邊信息 System.out.println("請輸入各邊的頂點及其權值:"); for(intk=0;k<arcNum;k++){

intv=locateVex(sc.next());//弧尾 intu=locateVex(sc.next());//弧頭 intvalue=sc.nextInt(); addArc(v,u,value);//加入邊 addArc(u,v,value);//加入邊 }}時間復雜度為O(n*e)6.2.2鄰接表【算法6.7】無向網(wǎng)的創(chuàng)建算法性能分析初始化變量輸入圖中各頂點輸入圖中各邊信息總的時間復雜度是

O(n*e+n+1)=O(n*e)O(1)O(n)O(n*e)6.2.2鄰接表在圖中插入邊(或弧)(v,u)結點的算法

addArc(v,u,value)操作要求：

用鄰接表存儲圖時，將權值為value的邊（或?。?/p>

(v,u)插入圖中問題：

如何確定插入位置？6.2.2鄰接表在圖中插入邊(或弧)(v,u)結點的算法

addArc(v,u,value)算法處理步驟： 1、u為邊的終點，生成邊結點 2、v為邊的起點，將邊結點插入頂點v的鏈表表頭

6.2.2鄰接表【算法6.8】在圖中插入邊(或弧)(v,u)結點的算法publicvoidaddArc(intv,intu,intvalue){

//u為邊的終點，生成邊結點 ArcNodearc=newArcNode(u,value);

//v為邊的起點，將邊結點插入頂點v的鏈表表頭

//取表頭 arc.setNextArc(vexs[v].getFirstArc());

//生成新表頭 vexs[v].setFirstArc(arc);}//算法6.8結束時間復雜度為O(1)6.2.2鄰接表查找下一個鄰接點的算法nextAdjVex(v,w)

操作要求：

返回v相對于w的下一個鄰接點，若w是v的最后一個鄰接點，則返回-1，其中0≤v,w<vexNum問題：

如何確定鄰接點？6.2.2鄰接表查找下一個鄰接點的算法nextAdjVex(v,w)

算法處理步驟： 1、

判斷插入位置是否正確 2、取結點v 3、在鄰接表中查找結點w

4、取w的下一結點

6.2.2鄰接表【算法6.6】查找下一個鄰接點的算法publicintnextAdjVex(intv,intw)throwsException{if(v<0&&v>=vexNum) thrownewException("第"+v+"個頂點不存在!");

//取結點vVNodevex=vexs[v];

//用于取結點v的鄰接點ArcNodearcvw=null;

……}時間復雜度為O(n)6.2.2鄰接表【算法6.6】查找下一個鄰接點的算法publicintnextAdjVex(intv,intw)throwsException{ ……for(ArcNodearc=vex.getFirstArc();arc!=null; arc=arc.getNextArc()) if(arc.getAdjVex()==w){

//取出結點w arcvw=arc; break;}

……}6.2.2鄰接表【算法6.6】查找下一個鄰接點的算法publicintnextAdjVex(intv,intw)throwsException{

…… if(arcvw!=null&&arcvw.getNextArc()!=null)

//取w的下一結點 returnarcvw.getNextArc().getAdjVex(); else return-1;}//算法6.9結束教學內容6.1圖的概述6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑圖的遍歷（TraversingGraph）從圖中的某個頂點出發(fā)，對圖中的所有頂點訪問且僅訪問一次的過程。廣度優(yōu)先搜索（BreadthFirstSearch，BFS）深度優(yōu)先搜索（DepthFirstSearch，DFS）6.3圖的遍歷6.3.1廣度優(yōu)先搜索（BFS）從圖中的某個頂點v開始，先訪問該頂點再依次訪問該頂點的每一個未被訪問過的鄰接點w1、w2、…然后按此順序訪問頂點w1、w2、…的各個還未被訪問過的鄰接點。重復上述過程，直到圖中的所有頂點都被訪問過為止。圖的廣度優(yōu)先搜索遍歷類似于樹的層次遍歷過程v1v0v6v3v2v4v5v7訪問次序：v06.3.1廣度優(yōu)先搜索（BFS）v1v2v3v4v5v6v7訪問次序：6.3.1廣度優(yōu)先搜索（BFS）Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4vw1w2w8w7s3w5w6w4例如：6.3.1廣度優(yōu)先搜索（BFS）圖的廣度優(yōu)先搜索算法BFSTraverse(G)操作要求：

對圖G做廣度優(yōu)先遍歷問題： 1、如何記錄結點已經(jīng)被訪問過 2、如何體現(xiàn)廣度優(yōu)先的訪問次序 3、非連通圖如何處理6.3.1廣度優(yōu)先搜索（BFS）v1v0v6v3v2v4v5v7V0V1V2V3V4V5V6V7輔助隊列：說明：紅色部分為隊列出隊元素6.3.1廣度優(yōu)先搜索（BFS）圖的廣度優(yōu)先搜索算法BFSTraverse(G)解決方案：1、遍歷過程實際上是尋找鄰接點的過程2、使用隊列操作體現(xiàn)結點訪問的先后次序每個結點一旦被訪問就插入隊列中

每次從隊頭取出結點，訪問它所有未被訪問過的鄰接點3、使用visited數(shù)組，標記結點是否被訪問過6.3.1廣度優(yōu)先搜索（BFS）圖的廣度優(yōu)先搜索算法BFSTraverse(G)算法處理步驟： 1、

初始化visited數(shù)組 2、從某個未被訪問過頂點出發(fā)廣度搜索所有未被訪問的結點BFS(G,v)

3、如果圖為非連通圖，則從某個頂點出發(fā)并不能訪問圖中所有結點而只能訪問圖中一連通分量，此時需從圖選擇另一未被訪問過的結點，繼續(xù)廣度搜索6.3.1廣度優(yōu)先搜索（BFS）//定義訪問標志數(shù)組privatestaticboolean[]visited;

//訪問標志數(shù)組初始化visited=newboolean[G.getVexNum()];for(intv=0;v<G.getVexNum();v++) visited[v]=false;6.3.1廣度優(yōu)先搜索（BFS）//訪問圖中每個連通分支for(intv=0;v<G.getVexNum();v++)

//如果結點v尚未訪問，則從V出發(fā)廣度搜索所有可訪問結點（連通分量） if(!visited[v])

BFS(G,v);這里的for循環(huán)確保當圖不是連通圖時，每個連通分量都可以被訪問到6.3.1廣度優(yōu)先搜索（BFS）從某個頂點出發(fā)廣度優(yōu)先搜索算法 BFS(G,v)算法處理步驟： 1、結點被訪問，相應visited數(shù)組中要做標記 2、定義一個輔助隊列，記錄結點訪問順序

3、每個結點一旦被訪問就插入隊列中

4、當沒有可以訪問的鄰接點時，從隊頭取出一個結點，訪問它所有未被訪問過的鄰接點，重復上面的過程，直到隊列為空6.3.1廣度優(yōu)先搜索（BFS）準備工作：//標記起始結點v被訪問visited[v]=true;//定義輔助隊列QLinkQueueQ=newLinkQueue();//v入隊列Q.offer(v);6.3.1廣度優(yōu)先搜索（BFS）//隊列不空，取出隊頭結點u，訪問u所有鄰結點while(!Q.isEmpty()){intu=(Integer)Q.poll();

//取u的所有鄰接頂點wfor(intw=G.firstAdjVex(u);w>=0; w=G.nextAdjVex(u,w))if(!visited[w]) { visited[w]=true;

//標記w被訪問 System.out.print(G.getVex(w).toString()+""); Q.offer(w); //w入隊 }}//取隊頭元素u//判斷是否被訪問過6.3.1廣度優(yōu)先搜索（BFS）privatestaticvoidBFS(IGraphG,intv)throwsException{ visited[v]=true; System.out.print(G.getVex(v).toString()+""); LinkQueueQ=newLinkQueue();//輔助隊列Q Q.offer(v);//v入隊列

while(!Q.isEmpty()){ intu=(Integer)Q.poll();//隊頭元素出隊列并賦值給u

for(intw=G.firstAdjVex(u);w>=0;w=G.nextAdjVex(u,w))

if(!visited[w]){//w為u的尚未訪問的鄰接頂點

visited[w]=true;

System.out.print(G.getVex(w).toString()+""); Q.offer(w);

}

}}//算法6.10結束6.3.1廣度優(yōu)先搜索（BFS）【算法6.10】圖的廣度優(yōu)先搜索算法privatestaticboolean[]visited;//定義標志數(shù)組publicstaticvoidBFSTraverse(IGraphG)throwsException{ //標志數(shù)組初始化 visited=newboolean[G.getVexNum()];

for(intv=0;v<G.getVexNum();v++) visited[v]=false; for(intv=0;v<G.getVexNum();v++) if(!visited[v])//v尚未訪問

BFS(G,v);}6.3.1廣度優(yōu)先搜索（BFS）【算法6.10】圖的廣度優(yōu)先搜索算法性能分析假設圖有n個頂點和e條邊時間復雜度存儲結構采用鄰接矩陣時，需要掃描鄰接矩陣中的每一個頂點，其時間復雜度為O(n2)；當圖的存儲結構采用鄰接表時，需要掃描鄰接表中的每一個單鏈表，其時間復雜度為O(e)6.3.1廣度優(yōu)先搜索（BFS）【算法6.10】圖的廣度優(yōu)先搜索算法性能分析空間復雜度需要使用隊列，依次記住被訪問過的頂點，每一個頂點最多入隊、出隊一次，空間復雜度為O(n)增設一個輔助數(shù)組visted，空間復雜度為O(n)6.3.2深度優(yōu)先搜索（DFS）連通圖的深度優(yōu)先搜索遍歷

從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。W1、W2和W3

均為V的鄰接點，SG1、SG2和SG3分別為含頂點W1、W2和W3

的子圖。訪問頂點V：for(W1、W2、W3)

若該鄰接點Wi未被訪問，

則從它出發(fā)進行深度優(yōu)先搜索遍歷。Vw1SG1SG2SG3w2w3w26.3.2深度優(yōu)先搜索（DFS）從上頁的圖解可見:從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點設立一個

“訪問標志visited[i]”。2.如何判別V的鄰接點是否被訪問？6.3.2深度優(yōu)先搜索（DFS）6.3.2深度優(yōu)先搜索（DFS）v1v0v6v3v2v4v5從頂點V0開始遍歷V0V1V4V5V6V2V3V0V2V6V1V5V4V3結束結束或：注意：對于一個圖，從某個頂點出發(fā)可得到多種搜索遍歷結果，但如果是在特定存儲結構上，按照某種特定搜索算法只能有一種唯一的遍歷結果。解決的辦法是：訪問完一個連通分量后，則另選圖中一個未曾被訪問的頂點作起始點繼續(xù)進行深度優(yōu)先搜索遍歷。思考：若圖不通如何處理？6.3圖的遍歷例1：已知一個圖，若從頂點v1出發(fā)分別寫出按深度優(yōu)先搜索法進行遍歷和按寬度優(yōu)先搜索法進行遍歷的一種可能得到的頂點序列。V1V2V3V4V5V6深度優(yōu)先搜索法遍歷序列：

V1,V2,V3,V5,V6,V4寬度優(yōu)先搜索法遍歷序列:V1,V2,V3,V4,V5,V66.3圖的遍歷例2：已知一個圖的鄰接表存儲結構如下圖，若從頂點v1出發(fā)分別寫出有向圖按深度優(yōu)先搜索法進行遍歷和按寬度優(yōu)先搜索法進行遍歷的得到的頂點序列。深度優(yōu)先搜索法遍歷序列：

V1,V2,V3,V5,V6,V4寬度優(yōu)先搜索法遍歷序列:V1,V2,V3,V4,V5,V6V1V2V3V4V5V6234550123451202431006.3.2深度優(yōu)先搜索（DFS）圖的深度優(yōu)先搜索算法DFSTraverse(G)解決方案：

遍歷過程實際上也是尋找鄰接點的過程，總體過程類似于廣度優(yōu)先搜索，區(qū)別在于尋找鄰接點的方式不同，所以主體算法處理大致相同

深度優(yōu)先搜索因為是搜索鄰接點的鄰接點，所以它可以看成是一個遞歸的過程6.3.2深度優(yōu)先搜索（DFS）圖的深度優(yōu)先搜索算法DFSTraverse(G)算法處理步驟：

1、

初始化visited數(shù)組

2、從某個未被訪問過頂點出發(fā)深度搜索所有未被訪問的結點DFS(G,v)

3、如果圖為非連通圖，則從某個頂點出發(fā)并不能訪問圖中所有結點而只能訪問圖中一連通分量，此時需從圖選擇另一未被訪問過的結點，繼續(xù)深度優(yōu)先搜索6.3.2深度優(yōu)先搜索（DFS）【算法6.11】圖的深度優(yōu)先搜索算法privatestaticboolean[]visited;//定義標志數(shù)組publicstaticvoidDFSTraverse(IGraphG)throwsException{

//標志數(shù)組初始化 visited=newboolean[G.getVexNum()]; for(intv=0;v<G.getVexNum();v++) visited[v]=false; for(intv=0;v<G.getVexNum();v++) if(!visited[v])//對尚未訪問的頂點

DFS(G,v);}與廣度優(yōu)先搜索不同的地方6.3.2深度優(yōu)先搜索（DFS）從某個頂點出發(fā)的深度優(yōu)先搜索算法DFS(G)解決方案：

深度優(yōu)先搜索因為是搜索鄰接點的鄰接點，所以它可以看成是一個遞歸的過程6.3.2深度優(yōu)先搜索（DFS）【算法6.11】圖的深度優(yōu)先搜索算法publicstaticvoidDFS(IGraphG,intv)throwsException{

//標記第v個頂點訪問過 visited[v]=true; System.out.print(G.getVex(v).toString()+""); for(intw=G.firstAdjVex(v);w>=0; w=G.nextAdjVex(v,w)) if(!visited[w])//尚未訪問的v的鄰接頂點w

DFS(G,w);//遞歸調用}6.3.2深度優(yōu)先搜索（DFS）【算法6.11】圖的深度優(yōu)先搜索算法性能分析在上述算法中，對圖中的每一個頂點最多調用一次DFS方法，深度優(yōu)先搜索遍歷圖的時間復雜度和廣度優(yōu)先搜索遍歷相同，不同之處僅在于對頂點的訪問順序不同。因此，遍歷圖的過程實際上就是查找每一個頂點的鄰接點的過程。假設圖有n個頂點和e條邊6.3.2深度優(yōu)先搜索（DFS）【算法6.11】圖的深度優(yōu)先搜索算法性能分析時間復雜度（同廣度優(yōu)先搜索）存儲結構采用鄰接矩陣時，需要掃描鄰接矩陣中的每一個頂點，其時間復雜度為O(n2)；當圖的存儲結構采用鄰接表時，需要掃描鄰接表中的每一個單鏈表，其時間復雜度為O(e)空間復雜度遞歸調用使用棧，棧最深為n增設一個輔助數(shù)組，大小為n6.1圖的概述教學內容6.2圖的存儲結構6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓撲排序6.7關鍵路徑6.4.1最小生成樹的基本概念連通圖的生成樹（SpanningTree）是圖的極小連通子圖，它包含圖中的全部頂點是圖的極大無回路子圖，它的邊集是關聯(lián)圖中的所有頂點而又沒有形成回路的邊一個有n個頂點的連通圖的生成樹只能有n-1條邊圖的生成樹不是唯一的連通圖的生成樹（SpanningTree）廣度優(yōu)先生成樹（BFSSpanningTree）深度優(yōu)先生成樹（DFSSpanningTree）6.4.1最小生成樹的基本概念非連通圖的生成森林對于非連通圖，每一個連通分量中的頂點集和遍歷時經(jīng)過的邊一起構成若干棵生成樹這些生成樹組成了該非連通圖的生成森林廣度優(yōu)先生成森林（BFSSpanningForest）深度優(yōu)先生成森林（DFSSpanningForest）6.4.1最小生成樹的基本概念問題： 假設要在n個城市之間建立通訊聯(lián)絡網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？6.4.1最小生成樹的基本概念該問題等價于： 構造網(wǎng)的一棵最小生成樹，即：在e條帶權的邊中選取n-1條邊（不構成回路），使“權值之和”為最小。6.4.1最小生成樹的基本概念最小生成樹在一個網(wǎng)的所有生成樹中，權值總和最小的生成樹稱為最小代價生成樹（MinimumCostSpanningTree)6.4.1最小生成樹的基本概念構造最小生成樹的準則：只能使用該圖中的邊構造最小生成樹；當且僅當使用n-1條邊來連接圖中的n個頂點；不能使用產(chǎn)生回路的邊。6.4.1最小生成樹的基本概念求圖的最小生成樹的典型的算法克魯斯卡爾（Kruskal）算法普里姆(Prim）算法6.4.1最小生成樹的基本概念考慮問題的出發(fā)點相同:為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄?.4.2克魯斯卡爾算法

先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。abcdegf195141827168213ae12dcbgf714853162171218196.4.2克魯斯卡爾算法所得生成樹權值和=14+8+3+5+16+21=67克魯斯卡爾（Kruskal）算法處理步驟： 設圖G＝(V,E)是一個具有n個頂點的連通無向網(wǎng)，

T＝(V,TE)是圖G的最小生成樹T的初始狀態(tài)為T＝(V,?)

將圖G中的邊按照權值從小到大的順序排序依次選取每條邊，若選取的邊未使生成樹T形成回路，則加入TE中；否則舍棄，直至TE中包含了n-1條邊為止6.4.2克魯斯卡爾算法連通無向網(wǎng)Gv0v1v2v3v4v57717563642v0v1v2v3v4v5圖G的最小生成樹T最小生成樹T生成過程：1、T＝(V,TE)，TE＝?2、將邊按權值由小到大排序v0v21v3v52v1v43v2v54v0v35v1v26v2v46v0v17v3v27v4v57起點終點權值3、按權值由小到大依次取每一條邊，如果構成回路就舍棄TEv0v21v3v52v1v43v2v54v1v26邊數(shù)12345＝n-16.4.2克魯斯卡爾算法克魯斯卡爾（Kruskal）算法分析不是每一條權值最小的邊都必然可選，有可能構成回路最小生成樹不是唯一的，因為同一時候可能有多種選擇算法的時間復雜度為O(eloge)，即克魯斯卡爾算法的執(zhí)行時間主要取決于圖的邊數(shù)該算法適用于針對稀疏圖的操作6.4.2克魯斯卡爾算法普里姆算法的基本思想:6.4.3普里姆算法取圖中任意一個頂點v作為生成樹的根，之后往生成樹上添加新的頂點w。在添加的頂點w和已經(jīng)在生成樹上的頂點v之間必定存在一條邊，并且該邊的權值在所有連通頂點v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n-1個頂點為止。abcdegf195141827168213ae12dcbgf7148531621所得生成樹權值和=14+8+3+5+16+21=676.4.3普里姆算法

在生成樹的構造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

和尚未落在生成樹上的頂點集V-U

，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。

一般情況下所添加的頂點應滿足下列條件:6.4.2克魯斯卡爾算法例題：

設有如下的兩個網(wǎng)絡,分別用普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法具體構造相應的最小生成樹。abdefc65362551646.4.3普里姆算法補充幾個有關距離的定義兩個頂點之間的距離：指將頂點鄰接到的關聯(lián)邊的權值，記為：|u,v|頂點到頂點集合之間的距離：指頂點到頂點集合中所有頂點之間的距離中的最小值，記為：|u,V|=minv∈V|u,v|兩個頂點集合之間的距離：指頂點集合到頂點集合中所有頂點之間的距離中的最小值，記為：|U,V|=minu∈U|u,V|v0v1v2v3v4v57717563642|v1,v0|令：V={v0,v2,v3}則：|v1,V|令：U={v2,v4,v5}V={v0,v2,v3}則：|U,V|=7=6=26.4.3普里姆算法普里姆(Prim）算法 從某個點開始構造最小生成樹設圖G＝(V,E)是一個具有n個頂點的連通無向網(wǎng)，T＝(V,TE)是圖G的最小生成樹

從V中任取一頂點，將它并入U中，每次選擇U內頂點到V-U（U之外的頂點）所有邊中最小的，并將另一不在U內的頂點并入U，相應的邊并入TE中，直到所有頂點都并入U6.4.3普里姆算法連通無向網(wǎng)Gv0v1v2v3v4v57717563642v0v1v2v3v4v5圖G的最小生成樹T從頂點V0開始71566423序號iclosedgeuv-u1adjvexlowcost2adjvexlowcost3adjvexlowcost4adjvexlowcost5adjvexlowcost6adjvexlowcostv07v01v0500000v26v26v2600v05v52000v26v26v26v130v240000{v0}{v0,v2}{v0,v2,v5}{v0,v2,v3,v5}{v0,v1,v2,v3,v5}{v0,v1,v2,v3,v4,v5}{v1,v2,v3,v4,v5}{v1,v3,v4,v5}{v1,v3,v4}{v1,v4}{v4}?v1v2v3v4v5輔助數(shù)組：6.4.3普里姆算法普里姆(Prim）算法類描述：publicclassMiniSpanTree_PRIM{ privateclassCloseEdge{//內部類，輔助記錄從頂點集U到V-U的代價最小的邊 ObjectadjVex; intlowCost;

publicCloseEdge(ObjectadjVex,intlowCost){ this.adjVex=adjVex; this.lowCost=lowCost;

} }6.4.3普里姆算法普里姆(Prim）算法：publicObject[][]PRIM(MGraphG,Objectu)throwsException{

//定義二維數(shù)組tree，用于記錄加入最小生成樹的邊 Object[][]tree=newObject[G.getVexNum()-1][2]; intcount=0; //添加邊的計數(shù)，count<=n-1//定義輔助數(shù)組

，記錄已添加的頂點集U，0表示已選 CloseEdge[]closeEdge= newCloseEdge[