數(shù)據(jù)結(jié)構主講人：楊丹常州信息職業(yè)技術學院5.1圖的概述圖是一種復雜的非線性結(jié)構。在圖結(jié)構中，對結(jié)點的前驅(qū)和后繼的個數(shù)沒有任何限制，結(jié)點之間的關系是任意的，圖中任意兩個結(jié)點之間都可能有關系，也就是說圖結(jié)點的關系是多對多的。引言IntroductionPart01圖的基本概念圖是由結(jié)點集合和結(jié)點間的關系集合組成的一種數(shù)據(jù)結(jié)構。記作：G=(V，E)其中，V={x│x∈某個數(shù)據(jù)元素集合}，E={(x,y)|x,y∈V}。V是有限的非空集合，V中的元素稱為頂點（Vertex）或結(jié)點，E是V中頂點偶對(x,y)的集合，E中的元素稱為邊（Edge）。圖說明圖的基本概念圖的基本概念5示例左圖中，頂點集合V＝{v1,v2,v3,v4,v5}；邊的集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}。無向圖與有向圖6無向圖

若圖G中的每條邊都是沒有方向的，則稱G為無向圖。無向圖中邊的表示：無向圖中的邊均是頂點的無序?qū)?，無序?qū)νǔＳ脠A括號表示，無序?qū)?x,y)和(y,x)表示圖中的同一條邊。無向圖若圖G中的每條邊都是有方向的，則稱G為有向圖。有向圖中邊的表示：有向圖中的邊是由頂點的有序?qū)M成，有序?qū)νǔＳ眉饫ㄌ柋硎?，有序?qū)?lt;x,y>和<y,x>表示的是圖中不同的邊。有向邊也稱為弧，邊的始點稱為弧尾，終點稱為弧頭。有向圖有向圖有向圖7示例左圖中，頂點集合V＝{v1,v2,v3,v4}；邊的集合E＝{<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。①若(x，y)或<y，x>是E(G)中的一條邊，則要求x≠y；②不允許一條邊在圖中重復出現(xiàn)；③不允許在同一個圖中既有有向邊又有無向邊。注意完全圖8無向圖

若G是具有n個頂點e條邊的無向圖，則頂點數(shù)與邊數(shù)的關系為0≤e≤n(n-1)/2。把恰有n(n-1)/2條邊的無向圖稱為無向完全圖。也就是說，在無向完全圖中，任意兩個頂點之間都有一條邊。無向完全圖有向圖完全圖9無向圖若G是具有n個頂點e條邊的有向圖，則頂點數(shù)與邊數(shù)的關系為0≤e≤n(n-1)。把恰有n(n-1)條邊的有向圖稱為有向完全圖。也就是說，在有向完全圖中，任意兩個頂點之間有方向相反的兩條邊。有向完全圖有向圖01無向邊和頂點若(x,y)是一條無向邊，則稱頂點x和y互為鄰接頂點，或稱x和y相鄰接；并稱(x,y)依附或關聯(lián)于頂點x和y，或稱(x,y)與頂點x和y相關聯(lián)。02有向邊和頂點若<x,y>是一條有向邊，則稱頂點x鄰接到y(tǒng)，頂點x鄰接于頂點y；并稱邊<x，y>關聯(lián)于x和y或稱<x,y>與頂點x和y相關聯(lián)。邊與頂點的關系度無向圖中頂點v的度無向圖中頂點v的度是關聯(lián)于該頂點的邊的數(shù)目，記為D(v)。有向圖頂點v的入度有向圖中，以頂點v為終點的邊的數(shù)目稱為v的入度，記為ID(v)。有向圖頂點v的出度有向圖中，以頂點v為始點的邊的數(shù)目，稱為v的出度，記為OD(v)。有向圖頂點v的度有向圖中，頂點v的度定義為該頂點的入度和出度之和，即D(v)=ID(v)+OD(v)。頂點的度無論有向圖還是無向圖，頂點數(shù)n、邊數(shù)e和度數(shù)之間有如下關系：頂點的度12無向圖有向圖D(v1)=2，D(v2)=3，D(v3)=3，D(v4)=2，D(v5)=2。ID(v1)=1，OD(v1)=2，D(v1)=3；ID(v2)=1，OD(v2)=0，D(v2)=1；ID(v3)=1，OD(v3)=1，D(v3)=2；ID(v4)=1，OD(v4)=1，D(v4)=2。路徑13無向圖在無向圖G中，若存在一個頂點序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均屬于E(G)，則稱該序列為頂點vp到vq的一條路徑。無向圖的路徑有向圖V3V1V2V4V5路徑14無向圖在有向圖G中，若存在一個頂點序列vp，vi1，vi2，…，vim，vq，使得有向邊<vp,vi1>，<vi1,vi2>，…，<vim,vq>均屬于E(G)，則稱該序列為頂點vp到vq的一條路徑。有向圖的路徑有向圖V1V2V4V3路徑15路徑長度定義為該路徑上邊的數(shù)目。起點和終點相同的路徑稱為回路。起點和終點相同的簡單路徑稱為簡單回路或簡單環(huán)。在一個有向圖中，若存在一個頂點v，從該頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為有根圖，v稱作圖的根。若一條路徑除兩端頂點可以相同外，其余頂點均不相同，則稱此路徑為一條簡單路徑。02030104子圖

無向圖和它的子圖有向圖和它的子圖連通圖和連通分量(a)無向圖(b)無向圖的兩個連通分量①任何連通圖的連通分量只有一個，即是其自身；②非連通的無向圖有多個連通分量。注意在無向圖G中，若從頂點x到頂點y有路徑，則稱x和y是連通的。若在無向圖G中，任意兩個不同的頂點x和y都連通(即有路徑)，則稱G為連通圖。無向圖G的極大連通子圖稱為G的連通分量。強連通圖和強連通分量有向圖G中，若對于V中任意兩個不同的頂點x和y，都存在從x到y(tǒng)以及從y到x的路徑，則稱G是強連通圖。有向圖的極大強連通子圖稱為G的強連通分量。(a)有向圖(b)有向圖的兩個連通分量①強連通圖只有一個強連通分量，即是其自身；②非強連通的有向圖有多個強連分量。注意網(wǎng)絡有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權。第i條邊的權用符號wi表示。權可以表示兩個頂點之間的距離、花費的代價、所需的時間等具有某種意義的數(shù)。若將圖的每條邊都賦上一個權，則稱這種圖為帶權圖，也稱為網(wǎng)絡。Part02圖的抽象數(shù)據(jù)類型描述及定義圖的抽象數(shù)據(jù)類型主要包括兩個方面：頂點集合和邊集合上的操作。圖上常見的操作有：插入頂點、插入邊、刪除邊、查找、獲取下一個鄰接點、深度遍歷、廣度遍歷等。圖的抽象數(shù)據(jù)類型描述及定義圖的抽象數(shù)據(jù)類型描述及定義T為泛型，表示圖中數(shù)據(jù)元素的數(shù)據(jù)類型。Java語言約定，T的實際參數(shù)必須是類，不能是int、double、char等基本