算法設(shè)計(jì)與分析課件：Graph Traversal

GraphTraversalContents

FlavorsofGraphsDataStructuresforGraphBreadth-FirstSearchandApplicationsConnectedComponentsTwo-ColoringGraphsDepth-FirstSearchandApplicationsFindingCyclesArticulationVerticesTopologicalSortingStronglyConnectedComponentsFlavorsofGraphsGraphsRealLifeExamplesAnexamplemapofGermanywithsomeconnectionsbetweencities.FlavorofGraphsThefirststepinanygraphproblemisdeterminingwhichflavorofgraphyouaredealingwith.Theflavorofgraphhasabigimpactonwhichalgorithmsareappropriateandefficient.Directedvs.UndirectedGraphsAgraphG=(V;E)isundirected

ifedge(x,y)∈Eimpliesthat(y,x)isalsoinE,elseitisdirectedandcalledDigraph.Roadnetworksbetweencitiesaretypicallyundirected.Streetnetworkswithincitiesarealmostalwaysdirectedbecauseofone-waystreets.有向圖邊都是單向(unidirectional)的,因此邊(u,v)是有序數(shù)對(duì).有時(shí)用弧(arc)專指有向邊在有向邊(u,v)中,u和v分別叫源(source)和目的(destination)尾(tail)和頭(head),不過和數(shù)據(jù)結(jié)構(gòu)有沖突有向無環(huán)圖(directedacyclicgraph,DAG)不是樹,它的基圖(underlyingundirectedgraph)也不一定是樹Weightedvs.UnweightedGraphsInweighted

graphs,eachedge(orvertex)ofGisassignedanumericalvalue,calledweightorcost.Theedgesofaroadnetworkgraphmightbeweightedwiththeirlength,drive-timeorspeedlimit.帶權(quán)圖可以給邊加權(quán)(weight),成為帶權(quán)圖,或加權(quán)圖(weightedgraph).權(quán)通常代表費(fèi)用、距離等,可以是正數(shù),也可以是負(fù)數(shù)也可以給點(diǎn)加權(quán),或者邊上加多種權(quán)帶權(quán)有向圖一般也稱為網(wǎng)絡(luò)(network)帶權(quán)圖的問題多為組合優(yōu)化問題,在運(yùn)籌學(xué)中有廣泛應(yīng)用Simplevs.Non-simpleGraphsCertaintypesofedgescomplicatethetaskofworkingwithgraphs.Aself-loop

isanedge(x,x)involvingonlyonevertex.Anedge(x,y)isamulti-edge

ifitoccursmorethanonceinthegraph.Anygraphwhichavoidsthesestructuresiscalledsimple.Sparsevs.DenseGraphsGraphsaresparse

whenonlyasmallfractionofthepossiblenumberofvertexpairsactuallyhaveedgesdefinedbetweenthem.Graphsareusuallysparseduetoapplication-specificconstraints.Roadnetworksmustbesparsebecauseofroadjunctions.Typicallydensegraphshaveaquadraticnumberofedgeswhilesparsegraphsarelinearinsize.稀疏圖和稠密圖邊和V(V-1)/2相比非常少的稱為稀疏圖(sparsegraph),它的補(bǔ)圖為稠密圖(densegraph)時(shí)間復(fù)雜度為ElogE的算法和V2的算法對(duì)于稀疏圖來說前者好,稠密圖來說后者好一般來說,即使對(duì)于稀疏圖,V和E相比都很小,可以用E來代替V+E,因此O(V(V+E))可以簡寫為O(VE)Cyclicvs.AcyclicGraphsAnacyclic

graphdoesnotcontainanycycles.Treesareconnectedacyclicundirectedgraphs.DirectedacyclicgraphsarecalledDAGs.Theyarisenaturallyinschedulingproblems,whereadirectededge(x,y)indicatesthatxmustoccurbeforey.Implicitvs.ExplicitGraphsManygraphsarenotexplicitlyconstructedandthentraversed,butbuiltasweusethem.Agoodexamplearisesinbacktracksearch.IsomorphismGraphsisomorphismtesting:determiningwhetherthetopologicalstructureoftwographsareinfactidenticalifweignoreanylabels.右圖是同一個(gè)圖的不同表示。所有邊如下表TheFriendshipGraphConsideragraphwheretheverticesarepeople,andthereisanedgebetweentwopeopleifandonlyiftheyarefriends.Thisgraphiswell-definedonanysetofpeople:SYSU,GuangZhou,ortheworld.Whatquestionsmightweaskaboutthefriendshipgraph?IfIamyourfriend,doesthatmeanyouaremyfriend?Agraphisundirected

if(x,y)implies(y,x).Otherwisethegraphisdirected.The“heard-of”graphisdirectedsincecountlessfamouspeoplehaveneverheardofme!The“be-married-with”graphispresumablyundirected,sinceitrequiresapartner.AmImyownfriend?Anedgeoftheform(x;x)issaidtobealoop.Ifxisy’sfriendseveraltimesover,thatcouldbemodeledusingmultiedges,multipleedgesbetweenthesamepairofvertices.Agraphissaidtobesimple

ifitcontainsnoloopsandmultipleedges.AmIlinkedbysomechainoffriendstothePresident?Apath

isasequenceofedgesconnectingtwovertices.SincethePresidentofSunYat-senUniversityismyfriend’sdirector,thereisapathbetweenmeandhim.路徑和圈一條路徑(path)是一個(gè)結(jié)點(diǎn)序列,路上的相鄰結(jié)點(diǎn)在圖上是鄰接的.如果結(jié)點(diǎn)和邊都不重復(fù)出現(xiàn),則稱為簡單路徑(simplepath).如果除了起點(diǎn)和終點(diǎn)相同外沒有重復(fù)頂點(diǎn)和邊,稱為圈(cycle).不相交路(disjointpath)表示沒有除了起點(diǎn)和終點(diǎn)沒有公共點(diǎn)的路.更嚴(yán)格地任意點(diǎn)都不相同的叫嚴(yán)格不相交路(vertex-disjointpath)同理定義邊不相交(edge-disjointpath)路注意:漢語中圈和環(huán)經(jīng)?；煊?包括一些固定術(shù)語).由于一般不討論自環(huán)(self-loop),所以以后假設(shè)二者等價(jià)而不會(huì)引起混淆HowcloseismylinktothePresident?weareofteninterestedintheshortest

path

betweentwonodes.Ingraph(a),path1-2-4isshorterthan1-2-3-4.Isthereapathoffriendsbetweenanytwopeople?Agraphisconnected

ifthereisapathbetweenanytwovertices.Adirectedgraphisstrongly

connected

ifthereisadirectedpathbetweenanytwovertices.連通性如果任意兩點(diǎn)都有路徑,則稱圖是連通(connected)的,否則稱圖是非連通的.非連通圖有多個(gè)連通分量(connectedcomponent,cc),每個(gè)連通分量是一個(gè)極大連通子圖(maximalconnectedsubgraph),因?yàn)槿我饧右粋€(gè)結(jié)點(diǎn)以后將成為非連通圖Whohasthemostfriends?Thedegree

ofavertexisthenumberofedgesadjacenttoit.生成樹連通無圈圖稱為樹(tree)樹的集合稱為森林(forest)生成樹:包含某圖G所有點(diǎn)的樹生成森林:包含某圖G所有點(diǎn)的森林一個(gè)圖G是樹當(dāng)且僅當(dāng)以下任意一個(gè)條件成立G有V-1條邊,無圈G有V-1條邊,連通任意兩點(diǎn)只有唯一的簡單路徑G連通,但任意刪除一條邊后不連通還有其他條件,可類似定義完全圖和補(bǔ)圖如果V個(gè)點(diǎn)的圖有V(V-1)/2圖,稱為完全圖對(duì)于(u,v),若鄰接則改為非鄰接,若非鄰接則改為鄰接,得到的圖為原圖的補(bǔ)圖原圖和補(bǔ)圖(complementgraph)的并(union)為完全圖完全子圖稱為團(tuán)(clique)術(shù)語示意二分圖可以把結(jié)點(diǎn)分成兩部分,每部分之間沒有邊.這樣的圖只有奇圈(odd-cycle),即包含奇數(shù)條邊的圈許多困難問題在二分圖上有有效算法相交圖、區(qū)間圖交圖:把物體看作頂點(diǎn),相交關(guān)系看為邊特殊情況:區(qū)間圖(intervalgraph).很多困難問題在區(qū)間圖上有有效算法DataStructuresforgraphDataStructuresforGraphsTherearetwomaindatastructuresusedtorepresentgraphs.AdjacencyMatrix(鄰接矩陣)AdjacencyLists(鄰接表)ForwardStar(向前星)WeassumethegraphG=(V,E)containsn=|V|verticesandm=|E|edges.AdjacencyMatrixRepresentationAdjacencyMatrixRepresentationAdjacencymatrixrepresentationforweightedgraphAdjacencyMatrixRepresentationintn;//numofvertexintm;//numofedgesintu,v;//vertexofedge(u,v)cin>>n>>m;intg[n+1][n+1];//storethegraphmemset(g,0,sizeof(g));for(intj=1;j<=m;j++){cin>>u>>v;g[u][v]=1;

if(directed==false)g[v][u]=1;}相關(guān)問題如何處理重邊和自環(huán)?如何用位存儲(chǔ)節(jié)省空間?如果用上三角法儲(chǔ)存無向圖?如何用邊測試函數(shù)而非完整的鄰接矩陣儲(chǔ)存隱式圖?如何修改A的元素類型以儲(chǔ)存邊的附加信息?AdjacencyListsRepresentationAdjacencyListsRepresentationThesetofverticesisacontiguouslistThesetofadjacentverticesisalinkedlistDirectedgraphAdjacencyListsRepresentationUndirectedgraphAdjacencyListsRepresentationintn;//numofvertexintm;//numofedgesintu,v;//vertexofedge(u,v)cin>>n>>m;vector<int>g[n+1];//storethegraphfor(intj=1;j<=m;j++){cin>>u>>v;g[u].push_back(v);

if(directed==false)g[v].push_back(u);}相關(guān)問題鄰居排序方式可能影響結(jié)果查找/刪除邊不是常數(shù)時(shí)間鄰接表的空間O(V+E),對(duì)于稀疏圖優(yōu)于鄰接矩陣可以用編號(hào)代替指針,加快速度并節(jié)省空間Forweightedgraph,storeneighboringverticesandtheiredgecostsIfnecessary,thetwocopiesofeachedgecanbelinkedbyapointertofacilitatedeletions.TradeoffsBetweenAdjacencyListsandAdjacencyMatricesComaprisonWinner

Fastertotestif(x,y)exists?matrices

Fastertofindvertexdegree?lists

Fastertofindvertexdegree?lists

Lessmemoryonsmallgraphs?listsO(m+n)vs.O(n2)Lessmemoryonbiggraphs?matrices(smallwin)Edgeinsertionordeletion?matricesO(1)vsO(d)Fastertotraversethegraph?listsO(m+n)vs.O(n2)Betterformostproblems?lists

Question–AdjacencyMatrixorList?

Wouldyouusetheadjacencyliststructureortheadjacencymatrixstructureineachofthefollowingcases?Justifyyourchoice.Thegraphhas10,000verticesand20,000edges.

Itisimportanttouseaslittlespaceaspossible.

Answer:Useadjacencylistasthereareonaverage2edgesoneachvertex.

Wewillwastealotofmemoryspaceifadjacencymatrixisused.

Thegraphhas10,000verticesand20,000,000edges.

Itisimportanttouseaslittlespaceaspossible.

Answer:Useadjacencymatrixasthereareonaverage2000edgesoneachvertex.

Itwouldbemuchfastertofindtheneighborsofeachvertex.

YouneedtoanswerthequeryareAdjacentasfastaspossible.

Nomatterhowmuchspaceyouuse.

Answer:UseadjacencyMatrixsincespaceisnotaproblem.

Moreimportantly,thequeryareAdjacentcanbeansweredinO(1)time.

前向星表示把所有邊(u,v)按u的主關(guān)鍵字,v為次關(guān)鍵字排序,并記錄每個(gè)結(jié)點(diǎn)u的鄰居列表的開始位置start[u](則start[u+1]是結(jié)束位置)緊湊存儲(chǔ),不需要使用指針,但邊的插入和刪除操作可能引起大幅度變化.一般用于靜態(tài)圖.可以方便的遍歷一個(gè)點(diǎn)的所有鄰居并通過可以儲(chǔ)存”當(dāng)前弧”提高某些圖算法的效率ThinkAboutPresentcorrectandefficientalgorithmstoconvertbetweenthefollowinggraphdatastructures,foranundirectedgraphGwithnverticesandmedges.Youmustgivethetimecomplexityofeachalgorithm.1.Convertfromanadjacencymatrixtoadjacencylists.2.Convertfromanadjacencymatrixtoadjacencylists.GraphtraversalbasicTraversingaGraphOneofthemostfundamentalgraphproblemsistotraverseeveryedgeandvertexinagraph.efficiency:visiteachedgeatmosttwice.correctness:dothetraversalinasystematicwaysothatwedon’tmissanything.MarkingVerticesThekeyideaisthatwemustmarkeachvertexwhenwefirstvisitit,andkeeptrackofwhathavenotyetcompletelyexplored.Eachvertexwillalwaysbeinoneofthefollowingthreestates:

undiscovered

–thevertexinitsinitial,virginstate.

discovered

–thevertexafterwehaveencounteredit,butbeforewehavecheckedoutallitsincidentedges.

processed

–thevertexafterwehavevisitedallitsincidentedges.MarkingVertices必須在訪問一個(gè)結(jié)點(diǎn)后再給它加上一個(gè)標(biāo)記，使得它不會(huì)被重復(fù)訪問。BFS和DFS的區(qū)別在于訪問結(jié)點(diǎn)的順序。任意結(jié)點(diǎn)總處于以下狀態(tài)中的一種:

undiscovered

–所有結(jié)點(diǎn)的初始狀態(tài).

discovered

–結(jié)點(diǎn)第一次被訪問，但它的出邊未處理完畢。

processed

–結(jié)點(diǎn)的所有出邊都已經(jīng)處理完畢。MarkingVerticesObviously,avertexcannotbeprocessed

beforewediscoverit,sooverthecourseofthetraversalthestateofeachvertexprogressesfromundiscovered

todiscovered

toprocessed.ToDoListWemustalsomaintainastructurecontainingalltheverticeswehavediscoveredbutnotyetprocessed.Initially,onlyasinglestartvertexisconsideredtobediscovered.Tocompletelyexploreavertex,welookateachedgegoingoutofit.Foreachedgewhichgoestoanundiscoveredvertex,wemarkitdiscovered

andaddittothelistofworktodo.Notethatregardlessofwhatorderwefetchthenextvertextoexplore,eachedgeisconsideredexactlytwice,wheneachofitsendpointsareexplored.Breadth-FirstSearchBFS基本算法由Moore和Lee獨(dú)立提出給定圖G和一個(gè)源點(diǎn)s,寬度優(yōu)先遍歷按照從近到遠(yuǎn)的順序考慮各條邊.算法求出從s到各點(diǎn)的距離寬度優(yōu)先的過程對(duì)結(jié)點(diǎn)著色.白色(undiscovered):沒有考慮過的點(diǎn)黑色(processed):已經(jīng)完全考慮過的點(diǎn)灰色(discovered):發(fā)現(xiàn)過,但沒有處理過,是遍歷邊界依次處理每個(gè)灰色結(jié)點(diǎn)u,對(duì)于鄰接邊(u,v),把v著成灰色并加入樹中,在樹中u是v的父親(parent)或稱前驅(qū)(predecessor).距離d[v]=d[u]+1整棵BFS樹的根為sBFS(G,s)1foreachvertexu∈V[G]-{s}2docolor[u]←WHITE3d[u]←∞4p[u]←NIL5color[s]←GRAY6d[s]←07p[s]←NIL8Q←?9ENQUEUE(Q,s)10whileQ≠?11dou←DEQUEUE(Q)12foreachv∈Adj[u]13doifcolor[v]=WHITE14thencolor[v]←GRAY15d[v]←d[u]+116p[v]←u17ENQUEUE(Q,v)18color[u]←BLACKvoidbfs(ints){queue<int>c;color[s]=1;dist[s]=0;parent[s]=-1;c.push(s);while(!c.empty()){u=c.front();c.pop();/*dosthwhenvertexdiscovered*/printf("%d",u);for(inti=0;i<graph[u].size();i++){v=graph[u][i];if(color[v]==0){color[v]=1;parent[v]=u;dist[v]=dist[u]+1;c.push(v);//dosthtotheedge(u,v)}}color[u]=2;}}voidbfs(){memset(color,0,sizeof(color));memset(dist,-1,sizeof(dist));memset(parent,-1,sizeof(parent));for(inti=1;i<=n;i++){if(color[i]==0)//vertexiisundiscoveredbfs(i);}}intmain(){read(false);printf("vertexdiscoverd:");bfs();printf("\n");printf("pathfrom1to4:");find_path(1,4,parent);printf("\n");}FindingPathsTheparentarraysetwithinbfs()isveryusefulforfindinginterestingpathsthroughagraph.Thevertexwhichdiscoveredvertexiisdefinedasparent[i].Theparentrelationdefinesatreeofdiscoverywiththeinitialsearchnodeastherootofthetree.RecursionandPathFindingfind_path(intstart,intend,intparents[]){ if((start==end)&&(end==-1))printf(”%d”,start);else{find_path(start,parents[end],parents);printf(”%d”,end);}}vertex123456parent-112511ShortestPathsinUnweightedGraphandBFSInBFS,verticesarediscoveredinorderofincreasingdistancefromtheroot,sothistreehasaveryimportantproperty.Theuniquetreepathfromtheroottoanynodex∈Vusesthesmallestnumberofedges(orequivalently,intermediatenodes)possibleonanyroot-to-xpathinthegraph.用BFS求最短路定理:對(duì)于無權(quán)圖(每條邊的長度為1),BFS算法計(jì)算出的d[i]是從s到i的最短路滿足d[i]=1的點(diǎn)一定是正確的(因?yàn)殚L度至少為1),并且其他點(diǎn)都滿足d[i]>1.容易證明對(duì)于任意距離值x,d[i]=x的點(diǎn)一定是正確的,而且白色點(diǎn)(沒有計(jì)算出距離的點(diǎn))的距離一定至少為x+1更進(jìn)一步,根據(jù)每個(gè)點(diǎn)的parent值,可以計(jì)算出它到s的一條最短路ConnectedComponentsTheconnectedcomponents

ofanundirectedgrapharetheseparate“pieces”ofthegraphsuchthatthereisnoconnectionbetweenthepieces.AnythingwediscoverduringaBFSmustbepartofthesameconnectedcomponent.Wethenrepeatthesearchfromanyundiscoveredvertex(ifoneexists)todefinethenextcomponent,untilallverticeshavebeenfound:voidconnected_components(){intcc=0;//cc:numofconnectedcomponentsmemset(color,0,sizeof(color));memset(dist,-1,sizeof(dist));memset(parent,-1,sizeof(parent));

for(inti=1;i<=n;i++){if(color[i]==0)//vertexiisundiscovered{++cc;printf("Component%d:",cc);bfs(i);printf("\n");}}}Two-ColoringGraphsThevertexcoloring

problemseekstoassignalabel(orcolor)toeachvertexofagraphsuchthatnoedgelinksanytwoverticesofthesamecolor.Agraphisbipartite

ifitcanbecoloredwithoutconflictswhileusingonlytwocolors.Bipartitegraphsareimportantbecausetheyarisenaturallyinmanyapplications.boolbicoloring(ints){queue<int>c;intpaint[MAXN];/*0未染色，1紅色，-1黑色*/memset(color,0,sizeof(color));memset(paint,0,sizeof(paint));color[s]=1;c.push(s);while(!c.empty()){u=c.front();c.pop();for(inti=0;i<graph[u].size();i++){v=graph[u][i];if(color[v]==1){if(paint[v]==-paint[u])continue;elsereturnfalse;}color[v]=1;paint[v]=-paint[u];c.push(v);}}returntrue;}BFS相關(guān)思考題給出判斷圖是否為二分圖的線性時(shí)間算法一棵樹T的直徑定義為結(jié)點(diǎn)兩兩間距離的最大值.給出求樹直徑的線性時(shí)間算法對(duì)無向圖G,給出一個(gè)路徑,經(jīng)過每條邊恰好兩次(一個(gè)方向一次).如何利用這條路徑來走迷宮?Depth-FirstSearch基本算法新發(fā)現(xiàn)的結(jié)點(diǎn)先擴(kuò)展。（可以把BFS程序中的隊(duì)列直接改成棧）得到的可能不是一棵樹而是森林,即深度優(yōu)先森林(Depth-firstforest)特別之處:引入時(shí)間戳(timestamp)發(fā)現(xiàn)時(shí)間pre[v]:變灰的時(shí)間結(jié)束時(shí)間post[v]:變黑的時(shí)間1<=pre[v]<post[v]<=2|V|初始化:time為0,所有點(diǎn)為白色,dfs森林為空對(duì)每個(gè)白色點(diǎn)u執(zhí)行一次DFS-VISIT(u)DFS(G)1foreachvertexu∈V[G]2docolor[u]←WHITE3parent[u]←NIL4time←05foreachvertexu∈V[G]6doifcolor[u]=WHITE7thenDFS-VISIT(u)DFS-VISIT(u)1color[u]←GRAY//Whitevertexuhasjustbeendiscovered.2pre[u]=++time4foreachv∈Adj[u]//Exploreedge(u,v).5doifcolor[v]=WHITE6thenparent[v]←u7DFS-VISIT(v)8color[u]=BLACK//Blackenu,itisfinished.9post[u]=++timeDepth-FirstSearchDFS樹的性質(zhì)括號(hào)結(jié)構(gòu)性質(zhì)對(duì)于任意結(jié)點(diǎn)對(duì)(u,v),考慮區(qū)間[pre[u],post[u]]和[pre[v],post[v]],以下三個(gè)性質(zhì)恰有一個(gè)成立:完全分離u的區(qū)間完全包含在v的區(qū)間內(nèi),則在dfs樹上u是v的后代v的區(qū)間完全包含在u的區(qū)間內(nèi),則在dfs樹上v是u的后代三個(gè)條件非常直觀DFS樹的性質(zhì)定理1(嵌套區(qū)間定理):在DFS森林中v是u的后代當(dāng)且僅當(dāng)pre[u]<pre[v]<post[v]<post[u],即區(qū)間包含關(guān)系.由區(qū)間性質(zhì)立即得到.定理2(白色路徑定理):在DFS森林中v是u的后代當(dāng)且僅當(dāng)在pre[u]時(shí)刻(u剛剛被發(fā)現(xiàn)),v可以由u出發(fā)只經(jīng)過白色結(jié)點(diǎn)到達(dá).證明:由嵌套區(qū)間定理可以證明EdgeClassificationforDFSTreeedgesareactuallypartoftheDFSforest.Backedges

leadtoanancestorintheDFStree.ForwardedgesleadfromanodetoanonchilddescendantintheDFStree.Crossedges

leadtoneitherdescendantnorancestor;theythereforeleadtoanodethathasalreadybeencompletelyexplored(thatis,alreadyprocessed).邊分類規(guī)則一條邊(u,v)可以按如下規(guī)則分類樹邊(TreeEdges,T):v通過邊(u,v)發(fā)現(xiàn),后向邊(BackEdges,B):u是v的后代前向邊(ForwardEdges,F):v是u的后代交叉邊(CrossEdges,C):

其他邊，可以連接同一個(gè)DFS樹中沒有后代關(guān)系的兩個(gè)結(jié)點(diǎn),也可以連接不同DFS樹中的結(jié)點(diǎn)判斷后代關(guān)系

可以借助定理1邊分類算法當(dāng)(u,v)第一次被遍歷,考慮v的顏色白色,(u,v)為Tree邊灰色,(u,v)為Back邊(只有它的祖先是灰色)黑色:(u,v)為Forward邊或Cross邊.此時(shí)需要進(jìn)一步判斷pre[u]<pre[v]:Forward邊(v是u的后代,因此為F邊)pre[u]>pre[v]:Cross邊(v早就被發(fā)現(xiàn)了,為另一DFS樹中)時(shí)間復(fù)雜度:O(n+m)定理:無向圖只有Tree邊和Back邊DFS數(shù)的性質(zhì)演示實(shí)現(xiàn)細(xì)節(jié)顏色值以及時(shí)間戳可以省略,用pre[u]和post[u]代表點(diǎn)u的先序/后序編號(hào),則檢查(u,v)可以寫為if(pre[v]==0)dfs(v);//樹邊,遞歸遍歷elseif(post[v]==0)show(“Back”);//后向邊elseif(pre[v]>pre[u])show(“Forward”);//前向邊elseshow(“Cross”);//交叉邊pre和post的初值均為0/*有向圖的深度優(yōu)先搜索標(biāo)記

INIT:edge[][]鄰接矩陣;pre[],post[],tag全置0;CALL:dfstag(i,n);pre/post:開始/結(jié)束時(shí)間*/intedge[V][V],pre[V],post[V],tag=0;voiddfstag(intcur,intn){//vertex:0~n-1pre[cur]=++tag;for(inti=0;i<n;++i)if(edge[cur][i]){if(0==pre[i]){printf("TreeEdge!\n");dfstag(i,n);}else{if(0==post[i])printf("BackEdge!\n");elseif(pre[i]>pre[cur])printf("DownEdge!\n");elseprintf("CrossEdge!\n");}}post[cur]=++tag;}DFSinUndirectedGraph:

NoCrossEdgesinDFSWhenexpanding2,wewoulddiscover5,sothetreewouldlooklike:DFSApplication:FindingCyclesBackedgesarethekeytofindingacycleinanundirectedgraph.Anybackedgegoingfromxtoanancestorycreatesacyclewiththepathinthetreefromytox.無根樹轉(zhuǎn)有根樹輸入一個(gè)n個(gè)結(jié)點(diǎn)的無根樹的各條邊，并指定其中一個(gè)結(jié)點(diǎn)作為結(jié)點(diǎn)，要求把該樹轉(zhuǎn)化為有根樹，輸出各個(gè)結(jié)點(diǎn)的父親編號(hào)。n<=10^6。無根樹轉(zhuǎn)有根樹存儲(chǔ)結(jié)構(gòu)n太大，鄰接矩陣存儲(chǔ)不合適。借用vector,空間O(n)vector<int>g[maxn];voidread_tree(){intu,v;scanf(“%d”,&n);for(inti=0;i<n-1;i++){scanf(“%d”,&u,&v);g[u].push_back(v);g[v].push_back(u);}}無根樹轉(zhuǎn)有根樹轉(zhuǎn)化過程voiddfs(intu,intfa)//遞歸轉(zhuǎn)化u為根的子樹,u的父親為fa{intd=g[u].size();//結(jié)點(diǎn)u的相鄰點(diǎn)個(gè)數(shù)for(inti=0;i<d;i++){intv=g[u][i];//結(jié)點(diǎn)u的第i個(gè)相鄰點(diǎn)//把v的父親設(shè)為u，然后遞歸轉(zhuǎn)化以v為根的子樹if(v!=fa)dfs(v,p[v]=u);}主程序中設(shè)置p[root]=-1（表示根節(jié)點(diǎn)的父親不存在），然后調(diào)用dfs(root,-1)即可。練習(xí)對(duì)于三種顏色WHITE,GRAY和BLACK,作一個(gè)3*3表格,判斷一種顏色到另一種顏色是否可能有邊,如有可能,邊的類型如何對(duì)于邊(u,v),證明它是T或F邊當(dāng)且僅當(dāng)pre[u]<pre[v]<post[v]<post[u]B邊當(dāng)且僅當(dāng)pre[v]<pre[u]<post[u]<post[v]C邊當(dāng)且僅當(dāng)pre[v]<post[v]<pre[u]<post[u]如何區(qū)分T邊和F邊?修改DFS算法,使得對(duì)于無向圖,可以求出每個(gè)點(diǎn)i所處的連通分量編號(hào)cc[i]TopologicalSortingIngraphtheory,atopologicalsortortopologicalorderingofadirectedacyclicgraph(DAG)isalinearorderingofitsnodesinwhicheachnodecomesbeforeallnodestowhichithasoutboundedges.EveryDAGhasoneormoretopologicalsorts.Moreformally,definethereachabilityrelationRoverthenodesoftheDAGsuchthatxRyifandonlyifthereisadirectedpathfromxtoy.Then,Risapartialorder,andatopologicalsortisalinearextensionofthispartialorder,thatis,atotalordercompatiblewiththepartialorder.TopologicalOrder(拓?fù)漤樞?DressingOrderApplicationsofTopologicalSortingThecanonicalapplicationoftopologicalsorting(topologicalorder)isinschedulingasequenceofjobsortasks;topologicalsortingalgorithmswerefirststudiedintheearly1960sinthecontextofthePERTtechniqueforschedulinginprojectmanagement(Jarnagin1960).Incomputerscience,applicationsofthistypeariseininstructionscheduling,orderingofformulacellevaluationwhenrecomputingformulavaluesinspreadsheets,logicsynthesis,determiningtheorderofcompilationtaskstoperforminmakefiles,andresolvingsymboldependenciesinlinkers.ExampleofTopologicalSortingThegraphshowntothelefthasmanyvalidtopologicalsorts,including:7,5,3,11,8,2,9,10(visualleft-to-right,top-to-bottom)3,5,7,8,11,2,9,10(smallest-numberedavailablevertexfirst)3,7,8,5,11,10,2,95,7,3,8,11,10,9,2(leastnumberofedgesfirst)7,5,11,3,10,8,9,2(largest-numberedavailablevertexfirst)7,5,11,2,3,8,9,10

TopologicalSortingAlgorithmOneKahn(1962),(O(|V|+|E|)).First,findathecompletesetof“sourcevertices"whichhavenoincomingedges;atleastonesuchnodemustexistifgraphisacyclic.Deletingalltheoutgoingedgesofthesesourceverticeswillcreatenewsourcevertices,whichcanthensitcomfortablytotheimmediaterightofthefirstset.Werepeatuntilallverticesareaccountedfor.TopologicalSortingAlgorithmOne

L←EmptylistthatwillcontainthesortedelementsS←Setofallnodeswithnoincomingedges

whileSisnon-emptydo

removeanodenfromSinsertnintoL

foreachnodemwithanedgeefromntomdo

removeedgeefromthegraph

ifmhasnootherincomingedgesthen

insertmintoSifgraphhasedgesthen

outputerrormessage(graphhasatleastonecycle)elseoutputmessage(proposedtopologicallysortedorder:L)TopologicalSortingAlgorithmOneIfthegraphwasaDAG,asolutioniscontainedinthelistL(thesolutionisnotunique).Otherwise,thegraphhasatleastonecycleandthereforeatopologicalsortingisimpossible.Notethat,reflectingthenon-uniquenessoftheresultingsort,thestructureScanbesimplyasetoraqueueorastack.DependingontheorderthatnodesnareremovedfromsetS,adifferentsolutioniscreated.TopologicalSortAlgorithmTwoPerformedonaDAG.LinearorderingoftheverticesofGsuchthatif(u,v)E,thenuappearssomewherebeforev.Topological-Sort(G)callDFS(G)

tocomputefinishingtimesf[v]forallv

Vaseachvertexisfinished,insertitontothefrontofalinkedlistreturnthelinkedlistofverticesTime:

(V+E).TopologicalSortExample

LinkedList:ABDCE1/TopologicalSortExample

LinkedList:ABDCE1/2/TopologicalSortExample

LinkedList:ABDCE1/2/3

E2/3TopologicalSortExample

LinkedList:ABDCE1/42/3

E2/3

1/4DTopologicalSortExample

LinkedList:ABDCE1/42/3

E2/3

1/4D5/TopologicalSortExample

LinkedList:ABDCE1/42/3

E2/3

1/4D5/6/TopologicalSortExample

LinkedList:ABDCE1/42/3

E2/3

1/4D5/6/7

6/7CTopologicalSortExample

LinkedList:ABDCE1/42/3

E2/3

1/4D5/86/7

6/7C

5/8BApplicationToposort假設(shè)有n個(gè)變量，還有m個(gè)二元組(u,v)，表示變量u<v。那么，所有變量從小到大排列起來應(yīng)該是什么樣子的呢？例如有4個(gè)變量a,b,c,d，若已知a<b,c<b,d<c,則這4個(gè)變量的排序可能是a<d<c<b?？赡苡卸喾N排序結(jié)果(如d<a<c<b)，你只需找出其中一個(gè)即可。ApplicationToposortintcolor[MAXN],topo[MAXN],t;booldfs(intu){ color[u]=1;//uisdiscovered for(intv=0;v<n;v++)if(G[u][v]) { if(color[v]==1)returnfalse;//backedgeexist elseif(!color[v]&&!dfs(v))returnfalse; } color[u]=2;topo[--t]=u;returntrue;}booltoposort(){ t=n;memset(color,0,sizeof(color)); for(intu=0;u<n;u++)if(!c[u]&&!dfs(u)) returnfalse; returntrue;}StronglyConnectedComponentsGisstronglyconnectedifeverypair(u,v)ofverticesinGisreachablefromoneanother.Astronglyconnectedcomponent

(SCC)ofGisamaximalsetofverticesC

Vsuchthatforallu,v

C,bothu

vandv

uexist.StronglyConnectedComponentsThestronglyconnectedcomponentsofagraphisapartitionoftheverticesintosubsets(maximal)suchthateachsubsetisstronglyconnected.StronglyConnectedComponentsThereisanelegant,lineartimealgorithmtofindthestronglyconnectedcomponentsofadirectedgraphusingDFSwhichissimilartothealgorithmforbiconnectedcomponents.Thealgorithmisbasedontheobservationthatitiseasytofindadirectedcycleusingadepth-firstsearch,sinceanybackedgeplusthedownpathintheDFStreegivessuchacycle.Allverticesinthecyclemustbeinthesamestronglyconnectedcomponent.Thus,wecanshrinktheverticesonthiscycledowntoasinglevertexrepresentingthecomponent,andthenrepeat.Thisprocessterminateswhennodirectedcycleremains,andeachvertexrepresentsadifferentSCC.StronglyConnectedComponentsStronglyConnectedGraphHowtoknowwhetheradirectedgraphisstronglyconnected?

Thesimplestlinear-timealgorithmperformsasearchfromsomevertexvtodemonstratethattheentiregraphisreachablefromv.WethenconstructagraphG’wherewereversealltheedgesofG.AtraversalofG’fromvsufficestodecidewhetherallverticesofGcanreachv.KosarajualgorithmtodetermineSCCsSCC(G)callDFS(G)

tocomputefinishingtimesf[u]forallucomputeGTcallDFS(GT),butinthemainloop,considerverticesinorderofdecreasingf[u].(asinline1,topologicalorder)outputtheverticesineachtreeofthedepth-firstforestformedinsecondDFSasaseparateSCCTime:

(V+E).Example13/1412/153/42/711/161/10abcefg5/68/9hdGinorderofdecreasingf[u]:b,e,a,c,d,g,h,fExampleabcefghdGTinorderofdecreasingf[u]:b,e,a,c,d,g,h,fExamplecdhfgabeKosaruju算法的正確性?當(dāng)按照f值排序以后,第二次DFS是按照SCC的拓?fù)漤樞蜻M(jìn)行(以后所指d[u]和f[u]都是第一次DFS所得到的值)?記d(C)和f(C)分別表示集合U所有元素的最早發(fā)現(xiàn)時(shí)間和最晚完成時(shí)間,有如下定理:?定理:對(duì)于兩個(gè)SCCC和C’,如果C到C’有邊,則f(C)>f(C’)–情況一:d(C)<d(C’),考慮C中第一個(gè)被發(fā)現(xiàn)的點(diǎn)x,則C’全為白色,而C到C’有邊,故x到C’中每個(gè)點(diǎn)都有白色路徑.這樣,C和C’全是x的后代,因此f(C)>f(C’)–情況二:d(C)>d(C’).由于從C’不可到達(dá)C,因此必須等C’全部訪問完畢才能訪問C.因此f(C)>f(C’)?推論:對(duì)于兩個(gè)SCCC和C’,如果在GT中C到C’有邊,則f(C)<f(C’)Kosaruju算法的正確性?首先考慮f(C)最大的強(qiáng)連通分量.顯然,此次DFS將訪問C的所有點(diǎn),問題是是否可能訪問其他連通分量的點(diǎn)?答案是否定的,因?yàn)楦鶕?jù)推論,如果在GT中C到另外某個(gè)C’存在邊,一定有f(C)<f(C’),因此第一棵DFS恰好包含C.由數(shù)學(xué)歸納法可知,每次從當(dāng)前強(qiáng)連通分量出發(fā)的邊一定連到f值更大的強(qiáng)連通分量,而它們是已經(jīng)被遍歷過的,不會(huì)在DFS樹形成多余結(jié)點(diǎn)局限性?SCC算法的簡單歷史–第一個(gè)SCC算法:Tarjan1972(經(jīng)典算法)–80年代:精美的Kosaraju算法