第6章圖主要內容6.1圖的定義和基本操作6.2圖的存儲表示6.3圖的遍歷6.4圖的連通性6.5最短路徑6.6有向無環圖及其應用小結2重難點（1）圖的存儲結構鄰接矩陣鄰接表逆鄰接表十字鏈表鄰接多重表——無向圖/無向網圖的遍歷算法深度優先遍歷DFS廣度優先遍歷BFS3無向圖/無向網有向圖/有向網有向圖/有向網重難點（2）求最小生成樹Prim算法Kruskal算法求單源最短路徑(Dijkstra算法)有向無環圖的應用對AOV網進行拓撲排序求AOE網的關鍵路徑46.1圖的定義和基本操作圖(Graph)是一種比樹形結構更復雜的非線性結構。在圖形結構中，每個結點都可以有多個直接前驅和多個直接后繼。圖G由兩個集合V和E組成，記為G＝(V,E)。其中，V是頂點的非空有限集；E是邊的有限集；邊是V中頂點的有序或無序偶對。56.1圖的定義和基本操作無向圖：如果每條邊都沒有方向，則稱該圖為無向圖。6邊(Vi,Vj)或(Vj,Vi)頂點Vi與Vj互為鄰接點G=(V,E)V={V1,V2,V3,V4}E={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4)}V1V3V4V2ViVj6.1圖的定義和基本操作有向圖：在一個圖中，如果每條邊都有方向，則稱該圖為有向圖。7弧<Vi,Vj>弧尾(起始點)Vj鄰接自Vi，Vj為Vi的鄰接點Vi鄰接到Vj，Vi為Vj的逆鄰接點弧頭(終端點)G=(V,E)V={V1,V2,V3,V4}E={<V1,V2>,<V2,V1>,<V1,V3>,<V4,V2>,<V1,V4>}V1V3V4V2ViVj6.1圖的定義和基本操作設圖中頂點數為n，邊數為e，則8有向圖：0≤e≤n(n-1)無向圖：0≤e≤n(n-1)/2

V1V3V4V2注意：在圖的定義中不包含重復邊和端點是同一個頂點的邊；V1VnViV2…………V1VnViV2…………6.1圖的定義和基本操作完全圖無向圖中，如果任意兩頂點都有一條直接邊相連，則稱該圖為無向完全圖。可以證明，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。有向完全圖：e=n(n-1)無向完全圖：e=n(n-1)/29V1V2V3V4V1V2V3V4e＝12e＝66.1圖的定義和基本操作稠密圖、稀疏圖邊數很多的圖為稠密圖；邊數很少的圖為稀疏圖。頂點的度在無向圖中，一個頂點擁有的邊數，稱為該頂點的度，記為TD(v)。頂點V的度TD(V)：關聯于頂點V的邊或弧的數目有向圖頂點V的入度ID(V)：以頂點V為弧頭的邊數有向圖頂點V的出度OD(V)：以頂點V為弧尾的邊數106.1圖的定義和基本操作一個頂點的度等于頂點的入度+出度，即：TD(v)=ID(v)＋OD(v)。11V1V3V2V4V5V1V3V2V4在圖G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在圖G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2無向圖G1有向圖G26.1圖的定義和基本操作

12

V1V3V2V4V5e=(2+3+3+2+2)/2=66.1圖的定義和基本操作帶權的圖稱之為網頂點帶權的圖，稱為AOV網(ActivityOnVertex)，每個頂點帶有相應的權值。邊(或弧)帶權的圖，一般稱為AOE網(ActivityOnEdge)，每條邊(或弧)帶有相應的權值。136V1V2V4V6V5V3310383141542有向帶權圖V1V3V4V2123875無向帶權圖6.1圖的定義和基本操作

14V1V3V2V4V56.1圖的定義和基本操作回路在一條路徑中，如果起始點和終止點是同一頂點，則稱其為回路或者環。簡單路徑如果一條路徑上，所有頂點除起始點和終止點外彼此都不同，則稱該路徑為簡單路徑。簡單回路除起始點和終止點外，其他頂點不重復出現的回路稱為簡單回路，或者簡單環。156.1圖的定義和基本操作子圖：設有兩個圖G=(V,E)，G’=(V’,E’),若V’V且E’E，則稱G’為G的子圖。16V1V3V4V2GV1V2G’G’’V1V4V2G’’’V16.1圖的定義和基本操作

17圖(a)圖(b)圖(c)6.1圖的定義和基本操作弱連通圖如果有向圖G去掉每條邊的方向后，得到的無向圖是連通的，則稱G是弱連通圖。單向連通圖如果G中任意兩個頂點之間至少一個可達另一個，則稱G是單向連通圖。18V1V3V4V2G6.1圖的定義和基本操作強連通如果Vi到Vj有路徑，Vj到Vi也有路徑，稱Vi到Vj是強連通的。強連通圖有向圖G中任意兩個頂點之間都是強連通的。強連通分量有向圖G的極大強連通子圖，稱為G的一個強連通分量。19V1V3V4V2G6.1圖的定義和基本操作有向圖G的連通性：強連通圖一定是單向連通圖；單向連通圖一定是弱連通圖。20V1V4V2V3強連通圖V1V4V2V3單向連通圖V1V4V2V3弱連通圖v1、v4無法到達6.1圖的定義和基本操作21非強連通圖G3G3的兩個強連通分量V1V3V4V2V1V3V4V2V3V1V4V26.1圖的定義和基本操作圖論中對樹的定義：無回路的連通圖22（n個頂點，n-1條邊）6.1圖的定義和基本操作無向連通圖的生成樹設G(V，E)是具有n個頂點的無向連通圖，G的生成樹是G的一個極小連通子圖，它包含了G的n個頂點及構成樹的n-1條邊。23V1V7V4V3V5V6V2V1V7V4V3V5V6V2V1V7V4V3V5V6V26.1圖的定義和基本操作無向連通圖的生成樹連通圖G的一個子圖，如果是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。所謂極小是指邊數最少。由于n個頂點的連通圖至少有n-1條邊，而所有包含n-1邊及n個頂點的連通圖都是無回路的樹，所以生成樹是無回路的樹。若在生成樹中去掉任何一條邊，都會使之變為非連通圖。若在生成樹上任意添加一條邊，就必定出現回路。246.1圖的定義和基本操作creatGraph(G)輸入圖G的頂點和邊，建立圖G的存儲。

dfsTraverse(G,v)在圖G中，從頂點v出發深度優先遍歷圖G。bfsTraverse(G,v)在圖G中，從頂點v出發廣度優先遍歷圖G。256.2圖的存儲表示圖的存儲圖中的頂點和邊，在內存中的表示形式；圖的存儲結構比較多，對于圖的存儲結構的選擇，取決于具體的應用和需要進行的運算。圖的常用存儲結構鄰接矩陣鄰接表逆鄰接表十字鏈表鄰接多重表——無向圖/無向網26無向圖/無向網有向圖/有向網有向圖/有向網6.2圖的存儲表示——鄰接矩陣

27

6.2圖的存儲表示——鄰接矩陣圖的鄰接矩陣存儲用一維數組vexs[N]，存放圖的頂點數據用矩陣edges[N][N]，存放圖中邊的信息，n為頂點數，e為邊數描述如下：28#defineN20//假設最大頂點數為20typedefcharVertexType;typedef

struct{

VertexType

vexs[N];

int

edges[N][N];

int

n,e;}AdjMatrix;6.2圖的存儲表示——鄰接矩陣無向圖的鄰接矩陣存放頂點的一維數組G.vexs=存放邊的矩陣(二維數組)G.edges=

290123456V1V2V3V4V5V6V7012345600111000110001112100000131000000401000105010010060110000V1V2V3V4V5V6V7V1V7V4V3V5V6V26.2圖的存儲表示——鄰接矩陣無向圖鄰接矩陣的特點：對稱矩陣頂點Vi的度等于第i行非零元個數，或第i列非零元個數：矩陣的非零元總數，等于邊數的2倍30

6.2圖的存儲表示——鄰接矩陣有向圖的鄰接矩陣存放頂點的一維數組G.vexs=存放弧的矩陣(二維數組)G.edges=

3101234567V1V2V3V4V5V6V7V801234567001110000100101100200000100300100110400000001500001010600000001700000000V4為弧尾V4為弧頭V1V7V4V3V5V6V2V86.2圖的存儲表示——鄰接矩陣

32

6.2圖的存儲表示——鄰接矩陣有向網的鄰接矩陣示例：3368314592ADCBG.edges=G.vexs=6.2圖的存儲表示——鄰接矩陣有向網的鄰接矩陣示例：34ABCD012301230∞1∞41∞∞92235∞83∞∞6∞G.edges=G.vexs=68314592ADCB6.2圖的存儲表示——鄰接表鄰接表鄰接表(AdjacencyList)是一種將順序存儲與鏈式存儲相結合的存儲方法鄰接表表示法類似于樹的孩子鏈表表示法，是圖最重要的存儲方法之一。在鄰接表表示中有如下兩種結點結構如果邊有權值，則邊結點的結構變為35圖的邊結點圖的頂點結點網的邊結點6.2圖的存儲表示——鄰接表鄰接表的結構體類型定義如下：36#defineN10//假設最大頂點數為10typedef

struct_EdgeNode{

intadjVex;

//鄰接頂點的下標

struct_EdgeNode*next;//指向下一個鄰接邊結點的指針}EdgeNode;

//定義邊結點類型typedef

struct{

VertexTypevertex;

//頂點標志或信息

EdgeNode*firstEdge;//保存第一個邊結點的地址}VertexNode;

//定義頂點結點類型typedef

struct{

VertexNodenodes[N];//頂點數組

int

n,e;

//頂點數和邊數}AdjList;

//定義鄰接表類型AdjList6.2圖的存儲表示——鄰接表鄰接表的結構體類型定義如下：37#defineN10//假設最大頂點數為10typedef

struct_EdgeNode{

intadjVex;

//鄰接頂點的下標

struct_EdgeNode*next;//指向下一個鄰接邊結點的指針}EdgeNode;

//定義邊結點類型typedef

struct{

VertexTypevertex;

//頂點標志或信息

EdgeNode*firstEdge;//保存第一個邊結點的地址}VertexNode,

AdjList[N];//定義頂點結點類型typedef

struct{

AdjListnodes;//頂點數組

int

n,e;

//頂點數和邊數}AdjList;

//定義鄰接表類型AdjList6.2圖的存儲表示——鄰接表C語言復習——數組類型的別名若有如下定義:typedefintIntArray[10];則:IntArrayb,c;完全等價于intb[10],c[10];38data0V11V22V33V44V55V66V789n7e86.2圖的存儲表示——鄰接表

39V1V7V4V3V5V6V2nodes1∧321∧5∧4∧601∧0645∧0∧21firstEdgeadjVexnextEdge邊結點的結構體6.2圖的存儲表示——鄰接表有向圖的鄰接表40V1V7V4V3V5V6V2V8data0V11V22V33V44V55V66V77V8∧8n8e14adjvexnextArc1∧32∧7∧6∧54firstArc54∧2∧726∧5nodes弧結點的結構體6.2圖的存儲表示——鄰接表

41data0V1∧1V22V33V44V55V66V77V88n8e146.2圖的存儲表示——鄰接表有向圖的逆鄰接表42nodes1∧32∧0∧5∧01firstArc01∧3∧53∧74V1V7V4V3V5V6V2V8adjVexnextArc邊結點的結構體6.2圖的存儲表示——鄰接表

436.2圖的存儲表示——鄰接表有向網的鄰接表44ADCB68314592data0A1B2C3D4n4e8nodesfirstArc1143∧9223∧305183∧62∧adjVexnextArcweight鄰接頂點的下標邊的權值下個弧結點的地址6.2圖的存儲表示——十字鏈表

45tailVexheadVexhLinktLinkweight十字鏈表的弧結點結構6.2圖的存儲表示——十字鏈表

46datafirstInfirstOut十字鏈表的頂點結點結構#defineN10typedef

struct_ArcNode{

inttailVex,headVex;

//弧尾和弧頭頂點的下標

struct_ArcNode*tLink;//指向同弧尾的下一個弧結點

struct_ArcNode*hLink;//指向同弧頭的下一個弧結點

intweight;

//弧的權值信息}ArcNode;

//定義弧結點的類型typedef

struct{

VertexTypevertex;//頂點標志或信息

ArcNode*firstIn;

//指向第一個弧頭結點

ArcNode*firstOut;//指向第一個弧尾結點}VexNode;

//定義頂點結點的類型typedef

struct{

VexNodenodes[N];

//頂點數組

int

vexNum,arcNum;//頂點數和弧數}OrthoList;

//定義十字鏈表的類型6.2圖的存儲表示——十字鏈表476.2圖的存儲表示——十字鏈表48弧頭頂點的下標弧尾頂點的下標弧尾頂點的下一個弧結點地址6.2圖的存儲表示——鄰接多重表無向圖鄰接表結構的缺點每條邊都存在兩個頂點，并且這兩個頂點分別位于兩個鏈表中，這給無向圖的某些操作帶來了不便。例如，當插入或刪除一條邊時，必須找到表示同一條邊的兩個邊結點，并分別對其操作，比較繁瑣。鄰接多重表(AdjacentMultiList)的每條邊都用一個邊結點表示，其邊結點和頂點結點的結構分別如圖所示。49鄰接多重表的邊結點結構鄰接多重表的頂點結點結構6.2圖的存儲表示——鄰接多重表50#defineN10typedef

struct_EdgeNode{

intiVex,jVex;

//邊兩端頂點的下標

struct_EdgeNode*iLink;//優先指向同iVex端點的下一個邊結點

struct_EdgeNode*jLink;//優先指向同jVex端點的下一個邊結點

doubleweight;

//邊的權值信息}EdgeNode;

//定義邊結點的類型typedef

struct{

VertexTypevertex;

//頂點標志

EdgeNode*firstEdge;//指向第一個鄰接邊結點的指針}VexNode;

//定義頂點結點的類型typedef

struct{

VexNodenodes[N];

//頂點數組

intvexNum,edgeNum;//頂點數和邊數}AdjMultiList;

//定義鄰接多重表的類型鄰接多重表的邊結點結構鄰接多重表的頂點結點結構6.2圖的存儲表示——鄰接多重表516.3圖的遍歷圖的遍歷從某一頂點出發，對圖中的所有頂點都訪問一次，而且只訪問一次。圖的(頂點)遍歷方法深度優先搜索DFS廣度優先搜索BFS526.3圖的遍歷圖的遍歷比較復雜，主要表現在四個方面：（1）圖中每個結點的地位都是相同的，沒有一個“自然”的起始結點，圖中任意一個頂點都可作為訪問的起始結點。（2）非連通圖中，從一個頂點出發，只能訪問它所在的連通分量上的所有頂點，因此需要考慮如何訪問圖中其余的連通分量。（3）如果有回路存在，一個頂點被訪問后，可能沿回路又訪問到該頂點，但是頂點不能重復訪問。（4）圖中一個頂點可以和其它多個頂點相連，當這個頂點訪問過后，要考慮如何選取下一個要訪問的頂點。536.3.1深度優先搜索(DFS)深度優先遍歷/搜索(Depth-FirstSearch,簡稱為DFS)，類似于樹的先根遍歷，是樹的先根遍歷的推廣。DFS的遍歷過程：從圖G中選某個頂點V作為出發點；訪問V；依次從V的尚未被訪問的鄰接點出發，調用遞歸函數深度優先遍歷圖G，直至與V相通的頂點都被訪問完；如果此時圖G中還有頂點未曾被訪問，則從這些未被訪問的頂點中，再選一個頂點V，轉2，繼續遍歷；否則遍歷結束。546.3.1深度優先搜索(DFS)55出發點DFS訪問序列：V1V2V5V6V7V3V4V1V7V4V3V5V6V26.3.1深度優先搜索(DFS)56出發點DFS訪問序列：V3V2V4V9V1V6V5V1V2V4V3V6V5V8V7V9V8V76.3.1深度優先搜索(DFS)DFS遍歷算法由于圖中可能存在回路，所以在遍歷時，可能會遇到已經被訪問過的頂點。為了避免同一個頂點被多次訪問，需要專門設置一個數組intvisited[N]，用于標記已經訪問過的頂點。visited[]數組的下標與頂點數組平行57visited[i]=

6.3.1深度優先搜索(DFS)基于鄰接表存儲結構，進行一次深度優先遍歷(遍歷一個連通分量)58voiddfs(AdjListg,intv,intvisited[]){

ArcNode*p;

intw;

visited[v]=1;

printf("%2c",g.nodes[v].data);//訪問v

p=g.nodes[v].firstArc;

//p先指向v后鏈表中的第一個結點

while(p!=NULL)

{

w=p->adjVex;

//用w保存鄰接頂點的下標

if(0==visited[w])

//如果w號頂點尚未訪問

dfs(g,w,visited); //則以w為起始，遞歸

p=p->next;

}}6.3.1深度優先搜索(DFS)基于鄰接表存儲結構，深度優先搜索遍歷整個圖g59調用dfs一次，只能訪問到與v有路徑相通的所有頂點。voiddfsTraverse(AdjListg){

intvisited[V_MAX]={0};//頂點的訪問標志全部設為0

intv;

for(v=0;v<g.vexNum;v++)

{

//若頂點v尚未訪問，則以v為起始，調用遞歸函數dfs()

if(0==visited[v])

dfs(g,v,visited);

}}6.3.1深度優先搜索(DFS)60出發點DFS訪問序列：V1V9V7V2V5V6V4datafirstArcV8V387V76V65V54V43V92V21V108∧311∧5054∧6∧41∧81∧60∧7∧0∧2V3V8V1V7V4V9V5V6V2V8V3nodes6.3.1深度優先搜索(DFS)61datafirstArc8∧V87V76V65V54V43V32V21V101∧32∧7∧524∧5∧64∧725∧6nodesDFS訪問序列：V1V2V3V6V5V8V7V4出發點V1V7V4V3V5V6V2V86.3.1深度優先搜索(DFS)

626.3.2廣度優先遍歷BFS廣度優先遍歷BFS，類似于樹的層次遍歷。BFS的遍歷過程：從圖g的某個頂點v出發，訪問v；依次訪問v的未被訪問的所有鄰接點；再按照“先被訪問頂點的鄰接點先訪問”的次序，依次訪問這些鄰接點的鄰接點，直至圖中所有已被訪問頂點的鄰接點都被訪問到；如果圖中還有頂點未曾被訪問，則另選一個未被訪問的頂點v作為出發點，重復上述過程，直至圖中所有的頂點都被訪問完。636.3.2廣度優先遍歷BFS64BFS訪問序列：V3V2V1V6V4V5V9V8V7V1V2V4V3V6V5V8V7V96.3.2廣度優先遍歷BFS65BFS訪問序列：V1V2V4V5V6V7V8出發點V3V1V7V4V3V5V6V2V8datafirstArc8∧V87V76V65V54V43V32V21V101∧32∧7∧524∧5∧64∧725∧6nodes6.3.1廣度優先搜索(BFS)基于鄰接表存儲結構，進行廣度優先遍歷66voidbfsTraverse(AdjListg)//4--廣度優先遍歷{

SeqQueuequeue;

intvisited[V_MAX]={0};//頂點的訪問標志全部設為0

ArcNode*p;

intv,u=-1,w;

initQueue(queue);//初始化隊列為空

for(v=0;v<g.vexNum;v++)

{

//如果頂點v尚未訪問，則先訪問并標記，并將其進隊

if(0==visited[v])

{

printf("%2c",g.nodes[v].data);//訪問

visited[v]=1;

//標記

inQueue(queue,v);

//進隊

while(!queueIsEmpty(queue))//如果隊列不為空

{

//出隊一個元素給u，然后訪問和u鄰接的所有頂點

outQueue(queue,u);

//p先指向u之后弧結點鏈表中的第一個弧結點

p=g.nodes[u].firstArc;

while(p!=NULL)

{

w=p->adjVex;//w為鄰接頂點的下標

//若w尚未訪問，則訪問并標記，并將其進隊

if(0==visited[w])

{

//先訪問w，將其標記為已訪問并進隊

printf("%2c",g.nodes[w].data);

visited[w]=1;

inQueue(queue,w);

}

p=p->next;

}

}}

}

}

//

endif//

end

for

//

endbfsTraverse6.3.2廣度優先遍歷BFS廣度優先遍歷(BFS)的分析每個頂點至多進一次隊列。遍歷的過程，實質是通過邊或弧找鄰接點的過程。廣度優先遍歷(BFS)和深度優先遍歷(DFS)兩者的時間復雜度是相同的；兩者不同之處僅僅在于對頂點訪問的順序不同。686.4圖的連通性無向圖的連通分量和生成樹在對無向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發，進行深度優先或廣度優先搜索，便可訪問到圖中所有頂點。對非連通圖，則需從多個頂點出發進行搜索，每次從一個新的起始點出發進行搜索，得到的頂點訪問序列，恰為各個連通分量的頂點集。696.4圖的連通性70AEBFCD兩次調用DFS（分別從頂點A和頂點D出發），得到的頂點訪問序列為：ABFE和D

C。這兩個頂點集合分別加上所有依附于這些頂點的邊，便構成了上述非連通圖的兩個連通分量。6.4圖的連通性判定一個無向圖是否為連通圖，或有幾個連通分量，可設一個計數變量count，初始時取值為0，在深度優先遍歷算法中，每調用一次DFS，就給count增1。當整個算法結束時，依據count的值，就可確定圖的連通性。設E(G)為連通圖G中所有邊的集合，則從圖中任一頂點出發遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點一起構成連通圖G的極小連通子圖。716.4圖的連通性——連通圖的生成樹由深度優先搜索得到的為深度優先生成樹；由廣度優先搜索得到的為廣度優先生成樹。72V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7無向連通圖廣度優先生成樹深度優先生成樹6.4圖的連通性——非連通圖的生成森林對于非連通圖，通過遍歷，將得到生成森林。73非連通無向圖深度優先生成樹林JHKLMAICFGBDEHKIGJLMACFBDE6.4圖的連通性——最小生成樹最小生成樹的基本概念由生成樹的定義可知，無向連通圖的生成樹不一定是唯一的。連通圖的一次遍歷所經過的邊及圖中所有頂點，構成該圖的一棵生成樹。連通圖的不同遍歷，可能得到不同的生成樹。74V1V5V2V4V8V3V6V7無向連通圖V1V5V2V4V8V3V6V7生成樹AV1V5V2V4V8V3V6V7生成樹B6.4圖的連通性——最小生成樹可以證明：有n個頂點的無向連通圖，無論其生成樹的形態如何，所有生成樹都有且僅有n-1條邊。最小生成樹如果無向連通圖是一個邊帶權值的網，那么它的所有生成樹中至少存在一棵邊的權值之和最小的生成樹，簡稱為最小生成樹。756.4圖的連通性——最小生成樹最小生成樹可以用于解決許多實際問題。例如：以盡可能低的總價建造城市間的通訊網絡，把若干個城市連接在一起。在這些城市中，任意兩個城市之間都可以建造通訊線路，通訊線路的造價依據城市之間的距離不同，而有不同的造價。可以構造一個通訊線路造價網，用每個頂點表示一個城市，頂點之間的邊表示城市之間的通訊線路，邊的權值表示該條通訊線路的造價，要使總的造價最低，實際上就是尋找該網的最小生成樹。766.4圖的連通性——最小生成樹最小(代價)生成樹n個頂點構成的無向網的所有生成樹中，n-1條邊的權值之和最小的生成樹。構造最小生成樹的著名算法Prim算法(普里姆算法)Kruskal算法(克魯斯卡爾算法)776.4圖的連通性——Prim算法求最小生成樹普里姆(Prim)算法的基本思想：從連通的帶權圖G={V,E}中的某一頂點z出發，將頂點z加入到生成樹的頂點集合U中。未加入到U集合的頂點，構成集合W=V－U。從集合U選取一個頂點u，從集合W中選取一個頂點w。從跨越兩個集合的所有邊(u,w)中，選擇一條權值最小的邊(x,y)，并把對應的頂點也加入到集合U中。如此繼續下去，直到帶權圖中的所有頂點都加入到生成樹的頂點集合U中為止。786.4圖的連通性——Prim算法求最小生成樹從頂點A出發構造最小生成樹與頂點A

關聯的候選邊有兩條，權值小的邊是(A,F)10，選取它及頂點F

加入到最小生成樹。與頂點A、F

關聯的候選邊有兩條，權值小的是(F,E)25，選取它及頂點E

加入到最小生成樹。79FAEGBDC281025142422161812FAEGBDC281025142422161812FAEGBDC2810251424221618126.4圖的連通性——Prim算法求最小生成樹繼續從指定范圍中選取權值最小的邊及其頂點與頂點A、F、E關聯的候選邊有三條，權值小的是(E,D)22，選取它并將頂點D

加入最小生成樹。與頂點A、F、E、D關聯的候選邊有四條，權值最小的是(D,C)12，選取它并將頂點C加入最小生成樹。80FAEGBDC281025142422161812FAEGBDC281025142422161812FAEGBDC2810251424221618126.4圖的連通性——Prim算法求最小生成樹繼續從指定范圍中選取權值最小的邊及其頂點與頂點A、F、E、D、C關聯的候選邊有四條，權值小的邊為(B,C)16，選取它并將頂點B

加入生成樹。與頂點A、F、E、D、C、B關聯的候選邊有四條，權值最小的是(B,G)14，選取它及頂點G加入最小生成樹。81FAEGBDC281025142422161812FAEGBDC102514242216181228FAEGBDC2810251424221618126.4圖的連通性——Prim算法求最小生成樹從n個頂點的圖中，選取到第n-1條邊時停止所有頂點A、F、E、D、C、B、G均已加入最小生成樹，算法完成，7個頂點的圖共需選取6次（每次選擇一條邊的同時，選取那個對應的頂點）。每次為了在候選邊中選取權值最小的邊，算法可以使用一個小根堆，把當前的候選邊放在堆內，每次從堆中取出的一定是權值最小的候選邊，可以提高效率。82FAEGBDC102514221612FAEGBDC281025142422161812FAEGBDC1025142422161812286.4圖的連通性——Prim算法求最小生成樹按Prim算法，選取各條邊的順序：(A,F)10(F,E)25(E,D)22(D,C)12(C,B)16(B,G)1483FAEGBDC281025142422161812FAEGBDC1025142216126.4圖的連通性——Prim算法求最小生成樹846.4圖的連通性——克魯斯卡爾(Kruskal)算法求最小生成樹Kruskal算法的基本思想設有一個有n

個頂點的連通帶權圖G={V,E}先將邊集E中所有的邊，按權值從小到大排序。然后從權值小的邊開始，依次選取各條邊；選取每條邊后，都要先判斷所選邊是否會讓頂點構成環。如果會構成環，則放棄該條邊；退而求其次，選取下一條權值稍大的邊。如此重復下去，直到選取的邊數達到n-1條。856.4圖的連通性——克魯斯卡爾(Kruskal)算法求最小生成樹8610FAEGBDC(a)1210FAEGBDC(b)16121410FAEGBDC(d)2216141210FAEGBDC(e)FAEGBDC101412(c)22FAEGBDC2810251424161812(原圖)6.4圖的連通性——克魯斯卡爾(Kruskal)算法求最小生成樹按Kruskal算法，選取各條邊的順序：(A,F)10(D,C)12(B,G)14(C,B)16(E,D)22(F,E)2587FAEGBDC281025142422161812原圖FAEGBDC102514221612(f)最小生成樹6.4圖的連通性——克魯斯卡爾(Kruskal)算法求最小生成樹886.5最短路徑最短路徑問題是圖的比較典型的應用例如，某一地區的一個交通網，給定了該網內的n個城市以及這些城市之間公路的距離，問題是如何在城市A和城市B之間找一條最近的通路。如果將城市用頂點表示，城市間的公路用邊表示，公路的長度作為邊的權值，那么，這個問題就可歸結為在網中，求點A到點B的所有路徑中，邊的權值之和最短的那一條路徑。這條路徑就稱為兩點之間的最短路徑，并稱路徑上的第一個頂點為源點(source)，最后一個頂點為終點(destination)。896.5最短路徑以V1為源點的路徑舉例V1到V2的路徑有1條：V1→V2(20)V1到V3的路徑有2條：V1→V3(15)V1→V2→V3(55)V1到V4的路徑有3條：V1→V2→V4(30)V1→V3→V4(45)V1→V2→V3→V4(85)V1到V5的路徑有2條：V1→V2→V3→V5(65)V1→V3→V5(25)90V1V5V2V4V32010351015306.5最短路徑——Dijkstra算法單源最短路徑從帶權有向圖G(E,V)中，找出從給定源頂點s到所有其它頂點v的最短路徑。最短路徑==路徑上所有邊的權值之和最小單源，例如從上海到全國所有其它大中城市。Dijkstra算法的核心要點：最終求出的是：某頂點到其它所有頂點的n-1條最短路徑；求解過程：按n-1條最短路徑遞增的次序。91

6.5最短路徑——Dijkstra算法單源最短路徑92目標頂點

i=1i=2i=3v1

v210(v0,v2)v3

60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,

v5)60(v0,v4,v3,

v5)S{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}20v5v4v0100601010v1v35030v26.5最短路徑——Dijkstra算法單源最短路徑Dijkstra算法：設置數組dist，其中每個分量dist[i]表示當前所求得的從源點到其余各頂點i的最短路徑的長度。一般情況下dist[k]=<源點到頂點i的弧的權值>或者dist[k]=<源點到其它頂點的路徑長度>+<其它頂點到頂點i的弧上的權值>936.5最短路徑——Dijkstra算法單源最短路徑在所有從源點出發的弧中，選取一條權值最小的弧，即為第一條最短路徑。dist中的最小值，即為最短路徑的長度。修改其它各頂點的dist[i]值。假設求得最短路徑的頂點為u，若dist[u]+g.arcs[u][i]<dist[i]則將dist[i]改為dist[u]+g.arcs[u][i]94

6.6有向無環圖及其應用一個不存在環的有向圖，稱為有向無環圖(DirectedAcyclineGraph)，簡稱為DAG圖。幾乎所有工程，都可分為若干個稱為活動的子工程，這些子工程之間，通常受著一定條件的約束。比如其中某些子工程的開始，必須在另一些子工程完成之后。956.6有向無環圖及其應用對于整個工程，人們往往最關心兩個方面：一是工程能否順利進行；二是估算完成整個工程所必須的最短時間。其中前一個就是有向圖能否拓撲排序的問題，后一個則和關鍵路徑有關。96補充：離散數學中的關系及其性質什么是“關系”(Relation)假設有一個集合X(通俗地說就是一類東西)，某些元素之間(例如x、y之間)有某一種關系R，則記為R(x,y)。這個關系可以是“x和y認識”，或者“x比y大”，或者“x包含y”，或者是任意你說了算的關系，你說有關系就有關系。97補充：離散數學中的關系及其性質自反性對于集合X的任意元素x、必有R(x,x)。因為一般語境下的“關系”是兩個對象，所以這個概念不太直觀。舉例，比如X=班級，x=小明，R=同班；那么小明一定和自己同班，所以R(x,x)。98補充：離散數學中的關系及其性質反自反性就是任意元素x，不滿足R(x,x)。如果關系R是“我是你爸爸”，那么顯然任意的x都不是自己的爸爸；因此關系“我是你爸爸”滿足反自反的性質。99補充：離散數學中的關系及其性質對稱性如果R(x,y)，則R(y,x)。還是“同班”的例子，“我是你同學”意味著“你是我同學”；結婚，我和你結婚，你必然和我結婚等。這里“意味著”就是推導。100補充：離散數學中的關系及其性質反對稱性如果R(x,y)，則R(y,x)不成立。例如“我是你爸爸”就滿足反對稱，因為“我是你爸爸”，肯定不意味著“你是我爸爸”。101補充：離散數學中的關系及其性質傳遞性如果R(x,y)和R(y,z)，則R(x,z)。比如“同班”這個(特定班級，不是“同過班”)關系，就具備傳遞性。再比如“直系血親”就是傳遞的，比如爸爸的爸爸是爺爺。102補充：離散數學中的關系及其性質不傳遞性（注意，不是反傳遞）很多關系都不滿足傳遞性，例如“朋友”，“我是你爸爸”，“接過吻”等都不滿足傳遞性。如果一個關系滿足“反身，對稱，傳遞”，那么這個關系就叫“等價關系”，也就是“分類關系”。也可以反過來理解，所有“分類關系”必然滿足“反身，對稱，傳遞”。1036.6.1拓撲排序在離散數學課程中關于偏序關系和全序關系有如下定義：若集合S上的關系R是自反的、反對稱的和可傳遞的，則稱R是集合S上的偏序關系。設關系R是集合S上的偏序(PartialOrder)，如果對每個R，必有xRy或yRx，則稱R是集合S上的全序關系。偏序指集合中僅有部分成員之間存在關系，全序指集合中的全部成員之間均存在關系。比如集合之間的包含關系，就是一個偏序關系；因為并不是任何兩個集合之間都存在包含關系。1046.6.1拓撲排序拓撲排序是有向圖的一個重要操作。拓撲序列、拓撲排序：在有向圖G中，若從頂點A到頂點B有一條路徑，則在某線性序列中頂點A必定在頂點B之前，則稱這個線性序列為一個拓撲序列。求一個有向圖拓撲序列的過程，稱為拓撲排序(TopologicalSort)實質上，拓撲排序是由某個集合上的偏序關系得到該集合上的一個全序關系的過程。1056.6.1拓撲排序偏序和全序關系舉例106B和C之間不可比較A、B、C、D之間均可比較(a)偏序關系(b)全序關系6.6.1拓撲排序——AOV網偏序關系的有向圖，可用來表示任務的流程。可能是施工的流程，或者是生產產品的流程。圖中每條有向邊表示兩個子工程完成的先后次序。這種用頂點表示活動，用弧表示活動之間優先關系的有向圖，稱為頂點為活動的網(ActivityOnVertex)，簡稱AOV網。1076.6.1拓撲排序——AOV網在AOV網中，不應該出現有向環如果存在環，則意味著某項活動以自己為先決條件；如果這樣，只能說明該活動無法完的，整個工程也是無法完成的。因此，對AOV網應首先判定是否存在環，如果不存在環，則可以進行拓撲排序，得到相應的拓撲序列，反之，則不能得到拓撲序列。1086.6.1拓撲排序——拓撲排序的應用109課程代號課程名稱先修課程C1高等數學C2程序設計基礎C3離散數學C1,C2C4數據結構C3,C2C5高級語言程序設計C2C6編譯方法C5,C4C7操作系統C4,C9C8普通物理C1C9計算機原理C86.6.1拓撲排序——拓撲排序的應用對課程進行拓撲排序，得到如下拓撲序列C1,C2,C3,C4,C5,C6,C8,C9,C7C1,C8,C9,C2,C5,C3,C4,C7,C6課程關系圖110C8C3C5C4C9C6C7C1C26.6.1拓撲排序拓撲排序示例11