第7章-圖-數(shù)據(jù)結(jié)構(gòu)與算法pptx

DataStructuresandAlgorithms主講教師:黃襄念西華大學數(shù)學與計算機學院圖像處理與模式識別實驗室課程QQ群：101600501數(shù)據(jù)結(jié)構(gòu)與算法本章授課內(nèi)容圖的定義圖的術(shù)語存儲結(jié)構(gòu)：鄰接矩陣存儲結(jié)構(gòu)：鄰接表存儲結(jié)構(gòu)：逆鄰接表圖的遍歷：DFSDFS：概念圖解DFS：遞歸算法DFS：棧過程圖解DFS：非遞歸算法DFS：簡單應(yīng)用圖的遍歷：BFSBFS：概念圖解BFS：隊列過程圖解BFS：算法設(shè)計BFS：簡單應(yīng)用遍歷時間效率分析本章作業(yè)本章授課學時：4學時04:062／33圖(Graph)定義：頂點集V和邊集（弧集）E組成的二元組

記為G=(V,E)無向圖：邊沒方向，上圖有向圖：邊有方向，右圖V={1,2,3,4}E={<1,2>,<1,3>,<2,4>,<3,4>,<4,1>}圖：定義1324V={1,2,3,4}E={(1,2),(1,3),(1,4),(2,4),(3,4)}樹：連通無環(huán)圖1324有向圖04:063／33頂點(Vertex)：圖中的數(shù)據(jù)元素弧(Arc)：<v,w>∈E，弧v→w弧尾(Tail)：

弧<v,w>頂點v弧頭(Head)：弧<v,w>頂點w邊(Edge)若

<v,w>∈E，則<w,v>∈E，無序?qū)?v,w)表示邊有向圖(Digraph)：由弧和頂點組成無向圖(Undigraph)：由邊和頂點組成完全圖(CompletedGraph)任意兩個頂點之間都有邊／弧相連，下圖圖：術(shù)語04:064／33無向完全圖：邊數(shù)有向完全圖：弧數(shù)稠密圖(DenseGraph)：邊數(shù)多稀疏圖(SparseGraph)：邊數(shù)少權(quán)(Weight)：賦予邊的數(shù)值，常表示距離或耗費網(wǎng)(Network)：帶權(quán)圖圖：術(shù)語1324無向完全圖有向完全76帶權(quán)圖204:065／33子圖(Subgraph)對于圖G

=(V,E

),若存在圖G1=(V1,E1)滿足：,則:G1

是

G

的子圖鄰接(Adjacent)若(vi,vj)∈E,稱vi與vj鄰接（互為鄰接頂點）若<vi,vj>∈E,稱vi與vj鄰接（有向圖）——vi鄰接到vj,vj鄰接自vi圖：術(shù)語1324G1324G11324G2132G304:066／33關(guān)聯(lián)：邊(vi,vj)

或弧<vi,vj>與頂點vi,vj關(guān)聯(lián)頂點的度(Degree)無向圖：與vi相連的邊數(shù)(頂點數(shù))，記為D(vi)有向圖：分為入度(InDegree)、出度(OutDegree)入度——以vi為終點的弧數(shù)，記為ID(vi)出度——以vi起點的弧數(shù)，記為OD(vi)vi的度=入度+出度，即:D(vi)=ID(vi)+OD(vi)邊(弧)的數(shù)量e：圖：術(shù)語1324D(2)=ID(2)+OD(2)

=2+1=3e=(3+3+2+2)/2=504:067／33路徑(Path)——頂點序列（從vp

到vq

的一條路徑）

下標：頂點。上標：該頂點在路徑中的序號

例如：(1,3,2,4)路徑長度路徑上的邊或弧數(shù)，或各邊的權(quán)值和（帶權(quán)圖）簡單路徑路徑上頂點不重復（每個頂點僅經(jīng)過一次）回路／環(huán)(Cycle)路徑上第一個與最后一個頂點相同（首尾相連）圖：術(shù)語132404:068／33簡單回路（簡單環(huán)）簡單路徑+回路：除首尾頂點外，其余頂點不重復連通(Connected)若兩個頂點之間存在一條路徑，則它們連通連通圖(ConnectedGraph)任意兩個頂點都連通的圖連通分量(ConnectedComponent)無向圖的一個極大連通子圖稱為一個連通分量極大：邊和頂點最多連通圖的連通分量：只一個（自己）非連通圖連通分量：有多個，下例圖：術(shù)語04:069／33強連通圖有向圖G的任意兩個頂點vi和vj,vi→vj和vj→vi

的路徑都存在，則G是強連通圖強連通分量有向圖的極大強連通子圖圖：術(shù)語連通分量強連通分量無向圖非強連通圖04:0610／33生成樹（支撐樹）樹（自由樹）：連通無環(huán)圖生成樹：包含連通圖全部頂點的一個極小連通子圖極?。哼厰?shù)最少且等于n-1

有向樹只有一個頂點入度=0,其余頂點入度=1

的有向圖

根（有向根）：入度=0

為何有且僅有

1個頂點度=0？圖：術(shù)語1324邊數(shù)>n-1？邊數(shù)<n-1？132413241324132404:0611／33圖的存儲結(jié)構(gòu)存儲：數(shù)據(jù)元素（頂點）、數(shù)據(jù)的關(guān)系（邊）四類：鄰接矩陣、鄰接表、鄰接多重表、十字鏈表鄰接矩陣存儲邊或?。旤c的關(guān)系）非帶權(quán)圖：n個頂點二維數(shù)組A[n][n]存儲A[i][j]：從i行到j(luò)列，vi→vj行元素和：出度；列元素和：入度圖的順序存儲結(jié)構(gòu)：鄰接矩陣132404:0612／33網(wǎng)（帶權(quán)圖）存儲頂點數(shù)據(jù)（數(shù)據(jù)元素）鄰接矩陣存儲的是頂點之間的關(guān)系（邊或?。┰儆靡粋€數(shù)組V[n]存儲頂點數(shù)據(jù)，V[i]存儲頂點vi——下標i相當于頂點的編號圖的順序存儲結(jié)構(gòu)：鄰接矩陣1324582.762無向圖：對稱陣04:0613／33數(shù)據(jù)類型constintMAXNODE=100;∥頂點的最大個數(shù)typedefstruct{ElemTypeVex[MAXNODE];

∥頂點數(shù)組,靜態(tài)分配

int

Edge[MAXNODE][MAXNODE];∥鄰接矩陣//數(shù)據(jù)類型與邊有關(guān)，如bool,int,double等

intVexNum,EdgeNum;∥頂點數(shù)，邊數(shù)}ArrGraph,

*pArrGraph;//----------------------------------------------------------------*可將兩個數(shù)組進行動態(tài)分配（new）**復習C++：如何new二維數(shù)組鄰接矩陣的數(shù)據(jù)類型04:0614／33鄰接表（AdjacencyList）每個頂點建一個單鏈表：鏈接該頂點的所有鄰接頂點n個頂點數(shù)據(jù)：一維數(shù)組存儲圖的鏈式存儲結(jié)構(gòu)：鄰接表v1v3v2v458462v1v3v2v4V[i]datafirst0v11v22v33v4182532^0836^0534^021624^V[i]datafirst0v11v22v33v412^3^3^0^度=鏈表長度（不含頭）怎么求入度？04:0615／33逆鄰接表問題提出：對有向圖的入度感興趣將每個頂點“鄰接自”的所有頂點連成單鏈表圖的鏈式存儲結(jié)構(gòu)：鄰接表v1v3v2v4V[i]datafirst0v11v22v33v43^2^0^0^1好處：某頂點入度=其單鏈表（不含頭）長度04:0616／33typedefstructAdjVex

∥鄰接頂點（單鏈表結(jié)點）{intadjvex;∥鄰接點在頂點數(shù)組中的下標

AdjVex*next;∥指向下一鄰接點

floatweight;∥權(quán)值}ArcNode;typedefstruct∥一個頂點{ElemTypeVertex;∥頂點數(shù)據(jù)

ArcNode*First;∥指向第一鄰接點

}VexNode;constintMAXNODE=100;

∥頂點的最大個數(shù)

typedefstruct∥頂點數(shù)組{VexNodeVex[MAXNODE];

intVexNum,ArcNum;∥頂點數(shù)、邊數(shù)

}ALGraph;鄰接表的數(shù)據(jù)類型04:0617／33十字鏈表（OrthogonalList）有向圖的另一種鏈式存儲方式——把鄰接表和逆鄰接表相結(jié)合*自修鄰接多重表（AdjacencyMultilist）無向圖的另一種鏈式存儲方式——與十字鏈表類似*自修十字鏈表與鄰接多重表04:0618／33圖的遍歷（

TraversingGraph

）訪問圖中所有頂點一次且僅一次的過程深度優(yōu)先搜索（DepthFirstSearch,DFS）廣度優(yōu)先搜索（BreadthFirstSearch,BFS）深度優(yōu)先搜索,DFS——類似于樹的先根遍歷，是樹的先根遍歷的推廣任選一頂點作始點v,訪問該頂點；沿深度方向，依次遍歷v的未訪問鄰接點，——直到本次遍歷結(jié)束一次遍歷完時，若有未訪問頂點：任選一個未訪問頂點作始點v，GOTO②圖：遍歷04:0619／33DFS遍歷——圖解過程DFS遍歷：圖解過程DFS過程實線：深度搜索虛線：回溯存儲結(jié)構(gòu)不確定，遍歷結(jié)果不唯一一種DFS序列：

DFS(G,v1)=(v1,v2,v3,v6,v5,v7,v4,v8,v9)04:0620／33bool

visited[MAXNODE];//頂點的訪問標志數(shù)組void

DFSInit(GraphG){for(i=0;i<G.VertexNum;i++)visited[i]=false;}//-------------------------------------------------------------------voidDFS(GraphG,intv)//v:頂點數(shù)組中的序號{Visit[v];

visited[v]=true;

w=FirstAdj(G,v);//返回：v的第一個鄰接點

while(w!=0)//返回：0表示無鄰接點

{if(!visited[w])

DFS(G,w);

//參數(shù)傳遞w→vw=NextAdj(G,v,w));}}

//NextAdj返回：v的在鄰接點w后的鄰接點

//返回0:不存在DFS遍歷：遞歸算法理解回溯過程本算法對G進行了多少次遍歷？本算法能夠遍歷非連通或有向圖所有結(jié)點嗎？04:0621／33完全遍歷算法問題：非連通圖或某些有向圖，一次不能完全遍歷辦法：重選一個未訪問頂點作始點，再次遍歷實現(xiàn)：如何重選始點？算法：voidDFSTrav(GraphG)//G的頂點數(shù)n{

for(i=0;i<n;i++)visited[i]=false;

for(i=0;i<n;i++)

if(!visited[i])DFS(G,i);}DFS遍歷：遞歸算法思考：你還有什么其他的辦法？04:0622／33DFS棧過程DFS遍歷：非遞歸算法設(shè)計AEBCDFACABCAFBCADFBCAEFBCAFBCABCACAAFBCA考察棧頂元素（頂點）：入棧：top的未訪問鄰接點退棧：top無未訪問鄰接點棧空：DFS遍歷結(jié)束DFS進棧序列：ACBFDEDFS退棧序列：DEFBCA04:0623／33voidDFS(GraphG,intv){CreateStack(S);Visite(v);visited[v]=true;

Push(S,v);//始點入棧while(!S.isEmpty())

{w

=FirstAdj(G,S[top]);//

棧頂?shù)牡谝粋€鄰點

while(w!=0)//0:無鄰點

{if(!visited[w])

{Visite(w);visited[w]=true;Push(S,w);

w=

FirstAdj(G,S[top]);}

elsew=NextAdj(G,S[top],w);}//本循環(huán)：縱深前進到底Pop(S);//退棧，回溯}}DFS遍歷：非遞歸算法163254考慮頂點2的第一個鄰接點是誰？04:0624／33求解連通性設(shè)計算法：求給定無向圖的連通分量個數(shù)求解邊數(shù)設(shè)計算法：求給定無向圖的邊數(shù)檢查無環(huán)性設(shè)計算法：判斷給定無向圖是否自由樹設(shè)計算法：判斷給定有向圖是否有向樹判斷關(guān)節(jié)點設(shè)計算法：判斷給定圖的一個頂點是否為關(guān)節(jié)點關(guān)節(jié)點：刪除關(guān)節(jié)點及與其相關(guān)聯(lián)的邊后，圖被

分解為若干個不相交的子圖DFS遍歷的簡單應(yīng)用04:0625／33廣度優(yōu)先搜索,BFS——類似于樹的層次遍歷，是樹的層次遍歷的推廣BFS遍歷一種BFS序列（不唯一）：

BFS(G,v1)=(v1,v2,v4,v3,v5,v7,v6,v9,v8)始點1234567989101284537604:0626／33BFS遍歷算法（非遞歸）復習“二叉樹層次遍歷”推廣到圖，BFS算法修改：根結(jié)點改為初始頂點圖可能有環(huán)，增加頂點訪問標志變量子女入隊的次序，由存儲結(jié)構(gòu)確定BFS遍歷：非遞歸算法設(shè)計12478356創(chuàng)建空隊Q;根結(jié)點入隊;if(Q==Φ)遍歷結(jié)束;elsep=出隊;if(p有子女)

{左→右子女入隊

;轉(zhuǎn)②;}04:0627／33BFS遍歷：算法過程圖解A隊頭A入隊CEA出隊，A鄰接點C,E入隊FD出隊，D無未訪問

鄰接點DFB出隊，B無未訪問

鄰接點EBDFC出隊，C鄰接點B,D,F入隊BDFE出隊，E無未訪問

鄰接點F出隊，F(xiàn)無未訪問

鄰接點隊空：BFS結(jié)束(ACEBDF)AEBCDFAEBCDFBFS樹04:0628／33void

BFS(GraphG,intv){QueueQ;//創(chuàng)建空隊列Q

Visite(v);visited[v]=true;EnQueue(v);//入隊

while(!Q.isEmpty()){v=DeQueue();//出隊

w=FirstAdj(G,v);//v的第一個鄰接點w

while(w!=0)//w存在

{

if(!visited[w])

{Visite(w);visited[w]=true;EnQueue(w);}

w=NextAdj(G,v,w);

//w后的下一個鄰接點

}

}}BFS遍歷：算法本算法對圖進行了多少次遍歷？本算法能遍歷非連通或有向圖所有結(jié)點嗎？04:0629／33檢查圖的連通性、無環(huán)性本質(zhì)上與DFS一樣求給定兩個