圖論C版課件.pptVIP

圖論算法c 一對(duì)一和一對(duì)多的結(jié)構(gòu) 在前邊講解的線性表中 每個(gè)元素之間只有一個(gè)直接前驅(qū)和一個(gè)直接后繼 在樹(shù)形結(jié)構(gòu)中 數(shù)據(jù)元素之間是層次關(guān)系 并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素相關(guān) 但只能和上一層中一個(gè)元素相關(guān) 圖結(jié)構(gòu) 是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系 在這種結(jié)構(gòu)中 任意兩個(gè)元素之間可能存在關(guān)系 即結(jié)點(diǎn)之間的關(guān)系可以是任意的 圖中任意元素之間都可能相關(guān) 圖的應(yīng)用極為廣泛 已滲入到諸如語(yǔ)言學(xué) 邏輯學(xué) 物理 化學(xué) 電訊 計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支 一 圖的定義及其術(shù)語(yǔ)圖 Graph 是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成 通常表示為 G V E 其中 G表示一個(gè)圖 V是圖G中頂點(diǎn)的集合 E是圖G中邊的集合 對(duì)于圖的定義 我們需要明確幾個(gè)注意的地方 線性表中我們把數(shù)據(jù)元素叫元素 樹(shù)中叫結(jié)點(diǎn) 在圖中數(shù)據(jù)元素我們則稱之為頂點(diǎn) Vertex 線性表可以沒(méi)有數(shù)據(jù)元素 稱為空表 樹(shù)中可以沒(méi)有結(jié)點(diǎn) 叫做空樹(shù) 而圖結(jié)構(gòu)在國(guó)內(nèi)大部分的教材中強(qiáng)調(diào)頂點(diǎn)集合V要有窮非空 線性表中 相鄰的數(shù)據(jù)元素之間具有線性關(guān)系 樹(shù)結(jié)構(gòu)中 相鄰兩層的結(jié)點(diǎn)具有層次關(guān)系 而圖結(jié)構(gòu)中 任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系 頂點(diǎn)之間的邏輯關(guān)系用邊來(lái)表示 邊集可以是空的 圖的各種定義 無(wú)向邊 若頂點(diǎn)Vi到Vj之間的邊沒(méi)有方向 則稱這條邊為無(wú)向邊 Edge 用無(wú)序偶數(shù)對(duì) Vi Vj 來(lái)表示 無(wú)向圖 圖中所有頂點(diǎn)間的邊均是無(wú)向的 上圖G1是一個(gè)無(wú)向圖 G1 V1 E1 其中V1 A B C D E1 A B B C C D D A A C 無(wú)序?qū)?A B 表示A和B之間的一條邊 Edge 因此 A B 和 B A 代表的是同一條邊 上圖G2是一個(gè)無(wú)向圖 G2 V2 E2 其中V2 A B C D E2 有向邊 若從頂點(diǎn)Vi到Vj的邊有方向 則稱這條邊為有向邊 也稱為弧 Arc 用有序偶數(shù)對(duì)來(lái)表示 Vi稱為弧尾 Vj稱為弧頭 有向圖 圖中所有頂點(diǎn)間的邊均是有向的 簡(jiǎn)單圖 在圖結(jié)構(gòu)中 若不存在頂點(diǎn)到其自身的邊 且同一條邊不重復(fù)出現(xiàn) 則稱這樣的圖為簡(jiǎn)單圖 以下兩個(gè)則不屬于簡(jiǎn)單圖 稀疏圖 稠密圖 權(quán)有很少邊或弧的圖 e n n 的圖稱為稀疏圖 反之稱為稠密圖 權(quán) Weight 與圖的邊和弧相關(guān)的數(shù) 權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi) 帶權(quán)的圖通常稱為網(wǎng) Network 無(wú)向完全圖 在無(wú)向圖中 如果任意兩個(gè)頂點(diǎn)之間都存在邊 則稱該圖為無(wú)向完全圖 含有n個(gè)頂點(diǎn)的無(wú)向完全圖有n n 1 2條邊 有向完全圖 在有向圖中 如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧 則稱該圖為有向完全圖 含有n個(gè)頂點(diǎn)的有向完全圖有n n 1 條邊 假設(shè)有兩個(gè)圖G1 V1 E1 和G2 V2 E2 如果V2 V1 E2 E1 則稱G2為G1的子圖 Subgraph 圖的頂點(diǎn)與邊之間的關(guān)系 對(duì)于無(wú)向圖G V E 如果邊 V1 V2 E 則稱頂點(diǎn)V1和V2互為鄰接點(diǎn) Adjacent 即V1和V2相鄰接 邊 V1 V2 依附 incident 于頂點(diǎn)V1和V2 或者說(shuō)邊 V1 V2 與頂點(diǎn)V1和V2相關(guān)聯(lián) 頂點(diǎn)V的度 Degree 是和V相關(guān)聯(lián)的邊的數(shù)目 記為T(mén)D V 如下圖 頂點(diǎn)A與B互為鄰接點(diǎn) 邊 A B 依附于頂點(diǎn)A與B上 頂點(diǎn)A的度為3 對(duì)于有向圖G V E 如果有 E 則稱頂點(diǎn)V1鄰接到頂點(diǎn)V2 頂點(diǎn)V2鄰接自頂點(diǎn)V1 以頂點(diǎn)V為頭的弧的數(shù)目稱為V的入度 InDegree 記為ID V 以V為尾的弧的數(shù)目稱為V的出度 OutDegree 記為OD V 因此頂點(diǎn)V的度為T(mén)D V ID V OD V 下圖頂點(diǎn)A的入度是2 出度是1 所以頂點(diǎn)A的度是3 路徑 Path 路徑長(zhǎng)度 回路 Cycle 對(duì)無(wú)向圖G V E 若從頂點(diǎn)vi經(jīng)過(guò)若干條邊能到達(dá)vj 稱頂點(diǎn)vi和vj是連通的 又稱頂點(diǎn)vi到vj有路徑 對(duì)有向圖G V E 從頂點(diǎn)vi到vj有有向路徑 指的是從頂點(diǎn)vi經(jīng)過(guò)若干條有向邊 弧 能到達(dá)vj 在一條路徑中 若沒(méi)有重復(fù)相同的頂點(diǎn) 該路徑稱為簡(jiǎn)單路徑 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路 環(huán) 在一個(gè)回路中 若除第一個(gè)與最后一個(gè)頂點(diǎn)外 其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路 簡(jiǎn)單環(huán) 如果G是有向圖 則路徑也是有向的 下圖用紅線列舉頂點(diǎn)B到頂點(diǎn)D的兩種路徑 而頂點(diǎn)A到頂點(diǎn)B就不存在路徑 路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目 第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán) Cycle 右圖用紅線列舉了從頂點(diǎn)B到頂點(diǎn)D的四種不同路徑 連通圖在無(wú)向圖G中 如果從頂點(diǎn)V1到頂點(diǎn)V2有路徑 則稱V1和V2是連通的 如果對(duì)于圖中任意兩個(gè)頂點(diǎn)Vi和Vj都是連通的 則稱G是連通圖 ConnectedGraph 下圖左側(cè)不是連通圖 右側(cè)是連通圖 無(wú)向圖中的極大連通子圖稱為連通分量 注意以下概念 首先要是子圖 并且子圖是要連通的 連通子圖含有極大頂點(diǎn)數(shù) 極大 的含義 指的是對(duì)子圖再增加圖G中的其它頂點(diǎn) 子圖就不再連通 具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊 在有向圖G中 如果對(duì)于每一對(duì)Vi到Vj都存在路徑 則稱G是強(qiáng)連通圖 有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量 下圖左側(cè)并不是強(qiáng)連通圖 右側(cè)是 并且右側(cè)是左側(cè)的極大強(qiáng)連通子圖 也是左側(cè)的強(qiáng)連通分量 二 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜 其復(fù)雜性主要表現(xiàn)在 任意頂點(diǎn)之間可能存在聯(lián)系 無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系 圖中頂點(diǎn)的度不一樣 有的可能相差很大 若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu) 則會(huì)浪費(fèi)很多存儲(chǔ)單元 反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu) 又會(huì)影響操作 圖的常用的存儲(chǔ)結(jié)構(gòu)有 鄰接矩陣 鄰接鏈表 十字鏈表 鄰接多重表和邊表 1 二維數(shù)組鄰接矩陣存儲(chǔ)基本思想 對(duì)于有n個(gè)頂點(diǎn)的圖 用一維數(shù)組vexs n 存儲(chǔ)頂點(diǎn)信息 用二維數(shù)組A n n 存儲(chǔ)頂點(diǎn)之間關(guān)系的信息 該二維數(shù)組稱為鄰接矩陣 在鄰接矩陣中 以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn) 鄰接矩陣中的元素A i j 存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息 定義intG 101 101 G i j 的值 表示從點(diǎn)i到點(diǎn)j的邊的權(quán)值 定義如下 上圖中的3個(gè)圖對(duì)應(yīng)的鄰接矩陣分別如下 0111011 58 3G A 1011G B 0015 2 61100010G C 82 1041100 10 1136411 另外有向圖是有講究的 要考慮入度和出度 頂點(diǎn)V1的入度為1 正好是第V1列的各數(shù)之和 頂點(diǎn)V1的出度為2 正好是第V1行的各數(shù)之和 下面是建立圖的鄰接矩陣的參考程序段 includeusingnamespacestd inti j k e n doubleg 101 101 doublew intmain inti j for i 1 i e for k 1 k i j w 讀入兩個(gè)頂點(diǎn)序號(hào)及權(quán)值g i j w 對(duì)于不帶權(quán)的圖g i j 1g j i w 無(wú)向圖的對(duì)稱性 如果是有向圖則不要有這句 return0 建立鄰接矩陣時(shí) 有兩個(gè)小技巧 初始化數(shù)組大可不必使用兩重for循環(huán) 1 如果是int數(shù)組 采用memset g 0 x7f sizeof g 可全部初始化為一個(gè)很大的數(shù) 略小于0 x7fffffff 使用memset g 0 sizeof g 全部清為0 使用memset g 0 xaf sizeof g 全部初始化為一個(gè)很小的數(shù) 2 如果是double數(shù)組 采用memset g 127 sizeof g 可全部初始化為一個(gè)很大的數(shù)1 38 10306 使用memset g 0 sizeof g 全部清為0 2 數(shù)組模擬鄰接表存儲(chǔ)鄰接矩陣看上去是個(gè)不錯(cuò)的選擇 首先是容易理解 第二是索引和編排都很舒服但是我們也發(fā)現(xiàn) 鄰接矩陣適合于結(jié)點(diǎn)數(shù)較少的稠密圖 如果用來(lái)表示稀疏圖 則會(huì)造成很大的空間浪費(fèi) 因此我們可以考慮另外一種存儲(chǔ)結(jié)構(gòu)方式 例如把數(shù)組與鏈表結(jié)合一起來(lái)存儲(chǔ) 這種方式在圖結(jié)構(gòu)也適用 我們稱為鄰接表 AdjacencyList 基本思想 對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表 存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息 每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn) 第i個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊 對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧 圖的鄰接表存儲(chǔ)法 又叫鏈?zhǔn)酱鎯?chǔ)法 本來(lái)是要用鏈表實(shí)現(xiàn)的 但大多數(shù)情況下只要用數(shù)組模擬即可 鄰接表 有向圖 鄰接表的處理方法是這樣 圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ) 當(dāng)然 頂點(diǎn)也可以用單鏈表來(lái)存儲(chǔ) 不過(guò)數(shù)組可以較容易地讀取頂點(diǎn)信息 更加方便 圖中每個(gè)頂點(diǎn)Vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表 由于鄰接點(diǎn)的個(gè)數(shù)不確定 所以我們選擇用單鏈表來(lái)存儲(chǔ) 若是有向圖 鄰接表結(jié)構(gòu)就是這樣定義的 有向圖的鄰接表 我們先來(lái)看下把頂點(diǎn)當(dāng)弧尾建立的鄰接表 這樣很容易就可以得到每個(gè)頂點(diǎn)的出度 但也有時(shí)為了便于確定頂點(diǎn)的入度或以頂點(diǎn)為弧頭的弧 我們可以建立一個(gè)有向圖的逆鄰接表 此時(shí)我們很容易就可以算出某個(gè)頂點(diǎn)的入度或出度是多少 判斷兩頂點(diǎn)是否存在弧也很容易實(shí)現(xiàn) 對(duì)于帶權(quán)值的網(wǎng)圖 可以在邊表結(jié)點(diǎn)定義中再增加一個(gè)數(shù)據(jù)域來(lái)存儲(chǔ)權(quán)值即可 鄰接表 網(wǎng) 在進(jìn)行鄰接表的輸入時(shí) 可以直接使用鄰接表的定義方式直接輸入 也可由別的輸入方式進(jìn)行演變 課本上的就是利用邊的頂點(diǎn)及其權(quán)值進(jìn)行輸入的 以下是用數(shù)組模擬鄰接表存儲(chǔ)的參考程序段 constintN maxn maxn表示圖中最大頂點(diǎn)數(shù)constintE maxe maxe圖中最大邊數(shù)structEdge intu v 邊所鄰接的兩個(gè)頂點(diǎn)intw 邊的權(quán)值intnext 邊指針 指向下一條邊的內(nèi)存地址 edge E 靜態(tài)內(nèi)存 用于分配邊inthead N 表頭intnum 內(nèi)存的指針voidinit for inti 0 i E i head i 1 這里為什么要設(shè)為 1num 0 voidaddedge intb inte intw edge num u b edge num v e edge num w w edge num next head b head b num intmain num edge 0 scanf d d 兩種方法各有用武之地 需按具體情況 具體選用 例題 求一個(gè)有向圖中指定頂點(diǎn)的出度 問(wèn)題描述 如題 文件輸入 第1行 2個(gè)空格分開(kāi)的整數(shù)n 2 n 200 和m 10 m 20000 分別表示圖的頂點(diǎn)數(shù)和邊數(shù) 第2 m 1行 每行2個(gè)空格分開(kāi)的整數(shù)i j i表示一條邊的起點(diǎn) j表示終點(diǎn) 第m 2行 1個(gè)整數(shù)k 2 k n 表示指定的頂點(diǎn) 文件輸出 只有一行為1個(gè)整數(shù) 表示頂點(diǎn)k的出度 樣例輸入 5835454323544142244 樣例輸出 4 2019 12 20 28 可編輯 參考代碼 方法1 鄰接矩陣存儲(chǔ)圖 includeusingnamespacestd inta 201 201 n m ans 0 x voidinit inti j k cin n m for i 1 i j k a j k 1 intmain init cin k for inti 1 i n i if a k i ans cout ans endl 方法2 鄰接表存儲(chǔ)圖 includeusingnamespacestd structEdge intto next w 20005 inth Maxn 0 i x y z n e k cnt ans 0 voidAddEdge intx inty cnt w cnt to y w cnt next h x h x cnt intmain cin n e 讀入頂點(diǎn)數(shù)目和邊數(shù)for i 1 i x y AddEdge x y 建圖cin k for intp h k p 0 p w p next ans cout ans endl 第二節(jié)圖的遍歷 一 深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點(diǎn)出發(fā)系統(tǒng)地訪問(wèn)圖中所有頂點(diǎn) 使每個(gè)頂點(diǎn)恰好被訪問(wèn)一次 這種運(yùn)算操作被稱為圖的遍歷 為了避免重復(fù)訪問(wèn)某個(gè)頂點(diǎn) 可以設(shè)一個(gè)標(biāo)志數(shù)組visited i 未訪問(wèn)時(shí)值為false 訪問(wèn)一次后就改為true 圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法 兩者的時(shí)間效率都是O n n 1 深度優(yōu)先遍歷深度優(yōu)先搜索 DepthFirstSearch DFS 遍歷類似樹(shù)的先序遍歷 是樹(shù)的先序遍歷的推廣 1算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn) 則 從圖中某個(gè)頂點(diǎn)vi出發(fā) 訪問(wèn)vi 然后找到vi的一個(gè)鄰接頂點(diǎn)vi1 從vi1出發(fā) 深度優(yōu)先搜索訪問(wèn)和vi1相鄰接且未被訪問(wèn)的所有頂點(diǎn) 轉(zhuǎn) 直到和vi相鄰接的所有頂點(diǎn)都被訪問(wèn)為止 繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vj作為起始頂點(diǎn) 轉(zhuǎn) 1 直到圖中所有頂點(diǎn)都被訪問(wèn)為止 例如對(duì)右邊的這個(gè)無(wú)向圖深度優(yōu)先遍歷 假定先從1出發(fā)程序以如下順序遍歷 1 2 5 然后退回到2 退回到1 從1開(kāi)始再訪問(wèn)未被訪問(wèn)過(guò)的點(diǎn)3 3沒(méi)有未訪問(wèn)的鄰接點(diǎn) 退回1 再?gòu)?開(kāi)始訪問(wèn)未被訪問(wèn)過(guò)的點(diǎn)4 再退回1 起點(diǎn)1的所有鄰接點(diǎn)都已訪問(wèn) 遍歷結(jié)束 下面給出的深度優(yōu)先遍歷的參考程序 假設(shè)圖以鄰接表存儲(chǔ)voiddfs inti 圖用數(shù)組模擬鄰接表存儲(chǔ) 訪問(wèn)點(diǎn)i visited i true 標(biāo)記為已經(jīng)訪問(wèn)過(guò)for intj 1 j num i j 遍歷與i相關(guān)聯(lián)的所有未訪問(wèn)過(guò)的頂點(diǎn)if visited g i j dfs g i j 主程序如下 intmain memset visited false sizeof visited for inti 1 i n i 每一個(gè)點(diǎn)都作為起點(diǎn)嘗試訪問(wèn) 因?yàn)椴皇菑娜魏?一點(diǎn)開(kāi)始都能遍歷整個(gè)圖的 例如下面的兩個(gè)圖 if visited i dfs i return0 廣度優(yōu)先搜索BFS 廣度優(yōu)先搜索 BreadthFirstSearch BFS 遍歷類似樹(shù)的按層次遍歷的過(guò)程 1算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn) 則 從圖中某個(gè)頂點(diǎn)vi出發(fā) 訪問(wèn)vi 訪問(wèn)vi的所有相鄰接且未被訪問(wèn)的所有頂點(diǎn)vi1 vi2 vim 以vi1 vi2 vim的次序 以vij 1 j m 依此作為vi 轉(zhuǎn) 繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vk作為起始頂點(diǎn) 轉(zhuǎn) 直到圖中所有頂點(diǎn)都被訪問(wèn)為止 下圖是有向圖的廣度優(yōu)先搜索遍歷示例 淺色箭頭 上述圖的BFS次序是 v1 v2 v4 v3 v5 用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點(diǎn)搜索次序不同 因此 廣度優(yōu)先搜索算法遍歷圖的總時(shí)間復(fù)雜度為O n e 圖的遍歷可以系統(tǒng)地訪問(wèn)圖中的每個(gè)頂點(diǎn) 因此 圖的遍歷算法是圖的最基本 最重要的算法 許多有關(guān)圖的操作都是在圖的遍歷基礎(chǔ)之上加以變化來(lái)實(shí)現(xiàn)的 例題 無(wú)向圖的BFS 問(wèn)題描述 一個(gè)無(wú)向圖 從指定頂點(diǎn)出發(fā)進(jìn)行BFS 求遍歷得到的頂點(diǎn)序 文件輸入 第1行 2個(gè)空格分開(kāi)的整數(shù)n 2 n 200 和m 10 m 20000 分別表示圖的頂點(diǎn)數(shù)和邊數(shù) 第2 m 1行 每行2個(gè)空格分開(kāi)的整數(shù)i j i表示一條邊的起點(diǎn) j表示終點(diǎn) 第m 2行 1個(gè)整數(shù)k 1 k n 表示指定的頂點(diǎn) 文件輸出 只一行頂點(diǎn)序 要求在同一層上 頂點(diǎn)序號(hào)從小到大輸出 includeusingnamespacestd inta 101 101 f 101 q 101 n m i st voidinit inti j x y cin n m memset f 0 sizeof f for i 1 i x y a x y 1 a y x 1 cin st voiddfs inti 深搜DFS intj cout i f i 1 for j 1 j n j if f j 0 二 歐拉圖 1 歐拉路 歐拉路徑 圖G中每條邊經(jīng)過(guò)一次且僅一次的路徑稱作歐拉路徑 如下圖中存在一條從頂點(diǎn)1到頂點(diǎn)6的歐拉路 一筆畫(huà)問(wèn)題其實(shí)本質(zhì)上就是判斷一個(gè)圖是否存在歐拉路 無(wú)向圖歐拉路存在的充要條件 圖是連通的 圖中有且僅有0個(gè)或2個(gè)度數(shù)為奇數(shù)的點(diǎn) 若存在2個(gè)奇點(diǎn) 則歐拉路一定是從一個(gè)奇點(diǎn)出發(fā) 以另一個(gè)奇點(diǎn)結(jié)束 2 歐拉回路 圖G中每條邊經(jīng)過(guò)一次且僅一次的回路稱作歐拉回路 著名的柯尼斯堡七橋問(wèn)題 圖論起源 本質(zhì)上就是討論一個(gè)圖的歐拉回路問(wèn)題 一個(gè)無(wú)向圖有歐拉回路的必要條件是 圖是連通的 圖中所有點(diǎn)的度均為偶數(shù) 求歐拉路的算法很簡(jiǎn)單 使用深度優(yōu)先遍歷即可 根據(jù)一筆畫(huà)的兩個(gè)定理 如果尋找歐拉回路 對(duì)任意一個(gè)點(diǎn)執(zhí)行深度優(yōu)先遍歷 找歐拉路 則對(duì)一個(gè)奇點(diǎn)執(zhí)行DFS 時(shí)間復(fù)雜度為O m n m為邊數(shù) n是點(diǎn)數(shù) 以下是尋找一個(gè)圖的歐拉路的算法實(shí)現(xiàn) 樣例輸入 第一行n m 有n個(gè)點(diǎn) m條邊 以下m行描述每條邊連接的兩點(diǎn) 551223344551樣例輸出 歐拉路或歐拉回路154321 參考程序 Euler cpp include includeusingnamespacestd definemaxn101intg maxn maxn 此圖用鄰接矩陣存儲(chǔ)intdu maxn 記錄每個(gè)點(diǎn)的度 就是相連的邊的數(shù)目intcircuit maxn 用來(lái)記錄找到的歐拉路的路徑intn e circuitpos i j x y start voidfind circuit inti 這個(gè)點(diǎn)深度優(yōu)先遍歷過(guò)程尋找歐拉路 intj for j 1 j n j if g i j 1 從任意一個(gè)與它相連的點(diǎn)出發(fā) g j i g i j 0 find circuit j circuit circuitpos i 記錄下路徑 intmain memset g 0 sizeof g cin n e for i 1 i x y g y x g x y 1 du x 統(tǒng)計(jì)每個(gè)點(diǎn)的度du y start 1 如果有奇點(diǎn) 就從奇點(diǎn)開(kāi)始尋找 這樣找到的就是for i 1 i n i 歐拉路 沒(méi)有奇點(diǎn)就從任意點(diǎn)開(kāi)始 if du i 2 1 這樣找到的就是歐拉回路 因?yàn)槊恳粋€(gè)點(diǎn)都是偶點(diǎn) start i circuitpos 0 find circuit start for i 1 i circuitpos i cout circuit i cout endl return0 注意以上程序具有一定的局限性 對(duì)于下面這種情況它不能很好地處理 上圖具有多個(gè)歐拉回路 而本程序只能找到一個(gè)回路 讀者在遇到具體問(wèn)題時(shí) 還應(yīng)對(duì)程序作出相應(yīng)的修改 三 哈密爾頓環(huán)歐拉回路是指不重復(fù)地走過(guò)所有路徑的回路 而哈密爾頓環(huán)是指不重復(fù)地走過(guò)所有的點(diǎn) 并且最后還能回到起點(diǎn)的回路 哈密頓通路 回路 與哈密頓圖 Hamilton圖 通過(guò)圖G的每個(gè)結(jié)點(diǎn)一次 且僅一次的通路 回路 就是哈密頓通路 回路 存在哈密頓回路的圖就是哈密頓圖 美國(guó)圖論數(shù)學(xué)家?jiàn)W勒在1960年給出了一個(gè)圖是哈密爾頓圖的充分條件 對(duì)于頂點(diǎn)個(gè)數(shù)大于2的圖 如果圖中任意兩點(diǎn)度的和大于或等于頂點(diǎn)總數(shù) 那這個(gè)圖一定是哈密頓圖 閉合的哈密頓路徑稱作哈密頓圈 含有圖中所有頂點(diǎn)的路徑稱作哈密頓路徑 例題1 哈密頓路問(wèn)題 問(wèn)題描述 郵遞員在送信時(shí) 為了節(jié)省路途 自己規(guī)定 每次總是從n個(gè)村子中選擇其中一個(gè)合適的村子出發(fā) 途經(jīng)每個(gè)村子僅且經(jīng)過(guò)一次 送完所有的信 已知各個(gè)村子的道路連通情況 請(qǐng)你幫郵遞員選擇一條合適的路線 文件輸入 第1行 整數(shù)n 2 n 200 村子的個(gè)數(shù) 接下來(lái)是一個(gè)n n的0 1矩陣 每2個(gè)數(shù)之間有1個(gè)空格 表示n個(gè)村子的連通情況 如 a i j 1 表示第i和第j個(gè)村子之間有路可走 如果a i j 0 表示他們之間無(wú)路可走 文件輸出 只有一行為1個(gè)整數(shù)表示可行的方案總數(shù) include includeusingnamespacestd inta 201 201 visit 201 found n sum voidinit inti j scanf d intmain inti init found 0 sum 0 for i 1 i n i memset visit 0 sizeof visit visit i 1 dfs i 1 if found 0 printf d 0 elseprintf d sum return0 使用簡(jiǎn)單的深度優(yōu)先搜索 就能求出一張圖中所有的哈密爾頓環(huán) 下面給出一段參考程序 include includeusingnamespacestd intstart length x n boolvisited 101 v1 101 intans 101 num 101 intg 101 101 voidprint inti for i 1 i length i cout ans i cout endl voiddfs intlast inti 圖用數(shù)組模擬鄰接表存儲(chǔ) 訪問(wèn)點(diǎn)i last表示上次訪問(wèn)的點(diǎn) visited i true 標(biāo)記為已經(jīng)訪問(wèn)過(guò)v1 i true 標(biāo)記為已在一張圖中出現(xiàn)過(guò)ans length i 記錄下答案for intj 1 j num i j if g i j x 這里是回溯過(guò)程 注意v1的值不恢復(fù) intmain memset visited false sizeof visited memset v1 false sizeof v1 for x 1 x n x 每一個(gè)點(diǎn)都作為起點(diǎn)嘗試訪問(wèn) 因?yàn)椴皇菑娜魏我稽c(diǎn)開(kāi)始都能找過(guò)整個(gè)圖的if v1 x 如果點(diǎn)x不在之前曾經(jīng)被訪問(wèn)過(guò)的圖里 length 0 定義一個(gè)ans數(shù)組存答案 length記答案的長(zhǎng)度 dfs 0 x return0 上機(jī)練習(xí) 1 珍珠BEAD 問(wèn)題描述 有n顆形狀和大小都一致的珍珠 它們的重量都不相同 n為整數(shù) 所有的珍珠從1到n編號(hào) 你的任務(wù)是發(fā)現(xiàn)哪顆珍珠的重量剛好處于正中間 即在所有珍珠的重量中 該珍珠的重量列 n 1 2位 下面給出將一對(duì)珍珠進(jìn)行比較的辦法 給你一架天平用來(lái)比較珍珠的重量 我們可以比出兩個(gè)珍珠哪個(gè)更重一些 在作出一系列的比較后 我們可以將某些肯定不具備中間重量的珍珠拿走 例如 下列給出對(duì)5顆珍珠進(jìn)行四次比較的情況 1 珍珠2比珍珠1重2 珍珠4比珍珠3重3 珍珠5比珍珠1重4 珍珠4比珍珠2重根據(jù)以上結(jié)果 雖然我們不能精確地找出哪個(gè)珍珠具有中間重量 但我們可以肯定珍珠1和珍珠4不可能具有中間重量 因?yàn)檎渲? 4 5比珍珠1重 而珍珠1 2 3比珍珠4輕 所以我們可以移走這兩顆珍珠 寫(xiě)一個(gè)程序統(tǒng)計(jì)出共有多少顆珍珠肯定不會(huì)是中間重量 輸入格式 輸入文件第一行包含兩個(gè)用空格隔開(kāi)的整數(shù)N和M 其中1 N 99 且N為奇數(shù) M表示對(duì)珍珠進(jìn)行的比較次數(shù) 接下來(lái)的M行每行包含兩個(gè)用空格隔開(kāi)的整數(shù)x和y 表示珍珠x比珍珠y重 輸出格式 輸出文件僅一行包含一個(gè)整數(shù) 表示不可能是中間重量的珍珠的總數(shù) 輸入樣例 BEAD IN542143514