1、第六章第六章 圖圖第第6 6章章 圖圖6.1 圖的概述圖的概述6.2 圖的存儲結構圖的存儲結構6.3 圖的遍歷圖的遍歷6.4 最小生成樹最小生成樹6.5 最短路徑最短路徑6.6 拓撲排序拓撲排序6.7 關鍵路徑關鍵路徑第第6 6章章 圖圖重點：重點：u圖的概念；圖的存儲結構；圖的遍圖的概念；圖的存儲結構；圖的遍歷；最小生成樹；最短路徑；拓撲歷；最小生成樹；最短路徑；拓撲排序；關鍵路徑。排序；關鍵路徑。難點：難點：u關鍵路徑關鍵路徑第第6 6章章 圖圖 圖是較線性表和樹更為復雜的數據結構，圖是較線性表和樹更為復雜的數據結構，因此和線性表、樹不同，雖然在遍歷圖的同因此和線性表、樹不同，雖然在遍歷圖

2、的同時可以對頂點或弧進行各種操作，但更多圖時可以對頂點或弧進行各種操作，但更多圖的應用問題如求最小生成樹等在圖論的研究的應用問題如求最小生成樹等在圖論的研究中都早已有了特定算法，在本章中主要是介中都早已有了特定算法，在本章中主要是介紹它們在計算機中的具體實現。這些算法乍紹它們在計算機中的具體實現。這些算法乍一看都比較難，應多對照具體圖例的存儲結一看都比較難，應多對照具體圖例的存儲結構進行學習。而圖遍歷的兩種搜索路徑和樹構進行學習。而圖遍歷的兩種搜索路徑和樹遍歷的兩種搜索路徑極為相似，應將兩者的遍歷的兩種搜索路徑極為相似，應將兩者的算法對照學習以便提高學習的效益。算法對照學習以便提高學習的效益。

3、 6.1 圖的概述圖的概述6.1 圖的概述圖的概述6.2 圖的存儲結構圖的存儲結構6.3 圖的遍歷圖的遍歷6.4 最小生成樹最小生成樹6.5 最短路徑最短路徑6.6 拓撲排序拓撲排序6.7 關鍵路徑關鍵路徑6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -圖圖由頂點（由頂點（Vertex）集和邊）集和邊( Edge）集組成，）集組成， 記為記為 G（V，E）,其中其中V 是是有窮非空集有窮非空集合，合，稱為稱為頂點集頂點集，v V 稱為頂點。稱為頂點。E 是是有窮集有窮集合，合，稱為稱為邊集邊集， e E 稱為邊稱為邊.EACBD例如例如: :G = (V, E)其中其中V=A,

4、B, C, D, EE=, , , , , , 零圖：零圖：E 是空集，是空集，此時圖只有頂點沒有邊此時圖只有頂點沒有邊6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -無向邊、無向圖無向邊、無向圖u 無向邊無向邊e =(u,v) =(v,u), 其中其中u,v V,邊邊(u,v)與邊與邊(v,u)是相同的。是相同的。u 無向圖（無向圖（Undirected Graph)全部由無向邊構成的圖全部由無向邊構成的圖01342無向圖無向圖G1 例例 G1(V1, E1) V1=0,1,2,3,4 E1=(0,1),(1,2),(1,4),(2,3),(3,4)6.1 圖的概述圖的概述6.

5、1.1圖的基本概念圖的基本概念 -有向邊、有向圖有向邊、有向圖例：例： G2(V2, E2)V2=v0, v1, v2, v3, v4E2=, ,v0v1v2v3v4有向圖有向圖G2u有向邊有向邊e =, 其中其中u,v V，簡稱為簡稱為弧?。ˋrc）其中其中u為始點（為始點（Initial Node）或）或弧尾弧尾（Tail），），v為終點（為終點（Terminal Node)或或弧頭弧頭（Head）邊邊與邊與邊是不同的是不同的u有向圖（有向圖（Directed Graph)全部由有向邊構成的圖全部由有向邊構成的圖6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -權、網權、網AB

6、EFDC2102755無向網無向網G3ABCD14764有向網有向網G46.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -權、網權、網u 權（權（Weight）：在一個圖中，每條邊可以標上在一個圖中，每條邊可以標上具有某種具有某種含義的數值含義的數值，此數值稱為該邊上的權，此數值稱為該邊上的權通常權是一個通常權是一個非負實數非負實數權可以表示從一個頂點到另一個頂點的權可以表示從一個頂點到另一個頂點的距離、時間或代價等含義距離、時間或代價等含義u 網（網（Network)邊上標識權的圖稱為邊上標識權的圖稱為網網6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -完全圖完全圖

7、 完全無向圖完全無向圖中的每兩個頂點之間都存在著中的每兩個頂點之間都存在著一一條邊條邊；完全有向圖完全有向圖中的每兩個頂點之間都存在中的每兩個頂點之間都存在著方向著方向相反的兩條邊相反的兩條邊0132完全無向圖完全無向圖ACB完全有向圖完全有向圖 假設圖中有假設圖中有 n 個頂點，個頂點，e 條邊，則條邊，則完全完全無向圖無向圖含有含有 e=n(n-1)/2 條邊；條邊；完全完全有向圖有向圖含有含有 e=n(n-1) 條弧條弧6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -稀疏稀疏圖、圖、稠密圖稠密圖 若邊或弧的個數若邊或弧的個數 eenlognnlogn，則稱作，則稱作稀疏圖稀

8、疏圖，否則稱作，否則稱作稠密圖稠密圖。6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -子圖子圖u 子圖（子圖（Subgraph）設有兩個圖設有兩個圖G(V, E)和和G(V , E ) ，若若V 是是V 的子集，即的子集，即V V ，并且，并且E 是是E 的子集，即的子集，即E E ，則稱，則稱G為為G的子圖，的子圖，記為記為G G 。u 生成子圖（生成子圖（Spanning Subgraph)若若G為為G的子圖，并且的子圖，并且V V ，則稱，則稱G為為G的生成子圖，即包含原圖中所有頂點的生成子圖，即包含原圖中所有頂點的子圖。的子圖。6.1 圖的概述圖的概述6.1.1圖的基本概

9、念圖的基本概念 -子圖子圖01342無向圖無向圖G100101342無向圖無向圖G1的生成子圖的生成子圖01342無向圖無向圖G1的生成子圖的生成子圖6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -鄰接點鄰接點u 鄰接點（鄰接點（Adjacent）在一個在一個無向圖無向圖中，若存在一條邊中，若存在一條邊(u,v)，則稱頂點則稱頂點u與與v互為互為鄰接點鄰接點。邊。邊(u,v)是頂點是頂點u和和v關聯的邊關聯的邊，頂點，頂點u和和v是邊是邊(u,v)關聯的頂關聯的頂點。點。 以頂點以頂點1為端點為端點的的3條邊是條邊是(0,1),(1,2),(1,4),頂點頂點1的的3個鄰接點分個

10、鄰接點分別為別為0,2,4；01342無向圖無向圖G16.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -鄰接點鄰接點u 鄰接點（鄰接點（Adjacent）在一個在一個有向圖有向圖中中,若存在一條弧若存在一條弧，則稱頂點則稱頂點u鄰接到鄰接到v,頂點頂點v鄰接自鄰接自u。弧?；『晚旤c和頂點u、v關聯。關聯。 頂點頂點v0有有2條出邊條出邊，1條入邊條入邊,頂頂點點v0鄰接到鄰接到v1和和v2 ，頂點頂點v0鄰接自鄰接自v3.v0v1v2v3v4有向圖有向圖G26.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -頂點的度頂點的度u 頂點的度（頂點的度（Degree）頂點的度是

11、圖中與該頂點相關聯邊的數頂點的度是圖中與該頂點相關聯邊的數目，記為目，記為D(v) 。若一個若一個圖圖有有n個頂點和個頂點和e條邊，則該圖所條邊，則該圖所有頂點的度之和與邊數滿足如下關系有頂點的度之和與邊數滿足如下關系 1021)(niivDe6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -無向圖頂點的度無向圖頂點的度 無向圖頂點的度無向圖頂點的度(degree)定義為以該頂點為一定義為以該頂點為一個端點的邊的數目，即該頂點的個端點的邊的數目，即該頂點的邊的數目邊的數目，記為，記為D(v) 。e=5； n=5D(0)=1; D(1)=3;D(2)=2; D(3)=2; D(4)=

12、2; 01342無向圖無向圖G1 1021niivD)(=(1+3+2+2+2)/2=10/2=5=e6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -有向圖頂點的度有向圖頂點的度 有向圖有向圖頂點的度頂點的度l 頂點頂點v的的入邊數目入邊數目是該頂點的是該頂點的入度入度(indegree)，記為，記為ID(v)；l 頂點頂點v的的出邊數目出邊數目是該頂點的是該頂點的出度出度(outdegree)，記為，記為OD(v)；l 頂點頂點v的度等于它的入度和出度之和，即的度等于它的入度和出度之和，即 D(v)=ID(v)+OD(v)6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概

13、念 -有向圖頂點的度有向圖頂點的度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 1021)(niivD=(3+1+2+3+1)/2=10/2=5=e6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -路徑、回路路徑、回路u 路徑路徑(Path)l在一個圖中，路徑是從頂點在一個圖中，路徑是從頂點u到頂點到頂點v

14、所所經過的頂點序列，即經過的頂點序列，即(u=vi0, vi1, , vim=v)。l路徑長度路徑長度是指該路徑上邊的數目。是指該路徑上邊的數目。u回路：回路： 第一個頂點和第一個頂點和最后一個頂點相同的最后一個頂點相同的路徑稱為回路或環。路徑稱為回路或環。ABECF6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -路徑、回路路徑、回路u 初等路徑初等路徑序列中頂點不重復出現的路徑稱為初等序列中頂點不重復出現的路徑稱為初等路徑路徑u初等回路初等回路 除了除了第一第一個頂點個頂點和和最后最后一個頂點之外，一個頂點之外，其余頂點不重復出現其余頂點不重復出現的回路的回路ABECF6.1

15、圖的概述圖的概述6.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 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -網中的路徑長度網中的路徑長度u 網中的路徑長度網中的路徑長度在在網

16、網中，從始點到終點的路徑上各邊的中，從始點到終點的路徑上各邊的權值之和權值之和，稱為，稱為路徑長度路徑長度ABEFDC2102755無向圖無向圖G3從頂點從頂點A到頂點到頂點E的一條的一條路徑路徑 ： ( A, B , D, E ) 路徑長度路徑長度為為10+7+2=196.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -連通圖和連通分量連通圖和連通分量 若若無向圖無向圖G G中任中任意兩個頂點之間都有意兩個頂點之間都有路徑相通，則稱此圖路徑相通，則稱此圖為為連通圖連通圖； 若若無向圖無向圖為非連通圖，為非連通圖，則圖中則圖中各個極大連通子各個極大連通子圖圖稱作此圖的稱作此圖的連通分

17、量連通分量。BACDFEABLCMHEFKGIDJ連通圖連通圖非連通圖非連通圖6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -強連通圖和強連通分量強連通圖和強連通分量 若若有向圖中有向圖中任意兩個頂點之間都存在一任意兩個頂點之間都存在一條條有向路徑，有向路徑，則稱此有向圖為則稱此有向圖為強連通圖。強連通圖。ABECF 否則，其各個極大強連通子圖稱作它的否則，其各個極大強連通子圖稱作它的強連通分量強連通分量。ABCF強連通圖強連通圖非強連通圖非強連通圖6.1 圖的概述圖的概述6.1.1圖的基本概念圖的基本概念 -生成樹生成樹 假設一個假設一個連通圖連通圖有有 n n 個頂點和個頂點

18、和 e e 條邊，條邊，其中其中 n-1 n-1 條邊和條邊和 n n 個頂點構成一個極小連通個頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的子圖，稱該極小連通子圖為此連通圖的生成樹生成樹。BACDFE6.1 圖的概述圖的概述3個個連通分量連通分量6.1.1圖的基本概念圖的基本概念 -生成森林生成森林ACDEFHKBGIMLJ非邊通圖非邊通圖ACDEFHKBGIMLJ 對對非連通圖非連通圖，則稱由各個連通分量的生成，則稱由各個連通分量的生成樹的集合為此非連通圖的樹的集合為此非連通圖的生成森林生成森林。6.1 圖的概述圖的概述6.1.2圖的抽象數據類型描述圖的抽象數據類型描述1.基本操作

19、（基本操作（1） 1）創建一個圖）創建一個圖createGraph() 2）返回圖中的頂點數）返回圖中的頂點數getVexNum() 3）返回圖中的邊數）返回圖中的邊數getArcNum() 4）給定頂點的位置）給定頂點的位置v，返回其對應的頂點值，返回其對應的頂點值，其中：其中：0vvexNum（vexNum為頂點數）為頂點數）getVex(v) 5）給定頂點的值）給定頂點的值vex，返回其在圖中的位置，返回其在圖中的位置，如果圖中不包含此頂點，則返回如果圖中不包含此頂點，則返回-1locateVex(vex)6.1 圖的概述圖的概述6.1.2圖的抽象數據類型描述圖的抽象數據類型描述1.基本

20、操作（基本操作（2） 6）返回）返回v的第一個鄰接點，若的第一個鄰接點，若v沒有鄰接點，沒有鄰接點，則返回則返回-1，其中：，其中：0vvexNum firstAdjVex(v) 7）返回）返回v相對于相對于w的下一個鄰接點，若的下一個鄰接點，若w是是v的最后一個鄰接點，則返回的最后一個鄰接點，則返回-1， 其中：其中：0v, wvexNum nextAdjVex(v,w)6.1 圖的概述圖的概述6.1.2圖的抽象數據類型描述圖的抽象數據類型描述 2.線性表抽象數據類型的線性表抽象數據類型的Java接口描述接口描述public interface IGraphvoid createGraph(

21、); int getVexNum(); int getArcNum(); Object getVex(int v)int locateVex(Object vex)int firstAdjVex(int v)int nextAdjVex(int v, int w)6.2 圖的存儲結構圖的存儲結構6.1 圖的概述圖的概述6.2 圖的存儲結構圖的存儲結構6.3 圖的遍歷圖的遍歷6.4 最小生成樹最小生成樹6.5 最短路徑最短路徑6.6 拓撲排序拓撲排序6.7 關鍵路徑關鍵路徑6.2 圖的存儲結構圖的存儲結構6.2 圖的存儲結構圖的存儲結構圖的類型主要有四種：無向圖、有向圖、圖的類型主要有四種：無向

22、圖、有向圖、無向網和有向網。可以用枚舉表示無向網和有向網?？梢杂妹杜e表示public enum GraphKindUDG, /無向圖（無向圖（UnDirected Graph)DG, /有向圖（有向圖（Directed Graph)UDN, /無向網（無向網（UnDirected Network)DN; /有向網（有向網（Directed Network)6.2 圖的存儲結構圖的存儲結構一、圖的數組一、圖的數組(鄰接矩陣鄰接矩陣)存儲表示存儲表示二、圖的鄰接表存儲表示二、圖的鄰接表存儲表示*三、有向圖的十字鏈表存儲表示三、有向圖的十字鏈表存儲表示 *四、無向圖的鄰接多重表存儲表示四、無向圖的鄰

23、接多重表存儲表示6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣u 圖的鄰接矩陣圖的鄰接矩陣(Adjacency Matrix)用來表示頂點之間相鄰關系的矩陣。用來表示頂點之間相鄰關系的矩陣。假設圖假設圖G(V, E)具有具有n(n1)個頂點，個頂點，頂點的順序依次為頂點的順序依次為v0, v1, , vn-1，則圖，則圖的鄰接矩陣的鄰接矩陣A是一個是一個n階方陣階方陣1,0),(, 0),(, 1njiEvvEvvEvvEvvjiAjijijiji其中：或或6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣01342無向圖無向圖G1 01010101000101010101

24、0001043210432101A無向圖的鄰接矩陣是無向圖的鄰接矩陣是對稱的對稱的（可（可 采用壓縮存儲）采用壓縮存儲）頂點頂點vivi的度的度是第是第i i行或第行或第i i列中列中“1 1” 的元素個數。的元素個數。6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣v0v1v2v3v4有向圖有向圖G2 000001000101000000000011043210243210vvvvvAvvvvv 有向圖的鄰接矩陣有向圖的鄰接矩陣不一定不一定為為對稱對稱矩陣矩陣. 每一行中每一行中“1”1”的個數為該頂點的的個數為該頂點的出度出度； 每一列中每一列中11的個數為該頂點的的個數為該頂點

25、的入度入度。6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣ABEFDC2102755 555227257102103FEDCBAAFEDCBAu 網的鄰接矩陣網的鄰接矩陣 (Adjacency Matrix)10 njiEvvEvvEvvEvvwjiAjijijijiij,),(,),(,其中：其中：或或或或6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣圖的鄰接矩陣類的描述：圖的鄰接矩陣類的描述： public class MGraph implements IGraphpublic final static int INFINITY = Integer.MAX_VAL

26、UE;/圖的種類標志圖的種類標志private GraphKind kind;/ /圖的當前頂點數和邊數圖的當前頂點數和邊數private int vexNum, arcNum;/頂點頂點private Object vexs;/鄰接矩陣鄰接矩陣private int arcs;6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣public class MGraph implements Igraphpublic MGraph()this(null, 0, 0, null, null);public MGraph(GraphKind kind, int vexNum, int arcN

27、um, Object vexs, int arcs)this.kind = kind;this.vexNum = vexNum;this.arcNum = arcNum;this.vexs = vexs;this.arcs = arcs;6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣public class MGraph implements IGraph/創建圖創建圖public void createGraph() /創建無向圖創建無向圖private void createUDG() /創建有向圖創建有向圖private void createDG() /創建無向網創建無向網

28、private void createUDN() /創建有向網創建有向網private void createDN() 6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣public class MGraph implements IGraph/返回頂點數返回頂點數public int getVexNum()return vexNum;/返回邊數返回邊數public int getArcNum()return arcNum;/給定頂點的值給定頂點的值vex，返回其在圖中的位置，如果圖中不包含，返回其在圖中的位置，如果圖中不包含此頂點，則返回此頂點，則返回-1public int loc

29、ateVex(Object vex) 6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣public class MGraph implements IGraph/ 返回返回v表示結點的值，表示結點的值， 0 = v vexNum public Object getVex(int v) throws Exceptionif (v = vexNum) throw new Exception(第第 + v + 個頂點個頂點不存在不存在!);return vexsv; public GraphKind getKind() return kind; public int getArcs() r

30、eturn arcs; public Object getVexs() return vexs; 6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣public class MGraph implements IGraph/ 返回返回v的第一個鄰接點，若的第一個鄰接點，若v沒有鄰接點則返回沒有鄰接點則返回-1，0vvexnumpublic int firstAdjVex(int v) throws Exception / 返回返回v相對于相對于w的下一個鄰接點，若的下一個鄰接點，若w是是v的最后一個鄰接點，的最后一個鄰接點，則返回則返回-1，其中，其中0v,wvexNumpublic

31、int nextAdjVex(int v, int w) throws Exception 6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣無向網的創建算法無向網的創建算法createUDN() 操作要求：操作要求：輸入的圖的頂點、邊及權值構造無向網輸入的圖的頂點、邊及權值構造無向網問題：問題：鄰接矩陣大??？鄰接矩陣大小？如何確定每一條邊？如何確定每一條邊？6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣無向網的創建算法無向網的創建算法createUDN() 算法處理步驟：算法處理步驟：1、輸入頂點數和邊數、輸入頂點數和邊數2、根據圖的頂點數構造鄰接矩陣、根據圖的頂點數構造

32、鄰接矩陣3、根據圖的邊數，確定輸入邊的數目、根據圖的邊數，確定輸入邊的數目4、根據輸入每條邊的頂點在鄰接矩陣相、根據輸入每條邊的頂點在鄰接矩陣相應位置保存每條邊的權值應位置保存每條邊的權值6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【P199/算法算法6.2】無向網的創建算法無向網的創建算法private void createUDN() /初始化變量初始化變量Scanner sc = new Scanner(System.in);System.out.println(請分別輸入圖的頂點數、圖請分別輸入圖的頂點數、圖的邊數的邊數:);vexNum = sc.nextInt();

33、arcNum = sc.nextInt(); /頂點數頂點數n/邊數邊數e6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【 P199/算法算法6.2】無向網的創建算法無向網的創建算法private void createUDN() /輸入圖中各頂點輸入圖中各頂點vexs = new ObjectvexNum;System.out.println(請分別輸入圖的各個頂點請分別輸入圖的各個頂點:);for (int v = 0; v vexNum; v+)/構造頂點向量構造頂點向量vexsv = sc.next(); 6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【 P19

34、9/算法算法6.2】無向網的創建算法無向網的創建算法private void createUDN() /定義鄰接矩陣定義鄰接矩陣 arcs = newintvexNumvexNum;/ 初始化鄰接矩陣初始化鄰接矩陣for (int v = 0; v vexNum; v+) for (int u = 0; u vexNum; u+) arcsvu = INFINITY;/初始為無窮大初始為無窮大6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【算法算法6.2】無向網的創建算法無向網的創建算法private void createUDN() /輸入邊信息輸入邊信息 System.out.

35、println(請輸入各個邊的兩個頂點及其權值請輸入各個邊的兩個頂點及其權值:); for (int k = 0; k arcNum; k+) int v = locateVex(sc.next(); /頂點頂點 int u = locateVex(sc.next(); /頂點頂點 arcsvu = arcsuv = sc.nextInt(); /權值權值 /算法算法6.2結束結束6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【算法算法6.2】無向網的創建算法無向網的創建算法createUDN()性性能分析能分析l初始化變量初始化變量l輸入圖中各頂點輸入圖中各頂點l定義鄰接矩陣定義

36、鄰接矩陣l輸入邊信息輸入邊信息l總的時間復雜度是總的時間復雜度是O(n2+n+e*n+1)=O(e*n)O(1)O(n)O(n2)O(e*n)6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣頂點定位算法頂點定位算法locateVex(vex) 操作要求：操作要求：根據頂點信息根據頂點信息vex，取得其在頂點數組中，取得其在頂點數組中的位置，若圖中無此頂點，則返回的位置，若圖中無此頂點，則返回-1問題：問題：如何確定查找？如何確定查找？解決：解決：遍歷頂點數組即可遍歷頂點數組即可6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【算法算法6.4】頂點定位算法頂點定位算法publ

37、icint locateVex(Object vex) /遍歷頂點數組遍歷頂點數組for (int v = 0; v vexNum; v+)if (vexsv.equals(vex)return v; return -1; /算法算法6.4結束結束/找到，返回位置找到，返回位置/未找到，返回未找到，返回-16.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣查找第一個鄰接點的算法查找第一個鄰接點的算法 firstAdjVex(v) 操作要求：操作要求： 返回返回v的第一個鄰接點，若的第一個鄰接點，若v沒有鄰接點沒有鄰接點則返回則返回-1，0vvexnum問題：問題：如何確定鄰接點？如何確

38、定鄰接點？6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣查找第一個鄰接點的算法查找第一個鄰接點的算法 firstAdjVex(v) 算法處理步驟：算法處理步驟：1、 判斷插入位置是否正確判斷插入位置是否正確2、遍歷鄰接矩陣第、遍歷鄰接矩陣第v行，查找是否有非行，查找是否有非0、非無窮大值元素、非無窮大值元素6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【算法算法6.5】查找第一個鄰接點的算法查找第一個鄰接點的算法publicint firstAdjVex(int v) throws Exception if (v = vexNum)thrownew Exception(

39、第第 + v + 個頂點不存在個頂點不存在!); /遍歷鄰接矩陣第遍歷鄰接矩陣第v行行 for (int j = 0; j vexNum; j+)if (arcsvj != 0&arcsvj INFINITY)return j;return -1;/算法算法6.5結束結束6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣查找下一個鄰接點的算法查找下一個鄰接點的算法 nextAdjVex(v,w) 操作要求：操作要求： 返回返回v相對于相對于w的下一個鄰接點，若的下一個鄰接點，若w是是v的最后一個鄰接點，則返回的最后一個鄰接點，則返回-1，其中，其中0v,wvexNum問題：問題

40、：如何確定鄰接點？如何確定鄰接點？6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣查找下一個鄰接點的算法查找下一個鄰接點的算法 nextAdjVex(v,w) 算法處理步驟：算法處理步驟：1、 判斷插入位置是否正確判斷插入位置是否正確2、從鄰接矩陣第、從鄰接矩陣第v行第行第W+1列開始遍歷列開始遍歷，查找是否有非，查找是否有非0、非無窮大值元素、非無窮大值元素6.2 圖的存儲結構圖的存儲結構6.2.1鄰接矩陣鄰接矩陣【算法算法6.6】查找下一個鄰接點的算法查找下一個鄰接點的算法publicint nextAdjVex(int v, int w) throws Exception if

41、 (v = vexNum) thrownew Exception(第第 + v + 個頂點不存在個頂點不存在!);/從從w+1開始遍歷第開始遍歷第v行行 for (int j = w + 1; j vexNum; j+) if (arcsvj != 0&arcsvj INFINITY) return j;return -1;/算法算法6.6結束結束6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表u 鄰接表鄰接表(Adjacency List）是圖的一種鏈式存儲方法是圖的一種鏈式存儲方法由一個順序存儲的頂點表和由一個順序存儲的頂點表和n個鏈式個鏈式存儲的邊表組成的存儲的邊表組成的頂

42、點表由頂點結點組成頂點表由頂點結點組成邊表是由邊邊表是由邊(或弧或弧)結點組成的一個單結點組成的一個單鏈表，表示所有依附于頂點鏈表，表示所有依附于頂點vi的邊（對于的邊（對于有向圖就是所有以有向圖就是所有以vi為始點的?。槭键c的?。?.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-無向圖無向圖無向圖無向圖對應的鄰接表某行上邊結點個數對應的鄰接表某行上邊結點個數 為該行表示結點的度為該行表示結點的度0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE6.2 圖的存儲結構圖的存儲結構1 96.2.2鄰接表鄰接表-無向網無向網ABEFDC2

43、927550 A1 B2 C3 D4 E5 F2 73 22 90 23 25 54 23 75 52 54 5如果如果無向圖（網）無向圖（網）中有中有e e條邊，則對應鄰條邊，則對應鄰 接表有接表有2e2e個邊結點個邊結點6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表datafirstArcadjVexvaluenextArc頂點結點頂點結點邊（或?。┙Y點邊（或?。┙Y點頂點信息第一個鄰結點與頂點相鄰接的點在圖中的位置與邊相關的信息，一般為權值（若不帶權圖，可以沒有此項）指向頂點的下一個邊結點6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-有向圖有向圖u 鄰接表：鄰接表：邊表表

44、示所有以邊表表示所有以vi為始點的弧。為始點的弧。0 1 2 3 41 4230 12 A B C D EABECD 在有向圖的鄰接表中不易找在有向圖的鄰接表中不易找到指向該頂點的弧。到指向該頂點的弧。有向圖有向圖對應的對應的鄰接鄰接表表某行上邊結點個數某行上邊結點個數為該結點的為該結點的出度出度6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-有向圖有向圖u 逆鄰接表：逆鄰接表：邊表表示所有以邊表表示所有以vi為終點的弧。為終點的弧。有向圖有向圖對應的對應的逆鄰接表逆鄰接表某行上邊結點某行上邊結點個數為該結點的個數為該結點的入度。入度。ABECDA B C D E 303420 012

45、3416.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-有向網有向網ABCD147640 A1 B2 C3 D0 62 43 71 12 4如果如果有向圖（網）有向圖（網）中有中有e e條邊，則對應鄰條邊，則對應鄰接表有接表有e e個邊結點個邊結點6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表u鄰接表與鄰接矩陣比較：鄰接表與鄰接矩陣比較：對于稀疏圖，鄰接表比鄰接矩陣節省存儲對于稀疏圖，鄰接表比鄰接矩陣節省存儲空間空間鄰接表上很容易找到任意一個頂點的鄰接鄰接表上很容易找到任意一個頂點的鄰接點和，但若要判定任意兩個鄰接點是否有邊點和，但若要判定任意兩個鄰接點是否有邊相連，則需遍歷單鏈

46、表，不如鄰接矩陣方便相連，則需遍歷單鏈表，不如鄰接矩陣方便6.2 圖的存儲結構圖的存儲結構例例1： 給出下圖的鄰接表和鄰接矩陣：給出下圖的鄰接表和鄰接矩陣：v4v1v2v3v50 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 2 3 41 3441 2 v1 v2 v3 v4 v50 21 30 26.2 圖的存儲結構圖的存儲結構例例2： 給出以下有向圖的給出以下有向圖的 1）鄰接矩陣）鄰接矩陣 2）每個頂點的入）每個頂點的入/出度；出度； 3）鄰接表及逆鄰接表）鄰接表及逆鄰接表 4）強連通分量）強連通分量2156436.2 圖的存儲結

47、構圖的存儲結構6.2.2鄰接表鄰接表-頂點結點類（頂點結點類（P201）public class VNode private Object data; / 頂點信息頂點信息private ArcNode firstArc; / 指向第一條依附于該頂點的弧指向第一條依附于該頂點的弧 public VNode() this(null, null);public VNode(Object data) this(data, null);public VNode(Object data, ArcNode firstArc) this.data = data;this.firstArc = firstAr

48、c;頂點結點頂點結點datafirstArc6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-邊結點類（邊結點類（P202）圖的鄰接表存儲表示中的邊圖的鄰接表存儲表示中的邊(或弧或弧)結點類描述：結點類描述：public class ArcNode / 該弧所指向的頂點位置該弧所指向的頂點位置private int adjVex;/ 邊邊(或弧或弧)的權值的權值private int value;/ 指向下一條弧指向下一條弧private ArcNode nextArc;邊（或弧）結點邊（或弧）結點adjVexvaluenextArc6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表

49、-邊結點類（邊結點類（P202）public class ArcNode public ArcNode() this(-1, 0, null);public ArcNode(int adjVex) this(adjVex, 0, null);public ArcNode(int adjVex, int value) this(adjVex, value, null);6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表-邊結點類（邊結點類（P202）public class ArcNode public ArcNode(int adjVex, int value, ArcNode nextA

50、rc) this.value = value;this.adjVex = adjVex;this.nextArc = nextArc;6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表頂點定位算法頂點定位算法locateVex(vex) 操作要求：操作要求：給定頂點的值給定頂點的值vex，返回其在圖中的位置，返回其在圖中的位置，若圖中不包含此頂點，則返回，若圖中不包含此頂點，則返回-1問題：問題：如何確定查找？如何確定查找？6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表頂點定位算法頂點定位算法locateVex(vex) 算法處理步驟：算法處理步驟：遍歷頂點數組即可遍歷頂點數組即可

51、6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表頂點定位算法頂點定位算法publicint locateVex(Object vex) /vexNum為頂點個數為頂點個數n /vexs為存放圖中各頂點的數組為存放圖中各頂點的數組for (int v = 0; v vexNum; v+)if (vexsv.getData().equals(vex)return v;return -1;6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表無向網的創建算法無向網的創建算法createUDN() 操作要求：操作要求：輸入的圖的頂點、邊及權值構造無向網輸入的圖的頂點、邊及權值構造無向網問題：問題

52、：鄰接表大??？鄰接表大?。咳绾紊擅恳粭l邊？如何生成每一條邊？6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表無向網的創建算法無向網的創建算法createUDN() 算法處理步驟：算法處理步驟：1、輸入頂點數和邊數、輸入頂點數和邊數2、構造頂點向量、構造頂點向量3、根據圖的邊數，確定輸入邊的數目、根據圖的邊數，確定輸入邊的數目4、根據輸入的每條邊生成邊結點，并在、根據輸入的每條邊生成邊結點，并在相應位置插入邊結點相應位置插入邊結點6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.7】無向網的創建算法無向網的創建算法private void createUDN() /初始

53、化變量初始化變量Scanner sc = new Scanner(System.in);System.out.println(請分別輸入圖的頂點數、圖請分別輸入圖的頂點數、圖的邊數的邊數:);vexNum = sc.nextInt(); /頂點數頂點數narcNum = sc.nextInt(); /邊數邊數e6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.7】無向網的創建算法無向網的創建算法private void createUDN() /輸入圖中各頂點輸入圖中各頂點vexs = new VNodevexNum;System.out.println(請分別輸入圖的各頂點

54、請分別輸入圖的各頂點:);/ 構造頂點向量構造頂點向量for (int v = 0; v vexNum; v+)vexsv = new VNode(sc.next();6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.7】無向網的創建算法無向網的創建算法private void createUDN() /輸入圖中各邊信息輸入圖中各邊信息System.out.println(請輸入各邊的頂點及其權值請輸入各邊的頂點及其權值:);for (int k = 0; k arcNum; k+) int v = locateVex(sc.next(); / 弧尾弧尾int u = loc

55、ateVex(sc.next(); / 弧頭弧頭int value = sc.nextInt();addArc(v, u, value); /加入邊加入邊addArc(u, v, value); /加入邊加入邊6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.7】無向網的創建算法性能分析無向網的創建算法性能分析l初始化變量初始化變量l輸入圖中各頂點輸入圖中各頂點l輸入圖中各邊信息輸入圖中各邊信息l總的時間復雜度是總的時間復雜度是O(n*e+n+1)=O(n*e)O(1)O(n)O(n*e)6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表在圖中插入邊在圖中插入邊(或弧或弧

56、)(v,u)結點的算法結點的算法 addArc(v, u, value) 操作要求：操作要求： 用鄰接表存儲圖時，將權值為用鄰接表存儲圖時，將權值為value的的邊（或?。┻叄ɑ蚧。?(v,u)插入圖中插入圖中問題：問題：如何確定插入位置？如何確定插入位置？6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表在圖中插入邊在圖中插入邊(或弧或弧)(v,u)結點的算法結點的算法 addArc(v, u, value) 算法處理步驟：算法處理步驟：1、 u為邊的為邊的終點終點，生成邊結點，生成邊結點2、 v為邊的為邊的起點起點，將邊結點，將邊結點插入插入頂點頂點v的的鏈表鏈表表頭表頭6.2 圖的存

57、儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.8】在圖中插入邊在圖中插入邊(或弧或弧)(v,u)結點的算法結點的算法public void addArc(int v, int u, int value) /u為邊的為邊的終點終點，生成邊結點，生成邊結點ArcNode arc = new ArcNode(u, value);/v為邊的為邊的起點起點，將邊結點，將邊結點插入插入頂點頂點v的鏈表的鏈表表頭表頭/取表頭取表頭arc.setNextArc(vexsv.getFirstArc();/生成新表頭生成新表頭vexsv.setFirstArc(arc);/算法算法6.8結束結束6.2 圖

58、的存儲結構圖的存儲結構6.2.2鄰接表鄰接表查找下一個鄰接點的算法查找下一個鄰接點的算法 nextAdjVex(v,w) 操作要求：操作要求： 返回返回v相對于相對于w的下一個鄰接點，若的下一個鄰接點，若w是是v的最后一個鄰接點，則返回的最后一個鄰接點，則返回-1，其中，其中0v,wvexNum問題：問題：如何確定鄰接點？如何確定鄰接點？6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表查找下一個鄰接點的算法查找下一個鄰接點的算法 nextAdjVex(v,w) 算法處理步驟：算法處理步驟：1、 判斷插入位置是否正確判斷插入位置是否正確2、取結點、取結點v 3、在鄰接表中查找結點、在鄰接表

59、中查找結點w 4、取、取w的下一結點的下一結點6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.6】查找下一個鄰接點的算法查找下一個鄰接點的算法publicint nextAdjVex(int v, int w) throws Exception if (v = vexNum)thrownew Exception(第第 + v + 個頂點不存在個頂點不存在!); /取結點取結點v VNode vex = vexsv; /用于取結點用于取結點v的鄰接點的鄰接點 ArcNode arcvw = null;6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.6】查找

60、下一個鄰接點的算法查找下一個鄰接點的算法publicint nextAdjVex(int v, int w) throws Exception for (ArcNode arc = vex.getFirstArc(); arc != null; arc = arc.getNextArc()if (arc.getAdjVex() = w) /取出結點取出結點warcvw = arc; break; 6.2 圖的存儲結構圖的存儲結構6.2.2鄰接表鄰接表【算法算法6.6】查找下一個鄰接點的算法查找下一個鄰接點的算法publicint nextAdjVex(int v, int w) throws Exception