資源描述：
《圖論算法總結(jié)及圖論建?！酚蓵?huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、圖論算法總結(jié)圖的基本概念圖的基本概念二元組G(V,E)稱為圖(graph)。V為結(jié)點(diǎn)(node)或頂點(diǎn)(vertex)集。E為圖中結(jié)點(diǎn)之間的邊的集合。點(diǎn)，用數(shù)字0…n-1表示點(diǎn)對(duì)(u,v)稱為邊(edge)或稱弧(arc)對(duì)于邊(u,v)∈E-u和v鄰接(adjacent)-e和u、v關(guān)聯(lián)(incident)子圖(subgraph):邊的子集和相關(guān)聯(lián)的點(diǎn)集圖的基本概念有向圖：邊都是單向(unidirectional)的,因此邊(u,v)是有序數(shù)對(duì).有時(shí)用弧(arc)專指有向邊帶權(quán)圖：可以給邊加權(quán)(weight),成為帶權(quán)圖,或加權(quán)圖(we
2、ightedgraph).權(quán)通常代表費(fèi)用、距離等,可以是正數(shù),也可以是負(fù)數(shù)稠密性：邊和V(V-1)/2相比非常少的稱為稀疏圖(sparsegraph),它的補(bǔ)圖為稠密圖(densegraph)路徑和圈一條路徑(path)是一個(gè)結(jié)點(diǎn)序列,路上的相鄰結(jié)點(diǎn)在圖上是鄰接的如果結(jié)點(diǎn)和邊都不重復(fù)出現(xiàn),則稱為簡(jiǎn)單路徑(simplepath).如果除了起點(diǎn)和終點(diǎn)相同外沒有重復(fù)頂點(diǎn)和邊,稱為圈(cycle).不相交路(disjointpath)表示沒有除了起點(diǎn)和終點(diǎn)沒有公共點(diǎn)的路.更嚴(yán)格地-任意點(diǎn)都不相同的叫嚴(yán)格不相交路(vertex-disjointpa
3、th)-同理定義邊不相交(edge-disjointpath)路注意:漢語中圈和環(huán)經(jīng)?；煊?包括一些固定術(shù)語).由于一般不討論自環(huán)(self-loop),所以以后假設(shè)二者等價(jià)而不會(huì)引起混淆連通性如果任意兩點(diǎn)都有路徑,則稱圖是連通(connected)的,否則稱圖是非連通的.非連通圖有多個(gè)連通分量(connectedcomponent,cc),每個(gè)連通分量是一個(gè)極大連通子圖(maximalconnectedsubgraph)完全圖和補(bǔ)圖完全圖:N個(gè)頂點(diǎn)的圖，有N(N-1)/2個(gè)節(jié)點(diǎn)對(duì)于(u,v),若鄰接則改為非鄰接,若非鄰接則改為鄰接,得到
4、的圖為原圖的補(bǔ)圖完全圖=原圖∪補(bǔ)圖團(tuán)：完全子圖生成樹樹：N個(gè)點(diǎn)，N-1條邊的連通圖（無環(huán)連通圖）生成樹:包含某圖G所有點(diǎn)的樹一個(gè)圖G是樹當(dāng)且僅當(dāng)以下任意一個(gè)條件成立G有V-1條邊,無圈G有V-1條邊,連通任意兩點(diǎn)只有唯一的簡(jiǎn)單路徑G連通,但任意刪除一條邊后不連通圖例圖的表示方法介紹兩種圖的表示方法：鄰接矩陣與鄰接表V*V的二維數(shù)組A，A[i][j]=0,若(i,j)不相連，A[i][j]=1,若(i,j)相連圖1圖1的鄰接矩陣表示鄰接矩陣無向圖的鄰接矩陣是對(duì)稱的優(yōu)點(diǎn)：查找/刪除某條邊是O(1)的缺點(diǎn)遍歷某一點(diǎn)的鄰居是O(V)的空間復(fù)雜度很
5、大，O(V*V)每個(gè)結(jié)點(diǎn)的鄰居形成一個(gè)鏈表鄰接表圖2圖2的鄰接表表示優(yōu)點(diǎn)快速遍歷某點(diǎn)所有鄰居占用存儲(chǔ)空間小，是O（邊數(shù)）的，在稀疏圖上的效率遠(yuǎn)勝鄰接表缺點(diǎn)：查找/刪除邊不是常數(shù)時(shí)間鄰接表一、寬度優(yōu)先遍歷(BFS)二、深度優(yōu)先遍歷(DFS)圖的遍歷算法給定圖G和一個(gè)源點(diǎn)s,寬度優(yōu)先遍歷按照從近到遠(yuǎn)的順序考慮各條邊.算法求出從s到各點(diǎn)的距離寬度優(yōu)先的過程對(duì)結(jié)點(diǎn)著色.白色:沒有考慮過的點(diǎn)黑色:已經(jīng)完全考慮過的點(diǎn)灰色:發(fā)現(xiàn)過,但沒有處理過,是遍歷邊界依次處理每個(gè)灰色結(jié)點(diǎn)u,對(duì)于鄰接邊(u,v),把v著成灰色并加入樹中,在樹中u是v的父親(pare
6、nt)或稱前驅(qū)(predecessor).距離d[v]=d[u]+1整棵樹的根為s寬度優(yōu)先遍歷(BFS)題目大意：給出N*M個(gè)格子，給出K個(gè)已經(jīng)被淹沒的格子，其他格子都是干的，求最大的湖的面積（一個(gè)格子的面積視為1），如果兩個(gè)濕的格子四聯(lián)通（上下左右），則視為這兩個(gè)格子同屬于一個(gè)湖輸入格式：第一行N，M，K接下來K個(gè)格子的坐標(biāo)AvoidTheLakes（NOI題庫2405）Input3453222312311Output4樣例解釋#....##.##..新發(fā)現(xiàn)的結(jié)點(diǎn)先擴(kuò)展得到的可能不是一棵樹而是森林,即深度優(yōu)先森林(Depth-first
7、forest)特別之處:引入時(shí)間戳(timestamp)發(fā)現(xiàn)時(shí)間d[v]:變灰的時(shí)間結(jié)束時(shí)間f[v]:變黑的時(shí)間1<=d[v]8、V
9、深度優(yōu)先遍歷(DFS)初始化:time為0,所有點(diǎn)為白色,dfs森林為空對(duì)每個(gè)白色點(diǎn)u執(zhí)行一次DFS-VISIT(u)時(shí)間復(fù)雜度為O(n+m)深度優(yōu)先遍歷(DFS)括號(hào)結(jié)構(gòu)性質(zhì)對(duì)于任意結(jié)點(diǎn)對(duì)(u,v),考慮區(qū)間[d[u],f[u]]和[d[v],f[v]],以下三個(gè)性質(zhì)恰有一個(gè)成立:完全分離u的區(qū)間完全包含在v的區(qū)間內(nèi),則在dfs樹上u是v的后代v的區(qū)間完全包含在u的區(qū)間內(nèi),則在dfs樹上v是
10、u的后代DFS樹的性質(zhì)定理(嵌套區(qū)間定理):在DFS森林中v是u的后代當(dāng)且僅當(dāng)d[u]
