圖論的基本算法-wenkub
2022-10-28 15:10:01 本頁(yè)面
【正文】 ] ] ] endP Car的旅行路線 ? 又到暑假了，住在城市 A的 Car想和朋友一起去城市 B旅游。 {s存儲(chǔ)被標(biāo)號(hào)的頂點(diǎn) } for k:=1 to vtxnum1 do [ wm:=max。 {存儲(chǔ)路徑長(zhǎng)度 } path:array[vtxptr] of set。 if size = n – 1 then break。 ? Kruskal算法是生成森林子集系統(tǒng)的貪心算法！ ?貪心算法在什么子集系統(tǒng)下是的對(duì)的呢？ ? 定理 ?貪心算法正確，當(dāng)且僅當(dāng)這個(gè)系統(tǒng)的極大獨(dú)立集具有相同的基數(shù) ?滿足條件的子集系統(tǒng)稱為“矩陣胚 (matroid)” 快速判斷是否產(chǎn)生圈 ? 需要借助數(shù)據(jù)結(jié)構(gòu)！ ? 我們的算法要求 ?判斷兩個(gè)點(diǎn)是否在同一棵樹(shù)中 ? 產(chǎn)生圈當(dāng)且僅當(dāng)此邊連接同一樹(shù)中的點(diǎn)！ ?快速把兩棵樹(shù)合并 ? 加邊意味著兩棵樹(shù)合為一棵 ?抽象數(shù)據(jù)類(lèi)型：并查集！ ? 經(jīng)典實(shí)現(xiàn)：森林 ? 并查集的森林實(shí)現(xiàn) ?森林中的每棵樹(shù)表示不同的集合 ?樹(shù)的形態(tài)并不重要，有意義的只是“哪些元素在樹(shù)中” 并查集的操作 ? 查找 ?用樹(shù)根作為集合的標(biāo)識(shí) ?不斷的找父親，最終將找到樹(shù)根 ? 要找多少次父親？和樹(shù)的高度有關(guān)！ ? 怎樣減少樹(shù)的高度？ ? 找到樹(shù)根后沿途把路徑上的結(jié)點(diǎn)的父親設(shè)為根 ? 專門(mén)名稱：路徑壓縮 ?兩元素所在的樹(shù)根相同，則二者屬于同一集合 ? 合并 ?其中一棵樹(shù)成為另一棵樹(shù)樹(shù)根的子樹(shù) ?誰(shuí)成為誰(shuí)的子樹(shù)？注意樹(shù)的高度！ ? 啟發(fā)式合并 ? 時(shí)間復(fù)雜度：幾乎都為常數(shù)！ 并查集的實(shí)現(xiàn) ? 回憶剛才用到了什么信息？ ?查找：“不斷的找父親” …“ 沿途設(shè)置結(jié)點(diǎn)的父親為樹(shù)根” ?合并：“把一棵樹(shù)的父親設(shè)置為另一棵樹(shù)的樹(shù)根” ?只有“父親”信息！ ? 父親表示法！ ? father : array[1..maxn] of integer。 ?該極大獨(dú)立集的基數(shù)為它包含的元素個(gè)數(shù) ? 在剛才介紹的子集系統(tǒng)中， G的所有生成樹(shù)就是所有的極大獨(dú)立集。 每次取最小值為 O(logm) 總時(shí)間復(fù)雜度為 O(nlogm) Kruskal算法 ? 任意時(shí)刻的中間結(jié)果是一個(gè)森林 ?從 n個(gè)點(diǎn)的集合開(kāi)始 ?每次選不產(chǎn)生圈的前提下權(quán)最小的邊加入 ? 問(wèn)題： ?這樣做是對(duì)的嗎？ ?如何快速的判斷是否產(chǎn)生圈 Kruskal算法的正確性 ? 把一個(gè)二元組 (E, I)叫做一個(gè)子集系統(tǒng)，如果滿足： ? 1． E是一個(gè)非空集合 ? 2． I是 E的一個(gè)子集族，它在包含運(yùn)算下封閉，即 I的每個(gè)元素 a都是 E的一個(gè)子集，并對(duì)于 a的任何子集 a’，a’一定也是 I的元素。 另一個(gè)例子 ? 考古學(xué)家發(fā)現(xiàn)了一塊布，布上做有針線活，叫做“十字繡” ? 交替地在布的兩面穿線 ? 布是一個(gè) n m的網(wǎng)格 ? 線只能在網(wǎng)格的頂點(diǎn)處才能從布的一面穿到另一面。 ? 那么，如果從房屋踏上走廊，門(mén)被漆成綠色；從走廊踏進(jìn)房屋，門(mén)被漆成黃色。 ? k:=nextadj(dig,j,k) ? ] ? ] ? if mn then return(false) else return(true)。 ? k:=firstadj(dig,j)。 m:=0。 end。 arode=record adjvex:vtxptr。圖論 朱全民 圖 ? 圖的概念 G=(V,E) ? 圖的基本概念 ? 有向圖、頂點(diǎn)、入度、出度、弧、環(huán) ? 無(wú)向圖、邊、路徑、頂點(diǎn)的度、鄰接 ? 簡(jiǎn)單圖、完全圖 ? 平面圖、二分圖 圖的存儲(chǔ)結(jié)構(gòu) ? 鄰接矩陣 graph=Record vex:array[1..vtxptr] of vertex。 nextarc:arcptr。 adjlist=array [vtxptr] of vexnode。 ve[1..n]:=0 ? while Not empty(top1) do ? [ j:=pop(top1)。 ? while k0 do ? [ 入度 (k):=入度 (k)1。 ? endF。由于走廊只走一次，因此，每間房屋進(jìn)出的次數(shù)一樣，因此，任意一間房屋的門(mén)，綠色門(mén)和黃色門(mén)的數(shù)量一樣。 ? 每一段線都覆蓋一個(gè)單位網(wǎng)格的兩條對(duì)角線之一 ? 而在繡的過(guò)程中，一針中連續(xù)的兩段線必須分處布的兩面 ? 給出布兩面的圖案（實(shí)線代表有線，虛線代表背面有線） ? 最少需要幾針才能繡出來(lái)？ ? 一針是指針不離開(kāi)布的一次繡花過(guò)程。 ? 3．給 E中每個(gè)元素 e賦予一個(gè)正權(quán) w(e)。所有極大獨(dú)立集具有相同的基數(shù) |V|1。 ?根結(jié)點(diǎn) root滿足 father[root] := root ?查找： while father[p] p do p := father[p]。 end。 {存儲(chǔ)路徑 } for i:=1 to vxtmun do
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1