數(shù)據(jù)結(jié)構(gòu)圖課件

7.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲表示7.3圖的遍歷7.4最小生成樹7.5重（雙）連通圖和關節(jié)點7.6兩點之間的最短路徑問題7.7拓撲排序7.8關鍵路徑7.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲表示7.3圖的1圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x某個數(shù)據(jù)對象}

是頂點的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條單向通路,它是有方向的。圖的基本概念圖定義圖是由頂點集合(vertex)及頂點2

有向圖與無向圖在有向圖中，頂點對<x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖若有

n個頂點的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有

n個頂點的有向圖有n(n-1)條邊,則此圖為完全有向圖。00001111222265433有向圖與無向圖在有向圖中，頂點對<x,y>3

鄰接頂點如果

(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖設有兩個圖G＝(V,E)和G'＝(V',E')。若V'V且E'E,則稱圖G'是圖G的子圖。權(quán)某些圖的邊具有與它相關的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡。子圖01230130123023鄰接頂點如果(u,v)是E(G)中的一4頂點的度一個頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數(shù),記作

ID(v);頂點v的出度是以v為始點的有向邊的條數(shù),記作

OD(v)。路徑在圖G＝(V,E)中,若從頂點

vi

出發(fā),沿一些邊經(jīng)過一些頂點

vp1,

vp2,…,

vpm，到達頂點vj。則稱頂點序列

(vi

vp1vp2...vpm

vj)

為從頂點vi到頂點

vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。頂點的度一個頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(5路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑若路徑上各頂點v1,v2,...,vm

均不互相重復,則稱這樣的路徑為簡單路徑。回路若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。012301230123路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的6連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。生成樹一個連通圖的生成樹是其極小連通子圖，在n個頂點的情形下，有

n-1條邊。連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有7

圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，VR＝{<v,w>|v,w∈V且P(v,w)}

<v,w>表示從v到w的一條弧，并稱v為弧頭，w為弧尾。

謂詞P(v,w)定義了弧<v,w>的意義或信息。圖的結(jié)構(gòu)定義:圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。8

由于“弧”是有方向的，因此稱由頂點集和弧集構(gòu)成的圖為有向圖。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}由于“弧”是有方向的，因此稱由頂點集和弧集構(gòu)成的圖為有向9若<v,w>VR必有<w,v>VR,則稱(v,w)為頂點v和頂點w之間存在一條邊。

BCADFE由頂點集和邊集構(gòu)成的圖稱作無向圖。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={<A,B>,<A,E>,<B,E>,<C,D>,<D,F>,<B,F>,<C,F>}若<v,w>VR必有<w,v>VR,10名詞和術(shù)語網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林名詞和術(shù)語網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點、11ABECFAEABBC設圖G=(V,{VR})和圖G=(V,{VR}),且VV,VRVR,則稱G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。ABECFAEABBC設圖G=(V,{VR})和圖G=12假設圖中有

n

個頂點，e

條邊，則

含有e=n(n-1)/2條邊的無向圖稱作完全圖；

含有e=n(n-1)條弧的有向圖稱作

有向完全圖；若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。假設圖中有n個頂點，e條邊，則含有e=n(n-113

假若頂點v和頂點w之間存在一條邊，則稱頂點v和w互為鄰接點，ACDFE例如:ID(B)=3ID(A)=2邊(v,w)

和頂點v和w相關聯(lián)。

和頂點v關聯(lián)的邊的數(shù)目定義為邊的度。B假若頂點v和頂點w之間存在一條邊，ACDFE例如:I14頂點的出度:以頂點v為弧尾的弧的數(shù)目；ABECF對有向圖來說，頂點的入度:以頂點v為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3頂點的出度:以頂點v為弧尾的弧的數(shù)目；ABECF對有向圖來15設圖G=(V,{VR})中的一個頂點序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,則稱從頂點u到頂點w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。ABECF如:長度為3的路徑{A,B,C,F}簡單路徑:序列中頂點不重復出現(xiàn)的路徑。簡單回路:序列中第一個頂點和最后一個頂點相同的路徑。設圖G=(V,{VR})中的一個頂點序列ABECF如:長度為16若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖；若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖；若無17

若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。ABECFABECF對有向圖，否則，其各個強連通子圖稱作它的強連通分量。若任意兩個頂18

假設一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE假設一個連通圖有n個頂點和e條邊，其中n-119結(jié)構(gòu)的建立和銷毀插入或刪除頂點對鄰接點的操作對頂點的訪問操作遍歷插入和刪除弧基本操作結(jié)構(gòu)的建立和銷毀插入或刪除頂點對鄰接點的操作對頂點的訪問操作20CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀CreatGraph(&G,V,VR):DestroyG21對頂點的訪問操作LocateVex(G,u);

//若G中存在頂點u，則返回該頂點在//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。對頂點的訪問操作LocateVex(G,u);GetV22對鄰接點的操作FirstAdjVex(G,v);

//返回v的“第一個鄰接點”。若該頂點//在G中沒有鄰接點，則返回“空”。NextAdjVex(G,v,w);

//返回v的（相對于w的）“下一個鄰接//點”。若w是v的最后一個鄰接點，則//返回“空”。對鄰接點的操作FirstAdjVex(G,v);Next23插入或刪除頂點InsertVex(&G,v);

//在圖G中增添新頂點v。DeleteVex(&G,v);//刪除G中頂點v及其相關的弧。插入或刪除頂點InsertVex(&G,v);Delet24插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無向的，//則還增添對稱弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無向的，//則還刪除對稱弧<w,v>。插入和刪除弧InsertArc(&G,v,w);Del25遍歷DFSTraverse(G,v,Visit());//從頂點v起深度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。遍歷DFSTraverse(G,v,Visit()267.2圖的存儲表示一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示7.2圖的存儲表示一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖27Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲表示BACDFE定義:矩陣的元素為Aij={0(i,j)VR1(i,j)VR一、圖28有向圖的鄰接矩陣為非對稱矩陣ABECF有向圖的鄰接矩陣為非對稱矩陣ABECF29typedefstructArcCell{//弧的定義VRTypeadj;//VRType是頂點關系類型。//對無權(quán)圖，用1或0表示相鄰否；//對帶權(quán)圖，則為權(quán)值類型。InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstructArcCell{//弧的30typedefstruct{//圖的定義VertexType//頂點信息vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點數(shù)，弧數(shù)GraphKindkind;//圖的種類標志

}MGraph;typedefstruct{//圖的定義310A141B0452C353D254E015F123BACDFE二、圖的鄰接表存儲表示0A14BACDFE二、圖的32142301201234ABCDE有向圖的鄰接表ABECF可見，在有向圖的鄰接表中不易找到指向該頂點的弧BECD有向圖的逆鄰接表ABCDE30342001234在有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。ABECD有向圖的逆鄰接表A303420034typedefstructArcNode{

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

structArcNode*nextarc;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關信息的指針}ArcNode;adjvexnextarcinfo弧的結(jié)點結(jié)構(gòu)typedefstructArcNode{adjv35typedefstructVNode{

VertexTypedata;//頂點信息ArcNode*firstarc;//指向第一條依附該頂點的弧

}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc頂點的結(jié)點結(jié)構(gòu)typedefstructVNode{data36typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標志}ALGraph;圖的結(jié)構(gòu)定義typedefstruct{圖的結(jié)構(gòu)定義37三、有向圖的十字鏈表存儲表示

弧的結(jié)點結(jié)構(gòu)弧尾頂點位置弧頭頂點位置弧的相關信息指向下一個有相同弧尾的結(jié)點指向下一個有相同弧頭的結(jié)點typedefstructArcBox{//弧的結(jié)構(gòu)表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}VexNode;三、有向圖的十字鏈表存儲表示弧的結(jié)點結(jié)構(gòu)弧尾頂點位置弧頭38頂點的結(jié)點結(jié)構(gòu)頂點信息數(shù)據(jù)指向該頂點的第一條入弧指向該頂點的第一條出弧typedefstructVexNode{//頂點的結(jié)構(gòu)表示VertexTypedata;ArcBox*firstin,*firstout;}VexNode;頂點的結(jié)點結(jié)構(gòu)頂點信息數(shù)據(jù)指向該頂點39typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//頂點結(jié)點(表頭向量)

intvexnum,arcnum;//有向圖的當前頂點數(shù)和弧數(shù)}OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)typedefstruct{有向圖的結(jié)構(gòu)表示(十字鏈表40四、無向圖的鄰接多重表存儲表示typedefstructEbox{VisitIfmark;//訪問標記

intivex,jvex;//該邊依附的兩個頂點的位置

structEBox*ilink,*jlink;InfoType*info;//該邊信息指針}EBox;邊的結(jié)構(gòu)表示四、無向圖的鄰接多重表存儲表示typedefstruct41typedefstruct{//鄰接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;頂點的結(jié)構(gòu)表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;無向圖的結(jié)構(gòu)表示typedefstruct{//鄰接多重表頂點的結(jié)427.3圖的遍歷

從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索遍歷應用舉例7.3圖的遍歷從圖中某個頂點出發(fā)游歷圖，訪43深度優(yōu)先搜索DFS

(DepthFirstSearch)深度優(yōu)先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前進回退深度優(yōu)先搜索過程深度優(yōu)先生成樹深度優(yōu)先搜索DFS(DepthFirstSearch)44DFS

在訪問圖中某一起始頂點v

后,由

v

出發(fā),訪問它的任一鄰接頂點

w1;再從w1出發(fā),訪問與w1鄰

接但還沒有訪問過的頂點w2;然后再從w2出發(fā),進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。DFS在訪問圖中某一起始頂點v后,由v出發(fā),45圖的深度優(yōu)先搜索算法template<classT,classE>voidDFS(Graph<T,E>&G,constT&v){//從頂點v出發(fā)對圖G進行深度優(yōu)先遍歷的主過程inti,loc,n=G.NumberOfVertices();//頂點個數(shù)bool*visited=newbool[n];//創(chuàng)建輔助數(shù)組 for(i=0;i<n;i++)visited

[i]=false;

//輔助數(shù)組visited初始化

loc=G.getVertexPos(v);

DFS(G,loc,visited);//從頂點0開始深度優(yōu)先搜索 delete[]visited; //釋放visited};圖的深度優(yōu)先搜索算法template<classT,cl46template<classT,classE>voidDFS(Graph<T,E>&G,intv,boolvisited[]){cout<<G.getValue(v)<<'';//訪問頂點v

visited[v]=true; //作訪問標記intw=G.getFirstNeighbor(v);//第一個鄰接頂點 while(w!=-1){ //若鄰接頂點w存在 if(!visited[w])DFS(G,w,visited);

//若w未訪問過,遞歸訪問頂點w

w=G.getNextNeighbor(v,w);//下一個鄰接頂點}};template<classT,classE>47廣度優(yōu)先搜索BFS

(BreadthFirstSearch)廣度優(yōu)先搜索的示例廣度優(yōu)先搜索過程廣度優(yōu)先生成樹ACDEGBFIHACDEGBFH123456789123456789I廣度優(yōu)先搜索BFS(BreadthFirstSearc48BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優(yōu)先搜索那樣有往回退的情況。因此,廣度優(yōu)先搜索不是一個遞歸的過程。BFS在訪問了起始頂點v之后,由v出發(fā),依次訪問49

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

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

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

若該鄰接點W未被訪問，

則從它出發(fā)進行深度優(yōu)先搜索遍歷。w2w3w2Vw1SG1SG2SG3W1、W2和W3均為V的鄰接點51從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點設立一個“訪問標志visited[w]”。2.如何判別V的鄰接點是否被訪問？從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于52voidDFS(GraphG,intv){//從頂點v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);

//對v的尚未訪問的鄰接頂點w//遞歸調(diào)用DFS}//DFSvoidDFS(GraphG,intv){53首先將圖中每個頂點的訪問標志設為FALSE,之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先搜索遍歷首先將圖中每個頂點的訪問標志設為FALSE54voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

//對圖G作深度優(yōu)先遍歷。VisitFunc=Visit;

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標志數(shù)組初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);//對尚未訪問的頂點調(diào)用DFS}voidDFSTraverse(GraphG,55abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問標志:訪問次序:例如:012345678abchdekfgFFFFFF56二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連通圖，從起始點V到其余各頂點必定存在路徑。其中，V->w1,V->w2,V->w8

的路徑長度為1；V->w7,V->w3,V->w5

的路徑長度為2；V->w6,V->w4

的路徑長度為3。w1Vw2w7w6w3w8w5w4二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連57從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問58

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪問標志

InitQueue(Q);

//置空的輔助隊列Q

for(v=0;v<G.vexnum;++v)

if(

!visited[v]){

//v尚未訪問

}

}//BFSTraverse……voidBFSTraverse(GraphG,……59visited[u]=TRUE;Visit(u);//訪問uEnQueue(Q,v);

//v入隊列while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

visited[w]=TRUE;Visit(w);EnQueue(Q,w);

//訪問的頂點w入隊列}//if}//whilevisited[u]=TRUE;Visit(u);60三、遍歷應用舉例1.求一條從頂點i到頂點s的簡單路徑2.

求兩個頂點之間的一條路徑長度最短的路徑三、遍歷應用舉例1.求一條從頂點i到頂點s的2.611.

求一條從頂點i到頂點s的簡單路徑abchdekfg求從頂點b到頂點k的一條簡單路徑。從頂點b出發(fā)進行深度優(yōu)先搜索遍歷。例如:假設找到的第一個鄰接點是a，則得到的結(jié)點訪問序列為:b

adhce

kfg。假設找到的第一個鄰接點是c，則得到的結(jié)點訪問序列為:

b

chdae

kfg，1.求一條從頂點i到頂點s的簡單路徑abchde621.從頂點i到頂點s,若存在路徑，則從頂點i出發(fā)進行深度優(yōu)先搜索，必能搜索到頂點s。2.

遍歷過程中搜索到的頂點不一定是路徑上的頂點。結(jié)論:3.

由它出發(fā)進行的深度優(yōu)先遍歷已經(jīng)完成的頂點不是路徑上的頂點。1.從頂點i到頂點s,若存在路徑，則從頂點i出63voidDFSearch(intv,ints,char*PATH){//從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G，//求得一條從v到s的簡單路徑，并記錄在PATH中visited[v]=TRUE;//訪問第v個頂點

Append(PATH,getVertex(v));

//第v個頂點加入路徑

for(w=FirstAdjVex(v);w!=0&&!found;

w=NextAdjVex(v))

if(w=s){found=TRUE;Append(PATH,w);}

else

if(!visited[w])DFSearch(w,s,PATH);if(!found)Delete(PATH);

//從路徑上刪除頂點v

}voidDFSearch(intv,ints,c642.

求兩個頂點之間的一條路徑長度最短的路徑

若兩個頂點之間存在多條路徑，則其中必有一條路徑長度最短的路徑。如何求得這條路徑?2.求兩個頂點之間的一條路徑若兩個頂點之間存在多條65abchdekfg因此，求路徑長度最短的路徑可以基于廣度優(yōu)先搜索遍歷進行，但需要修改鏈隊列的結(jié)點結(jié)構(gòu)及其入隊列和出隊列的算法。深度優(yōu)先搜索訪問頂點的次序取決于圖的存儲結(jié)構(gòu)，而廣度優(yōu)先搜索訪問頂點的次序是按“路徑長度”漸增的次序。abchdekfg因此，求路徑長度最短的路徑可以基于廣度優(yōu)先66例如:求下圖中頂點3至頂點5的一條最短路徑。鏈隊列的狀態(tài)如下所示:

312475

Q.front

Q.rear321475689例如:求下圖中頂點3至頂點5的一條最短路徑。鏈隊列的671)將鏈隊列的結(jié)點改為“雙鏈”結(jié)點。即結(jié)點中包含next和priou兩個指針；2)修改入隊列的操作。插入新的隊尾結(jié)點時，令其priou域的指針指向剛剛出隊列的結(jié)點，即當前的隊頭指針所指結(jié)點；3)修改出隊列的操作。出隊列時，僅移動隊頭指針，而不將隊頭結(jié)點從鏈表中刪除。1)將鏈隊列的結(jié)點改為“雙鏈”結(jié)點。即2)修改入隊列的操68typedef

DuLinkListQueuePtr;

voidInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

Q.front->next=Q.rear->next=NULL}voidEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;

p->priou=Q.front

Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,QelemType&e){

Q.front=Q.front->next;e=Q.front->data}typedefDuLinkListQueuePtr;697.4(連通網(wǎng)的)最小生成樹

假設要在n個城市之間建立通訊聯(lián)絡網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？問題：7.4(連通網(wǎng)的)最小生成樹假設要在n個70構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價于：算法一：（普里姆算法）構(gòu)造網(wǎng)的一棵最小生成樹，即：在e71

取圖中任意一個頂點v作為生成樹的根，之后往生成樹上添加新的頂點w。在添加的頂點w和已經(jīng)在生成樹上的頂點v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n-1個頂點為止。普里姆算法的基本思想:取圖中任意一個頂點v作為生成樹的根，之后往生成樹72abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67abcdegf例如:195141827168213ae12d73在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

和尚未落在生成樹上的頂點集V-U，則應在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點應滿足下列條件:在生成樹的構(gòu)造過程中，圖中n個頂點分74設置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊：struct{VertexTypeadjvex;//U集中的頂點序號VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];設置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄和75abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55abcdegf195141827168213ae12dcb776voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){}繼續(xù)向生成樹上添加頂點;voidMiniSpanTree_P(MGraphG,77

k=minimum(closedge);

//求出加入生成樹的下一個頂點(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹上一條邊closedge[k].lowcost=0;//第k頂點并入U集for(j=0;j<G.vexnum;++j)//修改其它頂點的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

k=minimum(closedge);78具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。考慮問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄壕唧w做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)79abcdegf195141827168213ae12dcbgf7148531621例如:7121819abcdegf195141827168213ae12dcbg80算法描述:構(gòu)造非連通圖ST=(V,{});k=i=0;//k計選中的邊數(shù)while(k<n-1){++i;檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}算法描述:構(gòu)造非連通圖ST=(V,{});81普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍比較兩種算法普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)827.5重（雙）連通圖和關節(jié)點

若從一個連通圖中刪去任何一個頂點及其相關聯(lián)的邊，它仍為一個連通圖的話，則該連通圖被稱為重（雙）連通圖。問題：7.5重（雙）連通圖若從一個連通圖中刪去任83

若連通圖中的某個頂點和其相關聯(lián)的邊被刪去之后，該連通圖被分割成兩個或兩個以上的連通分量，則稱此頂點為關節(jié)點。沒有關節(jié)點的連通圖為雙連通圖。如何判別給定的連通圖是否是雙連通圖？若連通圖中的某個頂點和其相關沒有關節(jié)點的連通84ahgcbfdeabcdefgh1234567833111111例如:下列連通圖中，頂點

a

和頂點c

是關節(jié)點深度優(yōu)先生成樹ahgcbfdeabcdefgh1234567833111185關節(jié)點有何特征？

假設從某個頂點V0出發(fā)對連通圖進行深度優(yōu)先搜索遍歷，則可得到一棵深度優(yōu)先生成樹，樹上包含圖的所有頂點。需借助圖的深度優(yōu)先生成樹來分析。關節(jié)點有何特征？假設從某個頂點V0出發(fā)對連通圖進行深86

若生成樹的根結(jié)點，有兩個或兩個以上的分支，則此頂點(生成樹的根)必為關節(jié)點；

對生成樹上的任意一個“頂點”，若其某棵子樹的根或子樹中的其它“頂點”沒有和其祖先相通的回邊，則該“頂點”必為關節(jié)點。若生成樹的根結(jié)點，有兩個或兩個以上的分支，則此頂點(生成樹87對上述兩個判定準則在算法中如何實現(xiàn)？對上述兩個判定準則在算法中如何實現(xiàn)？881)設V0為深度優(yōu)先遍歷的出發(fā)點

p=G.vertices[0].firstarc;v=p->adjvex;

DFSArticul(G,v);

//從第v頂點出發(fā)深度優(yōu)先搜索

if

(count<G.vexnum)

{

//生成樹的根有至少兩棵子樹

printf(0,G.vertices[0].data);

//根是關節(jié)點1)設V0為深度優(yōu)先遍歷的出發(fā)點892)定義函數(shù):low(v)=Min{visited[v],low[w],visited[k]}

其中:頂點w

是生成樹上頂點v

的孩子；頂點k

是生成樹上和頂點v由回邊相聯(lián)接的祖先；visited記錄深度優(yōu)先遍歷時的訪問次序

若對頂點v，在生成樹上存在一個子樹根w，

且

low[w]≥visited[v]

則頂點v為關節(jié)點。2)定義函數(shù):90對深度優(yōu)先遍歷算法作如下修改：1．visited[v]的值改為遍歷過程中頂點的訪問次序count值；

2．遍歷過程中求得

low[v]=Min{visited[v],low[w],visited[k]}3．從子樹遍歷返回時，判別low[w]≥visited[v]?對深度優(yōu)先遍歷算法作如下修改：1．visited[v]的值改91for(p=G.vertices[v0].firstarc;p;p=p->nextarc){

}voidDFSArticul(ALGraphG,intv0){//從第v0個頂點出發(fā)深度優(yōu)先遍歷圖G,

//查找并輸出關節(jié)點}//DFSArticulmin=visited[v0]=++count;//v0是第count個訪問的頂點,并設low[v0]的初值為min

//檢查v0的每個鄰接點low[v0]=min;for(p=G.vertices[v0].firstarc;92

w=p->adjvex;//w為v0的鄰接頂點

if(visited[w]==0){//w未曾被訪問DFSArticul(G,w);//返回前求得low[w]

}

else//w是回邊上的頂點if(low[w]<min)min=low[w];

if(low[w]>=visited[v0])

printf(v0,G.vertices[v0].data);

//輸出關節(jié)點if(visited[w]<min)min=visited[w];w=p->adjvex;//w為v0937.6兩點之間的

最短路徑問題求從某個源點到其余各點的最短路徑每一對頂點之間的最短路徑

7.6兩點之間的

最短路徑問題求從某個源點到其94求從源點到其余各點的最短路徑的算法的基本思想:依最短路徑的長度遞增的次序求得各條路徑源點v1…其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。v2求從源點到其余各點的最短路徑的算法的基本思想:95在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長度次短的最短路徑的特點：路徑長度最短的最短路徑的特點：它只可能有兩種情況：或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)。在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。96其余最短路徑的特點：再下一條路徑長度次短的最短路徑的特點:它可能有三種情況：或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)；或者是從源點經(jīng)過頂點v2，再到達該頂點。它或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點。其余最短路徑的特點：再下一條路徑長度次短的最短路徑的特點:97求最短路徑的迪杰斯特拉算法：一般情況下，Dist[k]=<源點到頂點k的弧上的權(quán)值>或者=<源點到其它頂點的路徑長度>

+<其它頂點到頂點k的弧上的權(quán)值>。

設置輔助數(shù)組Dist，其中每個分量Dist[k]表示

當前所求得的從源點到其余各頂點k的最短路徑。求最短路徑的迪杰斯特拉算法：一般情況下，設置輔助數(shù)組Di981）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點的Dist[k]值。假設求得最短路徑的頂點為u，若Dist[u]+G.arcs[u][k]<Dist[k]則將Dist[k]改為Dist[u]+G.arcs[u][k]。V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長度。1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最99求每一對頂點之間的最短路徑弗洛伊德算法的基本思想是：從vi到vj的所有可能存在的路徑中，選出一條長度最短的路徑。求每一對頂點之間的最短路徑弗洛伊德算法的基本思想是：從100若<vi,vj>存在，則存在路徑{vi,vj}//路徑中不含其它頂點若<vi,v1>,<v1,vj>存在，則存在路徑{vi,v1,vj}//路徑中所含頂點序號不大于1若{vi,…,v2},{v2,…,vj}存在，則存在一條路徑{vi,…,v2,…vj}//路徑中所含頂點序號不大于2…依次類推，則vi至vj的最短路徑應是上述這些路徑中，路徑長度最小者。若<vi,vj>存在，則存在路徑{vi,vj}依次1017.7拓撲排序

問題:

假設以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。

檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。7.7拓撲排序問題:假設以有向圖表示一個102何謂“拓撲排序”？對有向圖進行如下操作：

按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。何謂“拓撲排序”？對有向圖進行如下操作：按照有向圖給103例如：對于下列有向圖BDAC可求得拓撲有序序列：

ABCD

或

ACBD由此所得頂點的線性序列稱之為拓撲有序序列例如：對于下列有向圖BDAC可求得拓撲有序序列：由此所得頂點104BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路{B,C,D}BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖105如何進行拓撲排序？一、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之；

重復上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點為止。二、從有向圖中刪去此頂點以及所

有以它為尾的?。蝗绾芜M行拓撲排序？一、從有向圖中選取一個沒有前驅(qū)106abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點入度為零的頂點刪除頂點及以它為尾的弧弧頭頂點的入度減1abcghdfeabhcdgfe在算法中需要用定量的描述替代107取入度為零的頂點v;while(v<>0){

printf(v);++m;w:=FirstAdj(v);

while(w<>0){inDegree[w]--;w:=nextAdj(v,w);

}取下一個入度為零的頂點v;}ifm<nprintf(“圖中有回路”);算法描述取入度為零的頂點v;算法描述108為避免每次都要搜索入度為零的頂點，在算法中設置一個“棧”，以保存“入度為零”的頂點。CountInDegree(G,indegree);//對各頂點求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);//入度為零的頂點入棧為避免每次都要搜索入度為零的頂點，Count109count=0;//對輸出頂點計數(shù)while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧頭頂點的入度減一

if(!indegree[w])Push(S,w);

//新產(chǎn)生的入度為零的頂點入棧}}if(count<G.vexnum)printf(“圖中有回路”)count=0;//對輸出頂點計數(shù)1107.8關鍵路徑問題:

假設以有向網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項子工程所需時間。問：哪些子工程項是“關鍵工程”？即：哪些子工程項將影響整個工程的完成期限的。7.8關鍵路徑問題:假設以有向網(wǎng)表示一個111abcdefghk64521187244例如:“關鍵活動”指的是：該弧上的權(quán)值增加

將使有向圖上的最長路徑的長度增加。整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。源點匯點6174abcdefghk64521187244例如:“關鍵活動”指112

如何求關鍵活動？“事件(頂點)”的最早發(fā)生時間ve(j)ve(j)=從源點到頂點j的最長路徑長度；“事件(頂點)”的最遲發(fā)生時間vl(k)vl(k)=從頂點k到匯點的最短路徑長度。如何求關鍵活動？“事件(頂點)”的最早發(fā)生時間ve(113

假設第i條弧為<j,k>則對第i項活動言“活動(弧)”的最早開始時間ee(i)ee(i)=ve(j)；“活動(弧)”的最遲開始時間el(i)el(i)=vl(k)–dut(<j,k>)；假設第i條弧為<j,k>114

事件發(fā)生時間的計算公式：ve(源點)=0；ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點)=ve(匯點)；vl(j)=Min{vl(k)–dut(<j,k>)}事件發(fā)生時間的計算公式：115abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓撲有序序列:a-d-f-c-b-e-h-g-kabcdefghk6452118724400000000061160645771514181814161078660000645777151414160236688710064577151418181416107866000064117

算法的實現(xiàn)要點:顯然，求ve的順序應該是按拓撲有序的次序；

而求vl的順序應該是按拓撲逆序的次序；因為拓撲逆序序列即為拓撲有序序列的逆序列，因此應該在拓撲排序的過程中，另設一個“?！庇浵峦負溆行蛐蛄?。算法的實現(xiàn)要點:顯然，求ve的順序應該是按拓撲有序的次序；1181.熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系。2.熟練掌握圖的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學習中應注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。1.熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求解119

3.應用圖的遍歷算法求解各種簡單路徑問題。4.理解教科書中討論的各種圖的算法。3.應用圖的遍歷算法求解各種簡單路徑問題。1207.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲表示7.3圖的遍歷7.4最小生成樹7.5重（雙）連通圖和關節(jié)點7.6兩點之間的最短路徑問題7.7拓撲排序7.8關鍵路徑7.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲表示7.3圖的121圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x某個數(shù)據(jù)對象}

是頂點的有窮非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條單向通路,它是有方向的。圖的基本概念圖定義圖是由頂點集合(vertex)及頂點122

有向圖與無向圖在有向圖中，頂點對<x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖若有

n個頂點的無向圖有n(n-1)/2條邊,則此圖為完全無向圖。有

n個頂點的有向圖有n(n-1)條邊,則此圖為完全有向圖。00001111222265433有向圖與無向圖在有向圖中，頂點對<x,y>123

鄰接頂點如果

(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖設有兩個圖G＝(V,E)和G'＝(V',E')。若V'V且E'E,則稱圖G'是圖G的子圖。權(quán)某些圖的邊具有與它相關的數(shù),稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡。子圖01230130123023鄰接頂點如果(u,v)是E(G)中的一124頂點的度一個頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數(shù),記作

ID(v);頂點v的出度是以v為始點的有向邊的條數(shù),記作

OD(v)。路徑在圖G＝(V,E)中,若從頂點

vi

出發(fā),沿一些邊經(jīng)過一些頂點

vp1,

vp2,…,

vpm，到達頂點vj。則稱頂點序列

(vi

vp1vp2...vpm

vj)

為從頂點vi到頂點

vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。頂點的度一個頂點v的度是與它相關聯(lián)的邊的條數(shù)。記作TD(125路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。簡單路徑若路徑上各頂點v1,v2,...,vm

均不互相重復,則稱這樣的路徑為簡單路徑?；芈啡袈窂缴系谝粋€頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環(huán)。012301230123路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的126連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。生成樹一個連通圖的生成樹是其極小連通子圖，在n個頂點的情形下，有

n-1條邊。連通圖與連通分量在無向圖中,若從頂點v1到頂點v2有127

圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，VR＝{<v,w>|v,w∈V且P(v,w)}

<v,w>表示從v到w的一條弧，并稱v為弧頭，w為弧尾。

謂詞P(v,w)定義了弧<v,w>的意義或信息。圖的結(jié)構(gòu)定義:圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。128

由于“弧”是有方向的，因此稱由頂點集和弧集構(gòu)成的圖為有向圖。

AB