圖論的基本算法-文庫(kù)吧資料
2024-10-13 15:10本頁(yè)面
【正文】 v0。 s:=[v0]。 {存儲(chǔ)路徑 } for i:=1 to vxtmun do [dist[i]:=[v0,i]。v0:vtxptr) var dist:array[vtxptr] of weighttype。 end。 for i:=1 to m do if ei的兩個(gè)端點(diǎn) u, v不在同一個(gè)集合 then begin 合并 Su和 Sv inc(size)。 ?根結(jié)點(diǎn) root滿足 father[root] := root ?查找： while father[p] p do p := father[p]。 ? 子集優(yōu)化問題 ?在子集系統(tǒng) (E, I)中選取一個(gè)元素 S∈ I，使得 w(S)最大（定義 w(S)為 S中所有元素的權(quán)和） 子集優(yōu)化問題的貪心算法 ? 貪心算法 ?先把 E中元素按照權(quán)值從大到小排序?yàn)?e1,e2,… ?令集合 S=空集 ?然后每次嘗試著把 e1,e2,… ，添加到 S里面 ? 如果添加之后 S仍是獨(dú)立集，則添加成功 ? 如果 S不是獨(dú)立集，則由定義知以后無(wú)論怎樣繼續(xù)添加元素，得到的集合都不可能重新成為獨(dú)立集，因此撤消此添加操作。所有極大獨(dú)立集具有相同的基數(shù) |V|1。 子集優(yōu)化問題 ? 極大獨(dú)立集 ?把 I中的元素都稱為獨(dú)立集 ?對(duì)于 I中的元素 a，如果不存在 I中的另一個(gè)元素 a’使得 a是 a’的真子集，則稱 a是極大獨(dú)立集。 ? 3．給 E中每個(gè)元素 e賦予一個(gè)正權(quán) w(e)。 分析 ? 抽象成圖 ?網(wǎng)格交叉點(diǎn)：頂點(diǎn) ?正面的線：正邊 ?背面的線：負(fù)邊 ?有邊相連：連通塊 ? 每個(gè)連通塊分別求 ?對(duì)于某個(gè)頂點(diǎn) i ? |正邊數(shù) 負(fù)邊數(shù) |=K0時(shí) ? 以該頂點(diǎn)為開始或結(jié)束的針數(shù) =K ? 可以恰好為 K針 ?所有 K值加起來(lái)，除以 2（每一針有兩個(gè)端點(diǎn)） ? 注意差值為 0時(shí)，為 1針而不是 0針 最小生成樹問題 ? 要求連接所有島嶼 ? 電纜總長(zhǎng)度盡量小 400 250 1500 500 2500 Main lsland 750 600 Prim算法 ? 任意時(shí)刻的中間結(jié)果都是一棵樹 ?從一個(gè)點(diǎn)開始 ?每次都花最小的代價(jià)，用一條加進(jìn)一個(gè)新點(diǎn) ? 問題： ?這樣做是對(duì)的嗎？ ?如何快速找到這個(gè)“最小代價(jià)”？ Prim算法的正確性 ? 換一種說(shuō)法 ?如果存在一個(gè) MST，包含當(dāng)前所有邊 ?則也存在一個(gè) MST, 它包含最小代價(jià)邊 (u, v) ? 反證法！ ?假設(shè)存在這樣的 MST ?當(dāng)前結(jié)點(diǎn)集為 S，剩下的結(jié)點(diǎn)集為 T ?由于在 MST中 ST連通 ? 一定有跨越 ST的某邊 (u’,v’) ? 它不是最小代價(jià)邊 (u,v) ? 刪除 (u’,v’)，加入 (u,v)， S和 T分別連通，且 ST通過 (u,v)連通 ? 得到了一個(gè)更小的 MST！ 快速找到最小代價(jià) ? 需要借助數(shù)據(jù)結(jié)構(gòu)！ ? 我們的算法要求 ?快速取 /刪除最小值（邊權(quán)） ?允許插入邊（加入新點(diǎn)時(shí)插入它的關(guān)接邊） ?抽象數(shù)據(jù)類型：優(yōu)先隊(duì)列！ ? 經(jīng)典實(shí)現(xiàn)：堆！ Prim算法框架 初始化，樹僅含一個(gè)任意一點(diǎn) v0 把 v0的鄰邊插入堆 for i:=1 to n1 do begin 從堆中取出最小值，設(shè)邊為 (u’,v’)， v’為新點(diǎn) (u’,v’)加入生成樹中 v’和它所有不在樹中的鄰居組成的邊插入堆 end。 ? 每一段線都覆蓋一個(gè)單位網(wǎng)格的兩條對(duì)角線之一 ? 而在繡的過程中，一針中連續(xù)的兩段線必須分處布的兩面 ? 給出布兩面的圖案（實(shí)線代表有線，虛線代表背面有線） ? 最少需要幾針才能繡出來(lái)？ ? 一針是指針不離開布的一次繡花過程。 ? 然后按規(guī)律給門油漆，然后撤去所有虛設(shè)的走廊和門，由于被撤去的房屋的門最多只有一個(gè)，所以同樣保證綠色門的數(shù)量和黃色的門的數(shù)量相差不超過 1。由于走廊只走一次，因此，每間房屋進(jìn)出的次數(shù)一樣，因此，任意一間房屋的門，綠色門和黃色門的數(shù)量一樣。 ? 如何實(shí)現(xiàn)？ 分析 ? 如果每個(gè)房屋的門為偶數(shù)，那么幼兒園本身就是個(gè)歐拉回路。 ? endF。 ? if ve[j]+dut(j,k)ve[k] then ve[k]:=ve[j]+dut(j,k)。 ? while k0 do ? [ 入度 (k):=入度 (k)1。 m:=m+1。 ve[1..n]:=0 ? while Not empty(top1) do ? [ j:=pop(top1)。 ? init(top2)。 adjlist=array [vtxptr] of vexnode。 vex=Record vexdata: …{ 和頂點(diǎn)有關(guān)的其他信息 } firstarc:arcptr。 nextarc:arcptr。 ? 鄰接表 表節(jié)點(diǎn) type ar
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1