數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言描述)：第6章 圖(Java版)

第六章圖教學(xué)內(nèi)容6.1圖的概述6.2圖的存儲(chǔ)結(jié)構(gòu)6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓?fù)渑判?.7關(guān)鍵路徑教學(xué)重點(diǎn)與難點(diǎn)重點(diǎn)：圖的概念；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷；最小生成樹；最短路徑；拓?fù)渑判颍魂P(guān)鍵路徑。難點(diǎn)：最小生成樹；最短路徑；關(guān)鍵路徑；圖的應(yīng)用學(xué)習(xí)指南

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

是有窮非空集合，稱為頂點(diǎn)集，v

∈V稱為頂點(diǎn)。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是空集，此時(shí)圖只有頂點(diǎn)沒(méi)有邊6.1.1圖的基本概念---無(wú)向邊、無(wú)向圖無(wú)向邊e=(u,v)=(v,u),其中u,v

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

假設(shè)圖中有

n

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

條邊，則完全無(wú)向圖含有

條邊；完全有向圖含有

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

若邊或弧的個(gè)數(shù)

e<nlogn，則稱作稀疏圖，否則稱作稠密圖。6.1.1圖的基本概念---子圖子圖（Subgraph）設(shè)有兩個(gè)圖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的生成子圖，即包含原圖中所有頂點(diǎn)的子圖。6.1.1圖的基本概念---子圖01342無(wú)向圖G100101342無(wú)向圖G1的生成子圖01342無(wú)向圖G1的生成子圖6.1.1圖的基本概念---鄰接點(diǎn)鄰接點(diǎn)（Adjacent）在一個(gè)無(wú)向圖中，若存在一條邊(u,v)，則稱頂點(diǎn)u與v互為鄰接點(diǎn)。邊(u,v)是頂點(diǎn)u和v關(guān)聯(lián)的邊，頂點(diǎn)u和v是邊(u,v)關(guān)聯(lián)的頂點(diǎn)。以頂點(diǎn)1為端點(diǎn)的3條邊是(0,1),(1,2),(1,4),頂點(diǎn)1的3個(gè)鄰接點(diǎn)分別為0,2,4；01342無(wú)向圖G16.1.1圖的基本概念---鄰接點(diǎn)鄰接點(diǎn)（Adjacent）在一個(gè)有向圖中,若存在一條弧<u,v>，則稱頂點(diǎn)u鄰接到v,頂點(diǎn)v鄰接自u(píng)?；?lt;u,v>和頂點(diǎn)u、v關(guān)聯(lián)。頂點(diǎn)v0有2條出邊<v0,v1>，<v0,v2>，1條入邊<v3,v0>,頂點(diǎn)v0鄰接到v1和v2，頂點(diǎn)v0鄰接自v3.v0v1v2v3v4有向圖G26.1.1圖的基本概念---頂點(diǎn)的度頂點(diǎn)的度（Degree）頂點(diǎn)的度是圖中與該頂點(diǎn)相關(guān)聯(lián)邊的數(shù)目，記為D(v)。若一個(gè)圖有n個(gè)頂點(diǎn)和e條邊，則該圖所有頂點(diǎn)的度之和與邊數(shù)滿足如下關(guān)系6.1.1圖的基本概念---無(wú)向圖頂點(diǎn)的度無(wú)向圖頂點(diǎn)的度(degree)定義為以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目，即該頂點(diǎn)的邊的數(shù)目，記為D(v)。e=5；n=5D(0)=1;

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

D(3)=2;

D(4)=2;01342無(wú)向圖G1=(1+3+2+2+2)/2=10/2=5=e6.1.1圖的基本概念---有向圖頂點(diǎn)的度有向圖頂點(diǎn)的度頂點(diǎn)v的入邊數(shù)目是該頂點(diǎn)的入度(InDegree)，記為ID(v)；頂點(diǎn)v的出邊數(shù)目是該頂點(diǎn)的出度(OutDegree)，記為OD(v)；頂點(diǎn)v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)6.1.1圖的基本概念---有向圖頂點(diǎn)的度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)在一個(gè)圖中，路徑是從頂點(diǎn)u到頂點(diǎn)v所經(jīng)過(guò)的頂點(diǎn)序列，即(u=vi0,vi1,…,vim=v)。路徑長(zhǎng)度是指該路徑上邊的數(shù)目?；芈罚?/p>

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

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

v0)是初等回路其路徑長(zhǎng)度為3從頂點(diǎn)v0到頂點(diǎn)v1的一條路徑

(v0,v2,v3,

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

v0,

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

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

若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。BACDFEABLCMHEFKGIDJ連通圖非連通圖6.1.1圖的基本概念--強(qiáng)連通圖和強(qiáng)連通分量

若有向圖中任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECF

否則，其各個(gè)極大強(qiáng)連通子圖稱作它的強(qiáng)連通分量。ABCF強(qiáng)連通圖非強(qiáng)連通圖

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

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

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

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

createGraph()

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

getVexNum()

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

getArcNum()

4）給定頂點(diǎn)的位置v，返回其對(duì)應(yīng)的頂點(diǎn)值，其中：0≤v<vexNum（vexNum為頂點(diǎn)數(shù)）

getVex(v)

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

6）返回v的第一個(gè)鄰接點(diǎn)，若v沒(méi)有鄰接點(diǎn)，則返回-1，其中：0≤v<vexNum firstAdjVex(v)

7）返回v相對(duì)于w的下一個(gè)鄰接點(diǎn)，若w是v的最后一個(gè)鄰接點(diǎn)，則返回-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)}教學(xué)內(nèi)容6.1圖的概述6.2圖的存儲(chǔ)結(jié)構(gòu)6.3圖的遍歷6.4最小生成樹6.5最短路徑6.6拓?fù)渑判?.7關(guān)鍵路徑6.2圖的存儲(chǔ)結(jié)構(gòu)圖的類型主要有四種：無(wú)向圖、有向圖、無(wú)向網(wǎng)和有向網(wǎng)?？梢杂妹杜e表示為publicenumGraphKind{UDG,//無(wú)向圖（UnDirectedGraph)DG, //有向圖（DirectedGraph)UDN,//無(wú)向網(wǎng)（UnDirectedNetwork)DN //有向網(wǎng)（DirectedNetwork)}一、圖的鄰接陣存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示*三、有向圖的十字鏈表存儲(chǔ)表示*四、無(wú)向圖的鄰接多重表存儲(chǔ)表示6.2圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接陣

6.2.1鄰接矩陣01342

6.2.1鄰接矩陣v0v1v2v3v4

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

//圖的種類標(biāo)志 privateGraphKindkind; //圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) privateintvexNum,arcNum;

//頂點(diǎn) 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)建無(wú)向圖 privatevoidcreateUDG(){……}

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

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

{……}

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

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

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

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

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

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

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

……}6.2.1鄰接矩陣publicclassMGraphimplementsIGraph{

……

//返回v的第一個(gè)鄰接點(diǎn)，若v沒(méi)有鄰接點(diǎn)則返回-1，0≤v<vexnum publicintfirstAdjVex(intv)throwsException {……}

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

操作要求：

輸入的圖的頂點(diǎn)、邊及權(quán)值構(gòu)造無(wú)向網(wǎng)問(wèn)題：

鄰接矩陣大?。?/p>

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

算法處理步驟：

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

//初始化變量

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

vexNum=sc.nextInt();

arcNum=sc.nextInt();

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

……

//輸入圖中各頂點(diǎn) vexs=newObject[vexNum]; System.out.println("請(qǐng)分別輸入圖的各個(gè)頂點(diǎn):"); for(intv=0;v<vexNum;v++)//構(gòu)造頂點(diǎn)向量

vexs[v]=sc.next(); ……}時(shí)間復(fù)雜度為O(n)6.2.1鄰接矩陣【算法6.2】無(wú)向網(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;//初始為無(wú)窮大 ……}時(shí)間復(fù)雜度為O(n2)6.2.1鄰接矩陣【算法6.2】無(wú)向網(wǎng)的創(chuàng)建算法privatevoidcreateUDN(){ ……//輸入邊信息System.out.println("請(qǐng)輸入各個(gè)邊的兩個(gè)頂點(diǎn)及其權(quán)值:");for(intk=0;k<arcNum;k++){ intv=locateVex(sc.next());//頂點(diǎn) intu=locateVex(sc.next());//頂點(diǎn)

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

6.2.1鄰接矩陣

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

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

如何確定查找？解決：

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

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

如何確定查找？解決：

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

操作要求：

返回v的第一個(gè)鄰接點(diǎn)，若v沒(méi)有鄰接點(diǎn)則返回-1，0≤v<vexnum問(wèn)題：

如何確定鄰接點(diǎn)？6.2.1鄰接矩陣

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

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

操作要求：

返回v相對(duì)于w的下一個(gè)鄰接點(diǎn)，若w是v的最后一個(gè)鄰接點(diǎn)，則返回-1，其中0≤v,w<vexNum問(wèn)題：

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

算法處理步驟： 1、

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

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

鄰接表：邊表表示所有以vi為始點(diǎn)的弧。012341423012ABCDEABECD在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。有向圖對(duì)應(yīng)的鄰接表某行上邊結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的出度6.2.2鄰接表-有向圖

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

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

1）鄰接矩陣

2）每個(gè)頂點(diǎn)的入/出度；

3）鄰接表及逆鄰接表

4）強(qiáng)連通分量2156436.2.2鄰接表-頂點(diǎn)結(jié)點(diǎn)類publicclassVNode{

privateObjectdata;//頂點(diǎn)信息

privateArcNodefirstArc;

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

//該弧所指向的頂點(diǎn)位置

privateintadjVex;

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

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

……}6.2.2鄰接表-邊結(jié)點(diǎn)類publicclassArcNode{

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

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

給定頂點(diǎn)的值vex，返回其在圖中的位置，若圖中不包含此頂點(diǎn)，則返回-1問(wèn)題：

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

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

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

//vexNum為頂點(diǎn)個(gè)數(shù)n

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

操作要求：

輸入的圖的頂點(diǎn)、邊及權(quán)值構(gòu)造無(wú)向網(wǎng)問(wèn)題：

鄰接表大小？

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

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

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

//初始化變量

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

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

……

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

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

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

……

//輸入圖中各邊信息 System.out.println("請(qǐng)輸入各邊的頂點(diǎn)及其權(quán)值:"); 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);//加入邊 }}時(shí)間復(fù)雜度為O(n*e)6.2.2鄰接表【算法6.7】無(wú)向網(wǎng)的創(chuàng)建算法性能分析初始化變量輸入圖中各頂點(diǎn)輸入圖中各邊信息總的時(shí)間復(fù)雜度是

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

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

用鄰接表存儲(chǔ)圖時(shí)，將權(quán)值為value的邊（或?。?/p>

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

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

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

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

//u為邊的終點(diǎn)，生成邊結(jié)點(diǎn) ArcNodearc=newArcNode(u,value);

//v為邊的起點(diǎn)，將邊結(jié)點(diǎn)插入頂點(diǎn)v的鏈表表頭

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

//生成新表頭 vexs[v].setFirstArc(arc);}//算法6.8結(jié)束時(shí)間復(fù)雜度為O(1)6.2.2鄰接表查找下一個(gè)鄰接點(diǎn)的算法nextAdjVex(v,w)

操作要求：

返回v相對(duì)于w的下一個(gè)鄰接點(diǎn)，若w是v的最后一個(gè)鄰接點(diǎn)，則返回-1，其中0≤v,w<vexNum問(wèn)題：

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

算法處理步驟： 1、

判斷插入位置是否正確 2、取結(jié)點(diǎn)v 3、在鄰接表中查找結(jié)點(diǎn)w

4、取w的下一結(jié)點(diǎn)

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

//取結(jié)點(diǎn)vVNodevex=vexs[v];

//用于取結(jié)點(diǎn)v的鄰接點(diǎn)ArcNodearcvw=null;

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

//取出結(jié)點(diǎn)w arcvw=arc; break;}

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

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

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

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

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

初始化visited數(shù)組 2、從某個(gè)未被訪問(wèn)過(guò)頂點(diǎn)出發(fā)廣度搜索所有未被訪問(wèn)的結(jié)點(diǎn)BFS(G,v)

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

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

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

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

3、每個(gè)結(jié)點(diǎn)一旦被訪問(wèn)就插入隊(duì)列中

4、當(dāng)沒(méi)有可以訪問(wèn)的鄰接點(diǎn)時(shí)，從隊(duì)頭取出一個(gè)結(jié)點(diǎn)，訪問(wèn)它所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，重復(fù)上面的過(guò)程，直到隊(duì)列為空6.3.1廣度優(yōu)先搜索（BFS）準(zhǔn)備工作：//標(biāo)記起始結(jié)點(diǎn)v被訪問(wèn)visited[v]=true;//定義輔助隊(duì)列QLinkQueueQ=newLinkQueue();//v入隊(duì)列Q.offer(v);6.3.1廣度優(yōu)先搜索（BFS）//隊(duì)列不空，取出隊(duì)頭結(jié)點(diǎn)u，訪問(wèn)u所有鄰結(jié)點(diǎn)while(!Q.isEmpty()){intu=(Integer)Q.poll();

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

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

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

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

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

visited[w]=true;

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

}

}}//算法6.10結(jié)束6.3.1廣度優(yōu)先搜索（BFS）【算法6.10】圖的廣度優(yōu)先搜索算法privatestaticboolean[]visited;//定義標(biāo)志數(shù)組publicstaticvoidBFSTraverse(IGraphG)throwsException{ //標(biāo)志數(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尚未訪問(wèn)

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

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

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

的子圖。訪問(wèn)頂點(diǎn)V：for(W1、W2、W3)

若該鄰接點(diǎn)Wi未被訪問(wèn)，

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

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

V1,V2,V3,V5,V6,V4寬度優(yōu)先搜索法遍歷序列:V1,V2,V3,V4,V5,V66.3圖的遍歷例2：已知一個(gè)圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖，若從頂點(diǎn)v1出發(fā)分別寫出有向圖按深度優(yōu)先搜索法進(jìn)行遍歷和按寬度優(yōu)先搜索法進(jìn)行遍歷的得到的頂點(diǎn)序列。深度優(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)解決方案：

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

深度優(yōu)先搜索因?yàn)槭撬阉鬣徑狱c(diǎn)的鄰接點(diǎn)，所以它可以看成是一個(gè)遞歸的過(guò)程6.3.2深度優(yōu)先搜索（DFS）圖的深度優(yōu)先搜索算法DFSTraverse(G)算法處理步驟：

1、

初始化visited數(shù)組

2、從某個(gè)未被訪問(wèn)過(guò)頂點(diǎn)出發(fā)深度搜索所有未被訪問(wèn)的結(jié)點(diǎn)DFS(G,v)

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

//標(biāo)志數(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])//對(duì)尚未訪問(wèn)的頂點(diǎn)

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

深度優(yōu)先搜索因?yàn)槭撬阉鬣徑狱c(diǎn)的鄰接點(diǎn)，所以它可以看成是一個(gè)遞歸的過(guò)程6.3.2深度優(yōu)先搜索（DFS）【算法6.11】圖的深度優(yōu)先搜索算法publicstaticvoidDFS(IGraphG,intv)throwsException{

//標(biāo)記第v個(gè)頂點(diǎn)訪問(wèn)過(guò) 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])//尚未訪問(wèn)的v的鄰接頂點(diǎn)w

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

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

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

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

在生成樹的構(gòu)造過(guò)程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U

和尚未落在生成樹上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:6.4.2克魯斯卡爾算法例題：

設(shè)有如下的兩個(gè)網(wǎng)絡(luò),分別用普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法具體構(gòu)造相應(yīng)的最小生成樹。abdefc65362551646.4.3普里姆算法補(bǔ)充幾個(gè)有關(guān)距離的定義兩個(gè)頂點(diǎn)之間的距離：指將頂點(diǎn)鄰接到的關(guān)聯(lián)邊的權(quán)值，記為：|u,v|頂點(diǎn)到頂點(diǎn)集合之間的距離：指頂點(diǎn)到頂點(diǎn)集合中所有頂點(diǎn)之間的距離中的最小值，記為：|u,V|=minv∈V|u,v|兩個(gè)頂點(diǎn)集合之間的距離：指頂點(diǎn)集合到頂點(diǎn)集合中所有頂點(diǎn)之間的距離中的最小值，記為：|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è)點(diǎn)開始構(gòu)造最小生成樹設(shè)圖G＝(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向網(wǎng)，T＝(V,TE)是圖G的最小生成樹

從V中任取一頂點(diǎn)，將它并入U(xiǎn)中，每次選擇U內(nèi)頂點(diǎn)到V-U（U之外的頂點(diǎn)）所有邊中最小的，并將另一不在U內(nèi)的頂點(diǎn)并入U(xiǎn)，相應(yīng)的邊并入TE中，直到所有頂點(diǎn)都并入U(xiǎn)6.4.3普里姆算法連通無(wú)向網(wǎng)Gv0v1v2v3v4v57717563642v0v1v2v3v4v5圖G的最小生成樹T從頂點(diǎn)V0開始71566423序號(hào)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{//內(nèi)部類，輔助記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊 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; //添加邊的計(jì)數(shù)，count<=n-1//定義輔助數(shù)組

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