簡(jiǎn)介本資源是哈爾濱工業(yè)大學(xué)《集合論與圖論下》慕課MOOC課程的配套習(xí)題答案整理面向計(jì)算機(jī)、數(shù)學(xué)及相關(guān)專業(yè)本科生及自學(xué)者助力系統(tǒng)掌握?qǐng)D論核心理論與解題方法。內(nèi)容覆蓋圖的基本類型簡(jiǎn)單圖、有向/無(wú)向/加權(quán)圖、樹(shù)與連通性、鄰接矩陣與鄰接表表示法、補(bǔ)圖與偶圖、歐拉圖與哈密頓圖判定、圖著色、平面圖、割點(diǎn)橋分析及最短路徑算法等關(guān)鍵模塊緊扣課程講授邏輯適合作為課后鞏固、考前復(fù)習(xí)與自學(xué)核驗(yàn)的重要參考。資源為單個(gè)PDF文件大小3.16MB排版清晰、章節(jié)對(duì)應(yīng)明確含第1–4講完整答案便于離線查閱與重點(diǎn)標(biāo)注。目前已有359人學(xué)習(xí)下載答案基于高頻重復(fù)題型歸納整理并附有選項(xiàng)辨析提示雖非官方發(fā)布但結(jié)構(gòu)完整、思路清晰可有效提升解題準(zhǔn)確率與概念理解深度。1. 圖論到底是什么——?jiǎng)e被“點(diǎn)和線”騙了它其實(shí)是你手機(jī)里導(dǎo)航、社交推薦、甚至快遞路徑背后的隱形大腦你用地圖App查路線時(shí)系統(tǒng)怎么知道哪條路最快你刷短視頻平臺(tái)為什么總能推給你想看的內(nèi)容你點(diǎn)外賣(mài)騎手怎么在幾十個(gè)訂單里規(guī)劃出最省時(shí)間的送單順序這些看似毫不相干的事背后都藏著同一個(gè)數(shù)學(xué)工具圖論。它不講函數(shù)也不解方程只研究“誰(shuí)連著誰(shuí)”——把城市變成點(diǎn)頂點(diǎn)把道路變成線邊把用戶變成點(diǎn)把“關(guān)注”“點(diǎn)贊”變成線把商品變成點(diǎn)把“經(jīng)常一起買(mǎi)”變成線。就這么簡(jiǎn)單兩樣?xùn)|西搭出來(lái)的結(jié)構(gòu)卻能描述真實(shí)世界里最復(fù)雜的關(guān)聯(lián)。《哈工大集合論與圖論下慕課MOOC答案》這份資源不是一本習(xí)題集而是一份“帶注釋的通關(guān)地圖”它對(duì)應(yīng)的是國(guó)內(nèi)高校公認(rèn)扎實(shí)的圖論入門(mén)課下半程從“圖長(zhǎng)什么樣”一路走到“怎么用圖解決真問(wèn)題”。如果你剛學(xué)完集合論基礎(chǔ)、正卡在“歐拉圖和哈密頓圖分不清”“鄰接矩陣和鄰接表到底該用哪個(gè)”“補(bǔ)圖到底是把邊全刪了還是全加上了”這些具體困惑里——這份資料就是為你寫(xiě)的。它不替代聽(tīng)課但能幫你把老師講的抽象定義立刻對(duì)上一個(gè)可驗(yàn)證、可對(duì)比、有上下文的答案參考。零基礎(chǔ)沒(méi)關(guān)系。只要你能看懂“A連B”“C沒(méi)連D”就能跟著這份材料從第一講的“什么是簡(jiǎn)單圖”開(kāi)始一講一講地把圖論的骨架摸清楚。2. 先搞懂一個(gè)前提這份“答案”不是抄作業(yè)本而是幫你建立判斷力的腳手架很多人第一次看到“慕課答案”四個(gè)字本能反應(yīng)是“哦抄的吧”——這恰恰是新手最容易掉進(jìn)的第一個(gè)認(rèn)知坑。我們得先說(shuō)透這份《哈工大集合論與圖論下慕課MOOC答案》的價(jià)值根本不在“讓你交差”而在于幫你建立一種關(guān)鍵能力在高度相似的選項(xiàng)中識(shí)別出那個(gè)唯一符合定義的正確答案。慕課題庫(kù)有個(gè)特點(diǎn)題目重復(fù)率高但選項(xiàng)會(huì)微調(diào)。比如一道考“歐拉圖判定”的題A選項(xiàng)說(shuō)“所有頂點(diǎn)度數(shù)為偶數(shù)”B選項(xiàng)說(shuō)“至少有兩個(gè)頂點(diǎn)度數(shù)為偶數(shù)”C選項(xiàng)說(shuō)“所有頂點(diǎn)度數(shù)為奇數(shù)”D選項(xiàng)說(shuō)“存在一條經(jīng)過(guò)每條邊一次的路徑”。表面看都沾點(diǎn)邊但只有A完全滿足無(wú)向圖歐拉圖的充要條件。如果你沒(méi)真正理解定義光靠記憶“歐拉圖能一筆畫(huà)”就很容易選錯(cuò)C或D。這份答案的珍貴之處正在于它把每道題的判定依據(jù)直接錨定在教材定義上。它不是告訴你“選A”而是用簡(jiǎn)短注釋點(diǎn)明“此處考察無(wú)向圖歐拉圖判定定理當(dāng)且僅當(dāng)所有頂點(diǎn)度數(shù)均為偶數(shù)”。你看一遍再做一遍同類題下次再遇到選項(xiàng)微調(diào)就能自己推理出來(lái)。這種能力在后續(xù)學(xué)算法比如判斷一個(gè)網(wǎng)絡(luò)能不能遍歷所有鏈路而不重復(fù)、學(xué)數(shù)據(jù)庫(kù)比如分析用戶關(guān)系圖有沒(méi)有環(huán)、甚至學(xué)機(jī)器學(xué)習(xí)比如理解圖神經(jīng)網(wǎng)絡(luò)GNN的輸入結(jié)構(gòu)時(shí)都是底層思維習(xí)慣。所以使用它的第一步不是打開(kāi)文檔找答案而是打開(kāi)課程視頻暫停在題目出現(xiàn)的那一刻先自己讀題、劃關(guān)鍵詞、回憶定義再對(duì)照這份資料里的解析邏輯。你會(huì)發(fā)現(xiàn)很多“不會(huì)”其實(shí)只是定義沒(méi)吃透而很多“會(huì)了”是因?yàn)槟憬K于看清了題目在考哪個(gè)精確的數(shù)學(xué)條件。2.1 為什么必須從“圖的基本概念”講起——因?yàn)?0%的翻車(chē)都發(fā)生在起點(diǎn)沒(méi)站穩(wěn)圖論看起來(lái)簡(jiǎn)單但新手常犯一個(gè)隱蔽錯(cuò)誤把生活語(yǔ)言直接套進(jìn)數(shù)學(xué)定義。比如看到“連通圖”第一反應(yīng)是“我能從北京開(kāi)車(chē)到上?！边@沒(méi)錯(cuò)但數(shù)學(xué)上“連通”特指圖中任意兩個(gè)頂點(diǎn)之間都存在一條由邊組成的路徑。注意是“任意兩個(gè)”不是“大部分”是“存在路徑”不是“有直達(dá)航班”。再比如“簡(jiǎn)單圖”生活中說(shuō)“這個(gè)圖很簡(jiǎn)單”數(shù)學(xué)上它有明確定義沒(méi)有環(huán)頂點(diǎn)到自身的邊且沒(méi)有重邊同一對(duì)頂點(diǎn)間多于一條邊的無(wú)向圖。如果題目給了一張帶自環(huán)的圖問(wèn)“這是簡(jiǎn)單圖嗎”答案就是“否”哪怕它只有3個(gè)點(diǎn)、2條邊。這份資料的第一講“圖的基本概念”就是在幫你校準(zhǔn)這種語(yǔ)言差異。它覆蓋的類型非常典型無(wú)向圖 vs 有向圖無(wú)向圖的邊像一根繩子兩端沒(méi)區(qū)別有向圖的邊像單行道箭頭方向決定誰(shuí)能到誰(shuí)?？荚嚦？加邢驁D的“入度”指向它的邊數(shù)和“出度”它指向的邊數(shù)必須分開(kāi)算。加權(quán)圖每條邊標(biāo)著數(shù)字比如距離、費(fèi)用、延遲。這不是裝飾是后續(xù)學(xué)最短路徑Dijkstra、最小生成樹(shù)Kruskal的前提。子圖、生成子圖、導(dǎo)出子圖這三個(gè)詞長(zhǎng)得像但邏輯不同。子圖是隨便刪點(diǎn)刪邊生成子圖必須保留所有頂點(diǎn)只刪邊導(dǎo)出子圖則是選定一部分頂點(diǎn)把它們之間原來(lái)所有的邊都保留下來(lái)。考試題常讓判斷某個(gè)圖是不是另一個(gè)圖的導(dǎo)出子圖關(guān)鍵就看“選中的點(diǎn)之間原圖有的邊這里是不是全都有”。提示不要試圖背下所有定義。拿起一張白紙畫(huà)4個(gè)點(diǎn)標(biāo)為v1,v2,v3,v4然后按定義自己動(dòng)手構(gòu)造畫(huà)一個(gè)簡(jiǎn)單圖檢查有沒(méi)有環(huán)、重邊畫(huà)一個(gè)有向圖標(biāo)幾個(gè)箭頭算算v2的入度和出度再畫(huà)一個(gè)加權(quán)圖給幾條邊標(biāo)上1,5,10。動(dòng)手畫(huà)三遍比看十遍定義記得牢。2.2 “連通圖、補(bǔ)圖、偶圖”這組概念為什么總讓人暈——用三個(gè)生活場(chǎng)景秒懂第二講的這三個(gè)概念名字抽象但本質(zhì)極清晰。我們不用術(shù)語(yǔ)轟炸直接用你能馬上驗(yàn)證的例子連通圖想象一個(gè)微信群。群里所有人頂點(diǎn)只要能通過(guò)“好友關(guān)系鏈”傳話就算連通。比如A認(rèn)識(shí)BB認(rèn)識(shí)C那A和C就算連通哪怕他倆沒(méi)加微信。但如果群里有個(gè)人D誰(shuí)都不認(rèn)識(shí)也沒(méi)人認(rèn)識(shí)他那整個(gè)群就不連通了——D是孤立點(diǎn)。圖論里連通圖要求任意兩點(diǎn)間都有路徑不連通的圖會(huì)被分成若干個(gè)“連通分支”就像微信群里分成了幾個(gè)小圈子圈子內(nèi)能傳話圈子間不能。補(bǔ)圖這是個(gè)容易誤解的點(diǎn)。補(bǔ)圖不是“把圖刪干凈”而是“把原圖沒(méi)連的邊全連上已經(jīng)連的邊全斷開(kāi)”。舉個(gè)例子原圖只有3個(gè)點(diǎn)A,B,C只連了A-B這一條邊。那么它的補(bǔ)圖就是把A-C、B-C這兩條邊連上同時(shí)把A-B這條邊去掉。結(jié)果補(bǔ)圖里A和B不連但A連C、B連C。補(bǔ)圖的頂點(diǎn)集和原圖完全一樣邊集是“全可能邊集”減去原圖的邊集?？荚嚦？荚瓐D連通補(bǔ)圖一定連通嗎答案是否定的。上面3點(diǎn)例子中原圖只有A-B不連通C是孤立點(diǎn)但它的補(bǔ)圖A-C,B-C是連通的反過(guò)來(lái)也能構(gòu)造出原圖連通但補(bǔ)圖不連通的例子。關(guān)鍵在理解“補(bǔ)”是相對(duì)“完全圖”而言的。偶圖二部圖這個(gè)名字更直白——圖里的所有點(diǎn)能分成兩組比如男生組、女生組并且所有的邊都只出現(xiàn)在組與組之間組內(nèi)絕對(duì)沒(méi)有邊。比如“學(xué)生選課”學(xué)生是一組課程是一組邊表示“某學(xué)生選了某課”學(xué)生之間、課程之間沒(méi)有邊。這就是典型的偶圖。判斷一個(gè)圖是不是偶圖有個(gè)血淚經(jīng)驗(yàn)試著給所有頂點(diǎn)染兩種顏色比如紅和藍(lán)要求每條邊的兩個(gè)端點(diǎn)顏色不同。如果能成功染色它就是偶圖如果染著染著發(fā)現(xiàn)矛盾比如一個(gè)點(diǎn)既要是紅又要是藍(lán)那就不是。這個(gè)“二染色法”是考試和實(shí)際編程中最常用的判定手段。2.3 避坑新手在“圖的基本概念”階段最容易踩的5個(gè)坑現(xiàn)象做題時(shí)看到“有向圖的度數(shù)”直接用無(wú)向圖的“度數(shù)鄰接點(diǎn)個(gè)數(shù)”去算。原因混淆了有向圖的“入度”有多少邊指向它和“出度”它指向多少邊而“度數(shù)”在有向圖里通常指兩者之和但題目考的往往是單獨(dú)的入度或出度。解決看到有向圖第一反應(yīng)寫(xiě)兩列一列“入度”一列“出度”。計(jì)算前先確認(rèn)題目問(wèn)的是哪個(gè)。現(xiàn)象判斷“補(bǔ)圖”時(shí)以為要把原圖的邊全部刪除再隨便連幾條新邊。原因沒(méi)抓住“補(bǔ)圖是相對(duì)于完全圖而言的”這個(gè)核心。完全圖是n個(gè)點(diǎn)之間所有可能的邊無(wú)向圖是n(n-1)/2條有向圖是n(n-1)條都連滿的狀態(tài)。解決先算出n個(gè)點(diǎn)的完全圖有多少條邊再減去原圖的邊數(shù)得到補(bǔ)圖的邊數(shù)。這是驗(yàn)算補(bǔ)圖是否畫(huà)對(duì)的最快方法?，F(xiàn)象看到“偶圖”以為只要點(diǎn)能分成兩組就行忽略了“組內(nèi)不能有邊”這個(gè)硬性條件。原因生活化理解過(guò)度把“分組”等同于“偶圖”。比如把朋友圈所有人按年齡分“青年”“中年”但青年之間依然互相關(guān)注有邊這就不是偶圖。解決畫(huà)出分組后立刻檢查每一組內(nèi)部有沒(méi)有任意兩個(gè)點(diǎn)之間連了邊有就立刻排除?，F(xiàn)象做“子圖”相關(guān)題把“生成子圖”和“導(dǎo)出子圖”弄反。原因記混了“生成保點(diǎn)刪邊”和“導(dǎo)出選點(diǎn)保邊”的口訣。解決用縮寫(xiě)強(qiáng)化記憶“生頂點(diǎn)全留生下來(lái)的孩子一個(gè)都不能少”“導(dǎo)導(dǎo)出的點(diǎn)原邊全要導(dǎo)出即提取原汁原味”?，F(xiàn)象看到“簡(jiǎn)單圖”的定義覺(jué)得“沒(méi)有環(huán)和重邊”很容易結(jié)果題目給了一個(gè)帶平行邊的圖比如v1-v2之間有兩條邊還問(wèn)是不是簡(jiǎn)單圖。原因?qū)Α爸剡叀崩斫獠幻舾幸詾橹挥挟?huà)成兩條完全重疊的線才算其實(shí)只要兩個(gè)頂點(diǎn)間邊數(shù)1就是重邊。解決數(shù)邊時(shí)對(duì)每一對(duì)頂點(diǎn)vi,vj單獨(dú)統(tǒng)計(jì)它們之間有多少條邊。大于1立刻判否。3. 從“能畫(huà)出來(lái)”到“能算出來(lái)”歐拉圖與哈密頓圖是圖論里最經(jīng)典的兩道分水嶺第三講和第四講是整門(mén)課的轉(zhuǎn)折點(diǎn)。前兩講在學(xué)“圖長(zhǎng)什么樣”這兩講開(kāi)始學(xué)“圖能干什么”。歐拉圖和哈密頓圖聽(tīng)名字像孿生兄弟其實(shí)內(nèi)核完全不同歐拉圖關(guān)心的是“邊”——能不能不重復(fù)、不遺漏地走完所有邊哈密頓圖關(guān)心的是“點(diǎn)”——能不能不重復(fù)、不遺漏地路過(guò)所有頂點(diǎn)。這個(gè)根本差異決定了它們的判定方法、應(yīng)用場(chǎng)景和難度層級(jí)。歐拉圖有明確、易驗(yàn)證的充要條件無(wú)向圖所有頂點(diǎn)度數(shù)為偶數(shù)有向圖每個(gè)頂點(diǎn)入度出度所以它是“能算出來(lái)”的哈密頓圖至今沒(méi)有多項(xiàng)式時(shí)間的通用判定算法屬于NP難問(wèn)題所以它是“能猜出來(lái)、但很難證出來(lái)”的。這份資料把這兩講放在一起正是為了讓你在對(duì)比中建立清晰認(rèn)知?jiǎng)e被相似的名字迷惑先盯住問(wèn)題對(duì)象邊 or 點(diǎn)再選工具歐拉定理 or 哈密頓必要條件。3.1 歐拉圖一筆畫(huà)問(wèn)題的數(shù)學(xué)化身3步判定法比心算還快歐拉圖的現(xiàn)實(shí)感最強(qiáng)。小時(shí)候玩的“一筆畫(huà)”游戲就是歐拉回路的雛形。它的數(shù)學(xué)價(jià)值在于提供了一種檢驗(yàn)圖結(jié)構(gòu)是否“均衡”的方法。一個(gè)網(wǎng)絡(luò)比如電路板布線、物流配送路線如果能形成歐拉回路意味著你可以設(shè)計(jì)一條路徑讓設(shè)備/車(chē)輛/信號(hào)遍歷所有連接最終回到起點(diǎn)效率極高。判定它只需三步確認(rèn)圖的類型是無(wú)向圖還是有向圖題目一定會(huì)說(shuō)明別跳過(guò)檢查連通性必須是連通圖或強(qiáng)連通圖對(duì)有向圖而言。如果圖本身是散的肯定沒(méi)法一筆畫(huà)完。驗(yàn)證度數(shù)條件無(wú)向圖所有頂點(diǎn)的度數(shù)必須是偶數(shù)。這是充要條件缺一不可。有向圖每個(gè)頂點(diǎn)的入度必須等于出度。同樣是充要條件。來(lái)看一個(gè)典型例題模擬題給定無(wú)向圖G頂點(diǎn)集{v1,v2,v3,v4}邊集{(v1,v2), (v2,v3), (v3,v4), (v4,v1), (v1,v3)}。問(wèn)G是否為歐拉圖解第一步是無(wú)向圖。第二步畫(huà)一下四個(gè)點(diǎn)圍成一個(gè)四邊形再加一條對(duì)角線v1-v3。顯然任意兩點(diǎn)都連通是連通圖。第三步算度數(shù)。v1連v2,v4,v3 → 度數(shù)3v2連v1,v3 → 度數(shù)2v3連v2,v4,v1 → 度數(shù)3v4連v3,v1 → 度數(shù)2。v1和v3度數(shù)是奇數(shù)不滿足“全為偶數(shù)”所以不是歐拉圖。但注意它滿足歐拉路徑的條件恰好兩個(gè)奇度數(shù)頂點(diǎn)所以可以一筆畫(huà)但起點(diǎn)和終點(diǎn)必須是v1和v3。這份資料里對(duì)這類細(xì)微差別都有明確標(biāo)注避免你把“歐拉路徑”和“歐拉回路”混為一談。3.2 哈密頓圖旅行商問(wèn)題的簡(jiǎn)化版為什么它讓計(jì)算機(jī)科學(xué)家頭疼如果說(shuō)歐拉圖是“走完所有路”哈密頓圖就是“拜訪所有城”。它要求找到一條路徑哈密頓路徑或回路哈密頓回路使得圖中每個(gè)頂點(diǎn)恰好經(jīng)過(guò)一次。這聽(tīng)起來(lái)很美但數(shù)學(xué)上極其困難。目前沒(méi)有任何像歐拉定理那樣簡(jiǎn)潔的充要條件。我們能用的主要是必要條件不滿足則一定不是和充分條件滿足則一定是以及一些實(shí)用的排除技巧。必要條件Dirac定理對(duì)于n個(gè)頂點(diǎn)的簡(jiǎn)單圖如果每個(gè)頂點(diǎn)的度數(shù)都≥n/2那么它一定是哈密頓圖。這是一個(gè)“夠用就好”的強(qiáng)條件但不滿足它不代表不是哈密頓圖。常用排除法最有效割點(diǎn)法如果圖中存在一個(gè)頂點(diǎn)v刪除v后圖的連通分支數(shù)≥3那么原圖一定不是哈密頓圖。因?yàn)楣茴D回路是一個(gè)圈刪掉圈上一個(gè)點(diǎn)最多把圈切成一條鏈連通分支數(shù)1絕不可能變成3個(gè)以上碎片。度數(shù)和法對(duì)任意兩個(gè)不相鄰的頂點(diǎn)u和v如果deg(u)deg(v) n那么圖不是哈密頓圖。Ore定理舉個(gè)避坑例子題目給一個(gè)5個(gè)頂點(diǎn)的圖其中v1只連v2v2連v1和v3v3連v2和v4v4連v3和v5v5只連v4。這是一條鏈v1-v2-v3-v4-v5。問(wèn)是否為哈密頓圖答不是。因?yàn)楣茴D回路要求首尾相連形成圈而這條鏈的兩端v1和v5度數(shù)都是1無(wú)法閉合。更嚴(yán)謹(jǐn)?shù)赜酶铧c(diǎn)法刪掉v2剩下v1孤立、v3-v4-v5連通共2個(gè)分支刪掉v3剩下v1-v2、v4-v5也是2個(gè)分支。雖然沒(méi)到3個(gè)但已暴露結(jié)構(gòu)脆弱。而哈密頓圖要求圖是“1-連通”的刪一個(gè)點(diǎn)仍連通這個(gè)鏈刪掉中間點(diǎn)就斷成兩截顯然不滿足。3.3 避坑歐拉圖與哈密頓圖混淆的4個(gè)致命瞬間現(xiàn)象看到題目說(shuō)“能否不重復(fù)地走完所有邊”下意識(shí)去檢查每個(gè)頂點(diǎn)的度數(shù)是不是都≥2。原因把哈密頓圖的必要條件每個(gè)頂點(diǎn)度數(shù)≥2是哈密頓圖的必要條件但非充分錯(cuò)誤遷移到歐拉圖上。歐拉圖只認(rèn)“奇偶性”不認(rèn)“大小”。解決歐拉圖只問(wèn)“偶數(shù)”哈密頓圖才問(wèn)“夠不夠2”。建立條件反射見(jiàn)“邊”→想“奇偶”見(jiàn)“點(diǎn)”→想“度數(shù)大小”?，F(xiàn)象判斷有向圖歐拉性時(shí)只算了出度忘了入度或者把入度出度加起來(lái)當(dāng)度數(shù)用。原因沒(méi)區(qū)分有向圖的度數(shù)定義。有向圖的“度數(shù)”是入度出度但歐拉定理要求的是“入度出度”不是“入度出度偶數(shù)”。解決強(qiáng)制自己畫(huà)表格左邊列頂點(diǎn)中間列出度右邊列入度最后加一列“入度出度”。三列并排一目了然?，F(xiàn)象看到一個(gè)圖有哈密頓路徑就認(rèn)為它也有哈密頓回路。原因路徑和回路是不同概念。路徑有起點(diǎn)終點(diǎn)回路首尾相接。一個(gè)鏈狀圖有哈密頓路徑v1-v2-v3-v4但沒(méi)有哈密頓回路因?yàn)関1和v4不連。解決題目問(wèn)“哈密頓圖”默認(rèn)指存在哈密頓回路。如果只找到路徑必須額外驗(yàn)證起點(diǎn)和終點(diǎn)是否相鄰?，F(xiàn)象用Dirac定理度數(shù)≥n/2去證明一個(gè)圖是哈密頓圖結(jié)果算出來(lái)v1度數(shù)2n522.5于是斷定“不是哈密頓圖”。原因Dirac定理是充分條件不是必要條件。它說(shuō)“滿足就一定是”但沒(méi)說(shuō)“不滿足就一定不是”。這個(gè)圖完全可能通過(guò)其他方式是哈密頓圖。解決Dirac定理只用來(lái)“快速確認(rèn)是”絕不用來(lái)“快速確認(rèn)不是”。排除哈密頓圖優(yōu)先用割點(diǎn)法或Ore定理。4. 把抽象概念落地用鄰接矩陣和鄰接表親手“看見(jiàn)”一個(gè)圖的結(jié)構(gòu)前面講的都是“紙上談兵”現(xiàn)在到了動(dòng)手環(huán)節(jié)。圖論要真正用起來(lái)必須把它變成計(jì)算機(jī)能處理的數(shù)據(jù)。而“鄰接矩陣”和“鄰接表”就是圖論通往編程世界的兩座橋。它們不是選擇題而是必修課鄰接矩陣適合小而稠密的圖比如5個(gè)點(diǎn)邊很多操作直觀鄰接表適合大而稀疏的圖比如1000個(gè)用戶每人只關(guān)注10個(gè)節(jié)省空間。這份資料雖是文字答案但它在解析題目時(shí)會(huì)明確指出“此題用鄰接矩陣更易觀察”或“此題用鄰接表可快速找出所有鄰居”教你根據(jù)問(wèn)題選工具。下面我們就用一個(gè)統(tǒng)一的例子帶你親手構(gòu)建這兩種表示。4.1 鄰接矩陣一張“誰(shuí)和誰(shuí)有關(guān)系”的二維表格我們還是用之前的5點(diǎn)鏈圖頂點(diǎn){v1,v2,v3,v4,v5}邊{(v1,v2), (v2,v3), (v3,v4), (v4,v5)}。鄰接矩陣是一個(gè)5×5的方陣行和列都按頂點(diǎn)順序排列v1,v2,v3,v4,v5。規(guī)則超簡(jiǎn)單如果vi到vj有一條邊無(wú)向圖中vi-vj和vj-vi等價(jià)矩陣[i][j]位置填1否則填0。因?yàn)槭菬o(wú)向圖矩陣一定是對(duì)稱的主對(duì)角線以外。構(gòu)建過(guò)程第一行v1v1只連v2所以[0][1]1索引從0開(kāi)始其余為0 →[0,1,0,0,0]第二行v2v2連v1和v3 →[1,0,1,0,0]第三行v3v3連v2和v4 →[0,1,0,1,0]第四行v4v4連v3和v5 →[0,0,1,0,1]第五行v5v5只連v4 →[0,0,0,1,0]最終鄰接矩陣[[0,1,0,0,0], [1,0,1,0,0], [0,1,0,1,0], [0,0,1,0,1], [0,0,0,1,0]]注意主對(duì)角線全是0因?yàn)槲覀兗僭O(shè)沒(méi)有自環(huán)簡(jiǎn)單圖。如果題目允許自環(huán)對(duì)角線對(duì)應(yīng)位置填1。這個(gè)矩陣能直接回答很多問(wèn)題v1的鄰居是誰(shuí)看第一行只有第1列v2是1 → 鄰居是v2。v2和v4連嗎看第二行第四列索引[1][3]是0 → 不連。圖是連通的嗎計(jì)算矩陣的冪A2, A3...如果某次冪后所有非對(duì)角線元素都0說(shuō)明任意兩點(diǎn)間有路徑。但手動(dòng)算冪太麻煩所以鄰接矩陣更適合小圖的直觀觀察。4.2 鄰接表一份“每個(gè)點(diǎn)的朋友圈”清單鄰接表更貼近人的思維。它是一個(gè)列表列表的每個(gè)元素對(duì)應(yīng)一個(gè)頂點(diǎn)里面存著這個(gè)頂點(diǎn)的所有鄰居。對(duì)同一個(gè)5點(diǎn)鏈圖v1: [v2]v2: [v1, v3]v3: [v2, v4]v4: [v3, v5]v5: [v4]在Python里它通常用字典實(shí)現(xiàn)graph { v1: [v2], v2: [v1, v3], v3: [v2, v4], v4: [v3, v5], v5: [v4] }優(yōu)勢(shì)立現(xiàn)查鄰居快graph[v3]直接返回[v2, v4]O(1)時(shí)間。省空間只存儲(chǔ)存在的邊。5個(gè)點(diǎn)最多有10條邊完全圖但這個(gè)圖只有4條邊鄰接表只存4個(gè)字符串而鄰接矩陣要存25個(gè)數(shù)字。增刪邊方便給v1加個(gè)朋友v3graph[v1].append(v3)graph[v3].append(v1)無(wú)向圖要雙向加。4.3 避坑表示法選擇與轉(zhuǎn)換的3個(gè)實(shí)戰(zhàn)陷阱現(xiàn)象題目要求“求v1的度數(shù)”你對(duì)著鄰接矩陣把第一行所有1加起來(lái)得到1但答案是2。原因忘了無(wú)向圖的鄰接矩陣是對(duì)稱的v1-v2這條邊在矩陣?yán)镎剂藘蓚€(gè)位置[0][1]和[1][0]。但度數(shù)是鄰居個(gè)數(shù)不是矩陣?yán)?的總數(shù)。解決算度數(shù)永遠(yuǎn)只看一行或一列別加總整個(gè)矩陣。第一行有1個(gè)1度數(shù)就是1。現(xiàn)象用鄰接表表示有向圖時(shí)把“v1→v2”只加在v1的列表里忘了v2的列表里不需要加v1。原因混淆了無(wú)向圖雙向添加和有向圖單向添加。有向圖的鄰接表只記錄“出邊”。v1→v2只在v1的列表里加v2v2的列表里只有它指向的點(diǎn)。解決畫(huà)個(gè)小箭頭在草稿紙上箭頭從誰(shuí)出發(fā)就往誰(shuí)的列表里加目標(biāo)?，F(xiàn)象需要判斷兩個(gè)圖是否同構(gòu)結(jié)構(gòu)相同只是點(diǎn)標(biāo)簽不同你試圖用鄰接矩陣逐個(gè)比較發(fā)現(xiàn)標(biāo)簽順序不同矩陣就不同于是判否。原因同構(gòu)圖的鄰接矩陣只是行和列的順序不同即存在一個(gè)置換矩陣P使得P·A1·P^T A2。直接比矩陣肯定不行。解決同構(gòu)判定是難題新手應(yīng)聚焦于不變量頂點(diǎn)數(shù)、邊數(shù)、度數(shù)序列把所有頂點(diǎn)度數(shù)從小到大排序列相同才可能同構(gòu)、是否存在三角形等。這份資料在相關(guān)題目解析里會(huì)提示用哪些不變量快速排除。5. 學(xué)完這四講你的下一步該往哪里走——從“會(huì)做題”到“能建?！钡能S遷路徑學(xué)到這里你已經(jīng)掌握了圖論的核心骨架從基本概念點(diǎn)、邊、圖的類型到關(guān)鍵性質(zhì)連通、補(bǔ)、偶再到兩大經(jīng)典問(wèn)題歐拉、哈密頓最后落到了數(shù)據(jù)表示矩陣、表。但這只是開(kāi)始。真正的圖論能力不在于解出慕課的題目而在于當(dāng)你面對(duì)一個(gè)新問(wèn)題時(shí)能本能地問(wèn)“這個(gè)問(wèn)題能不能抽象成一張圖”。比如你幫社團(tuán)設(shè)計(jì)值班表發(fā)現(xiàn)“每個(gè)人不能連續(xù)值兩天”“每天至少兩人”這就可以建模成一個(gè)圖頂點(diǎn)是所有“人-日期”組合邊連接那些沖突的組合如張三周一和張三周二求一個(gè)獨(dú)立集選中的點(diǎn)互不相鄰就解決了。這種建模能力才是圖論賦予你的“超能力”。下面是我為你規(guī)劃的、可立即執(zhí)行的三條進(jìn)階路徑每條都配了具體動(dòng)作不空談5.1 路徑一用Python把課堂知識(shí)跑起來(lái)推薦指數(shù)★★★★★理論不動(dòng)手永遠(yuǎn)是霧里看花。用50行代碼你就能親手驗(yàn)證歐拉定理、畫(huà)出鄰接矩陣、甚至搜索哈密頓路徑。這不是為了炫技而是為了獲得“確定性反饋”——代碼跑通了你就真的懂了報(bào)錯(cuò)了錯(cuò)在哪一清二楚。第一步安裝并跑通基礎(chǔ)環(huán)境確保你有Python 3.7然后安裝NetworkX圖論專用庫(kù)pip install networkx matplotlib第二步復(fù)現(xiàn)“5點(diǎn)鏈圖”的歐拉性判定import networkx as nx # 創(chuàng)建無(wú)向圖 G nx.Graph() G.add_nodes_from([v1,v2,v3,v4,v5]) G.add_edges_from([(v1,v2), (v2,v3), (v3,v4), (v4,v5)]) # 打印每個(gè)頂點(diǎn)的度數(shù) print(各頂點(diǎn)度數(shù):, dict(G.degree())) # 輸出: {v1: 1, v2: 2, v3: 2, v4: 2, v5: 1} # 判定所有度數(shù)是否為偶數(shù) degrees [d for n, d in G.degree()] is_eulerian all(d % 2 0 for d in degrees) print(是否為歐拉圖, is_eulerian) # False運(yùn)行這段代碼你會(huì)親眼看到v1和v5度數(shù)是1奇數(shù)程序輸出False。這就是最硬的證據(jù)。把邊改成[(v1,v2), (v2,v3), (v3,v4), (v4,v5), (v5,v1)]首尾相連成環(huán)再運(yùn)行度數(shù)全變2輸出True。這種即時(shí)反饋比看十頁(yè)解析都管用。5.2 路徑二攻克一個(gè)真實(shí)小項(xiàng)目推薦指數(shù)★★★★☆選一個(gè)你生活中能接觸到的小問(wèn)題用圖論建模解決。我當(dāng)年第一個(gè)項(xiàng)目是優(yōu)化宿舍樓的快遞代取路線。目標(biāo)讓一個(gè)同學(xué)取件員一次性幫5個(gè)人取完快遞路徑最短。這本質(zhì)上就是哈密頓路徑問(wèn)題5個(gè)快遞點(diǎn)1個(gè)起點(diǎn)找最短訪問(wèn)順序。步驟如下抽象把宿舍樓一層平面圖簡(jiǎn)化標(biāo)出5個(gè)快遞柜位置v1-v5和取件員起點(diǎn)s。賦權(quán)用步數(shù)或秒數(shù)估算任意兩點(diǎn)間的距離構(gòu)成一個(gè)6×6的加權(quán)鄰接矩陣。求解用NetworkX的nx.approximation.traveling_salesman_problem近似算法因精確解太慢求最短環(huán)。驗(yàn)證把算出的順序如s→v3→v1→v5→v2→v4→s畫(huà)在紙上量一下總長(zhǎng)度和你隨便走的路線比是不是真短了20%這個(gè)項(xiàng)目不追求完美但做完你會(huì)深刻理解哈密頓圖不是紙上的概念它是解決“最優(yōu)順序”問(wèn)題的數(shù)學(xué)語(yǔ)言。而且你順手學(xué)會(huì)了如何把現(xiàn)實(shí)距離轉(zhuǎn)化為圖的權(quán)重這是建模的關(guān)鍵一步。5.3 路徑三向“圖神經(jīng)網(wǎng)絡(luò)GNN”眺望推薦指數(shù)★★★☆☆如果你對(duì)AI、機(jī)器學(xué)習(xí)感興趣圖論是GNN的基石。GNN能處理社交網(wǎng)絡(luò)、分子結(jié)構(gòu)、知識(shí)圖譜等“關(guān)系型數(shù)據(jù)”而它的輸入就是你剛學(xué)的鄰接矩陣或鄰接表。GNN的第一層就是對(duì)每個(gè)頂點(diǎn)聚合它鄰居的特征就像你查graph[v3]拿到[v2,v4]然后把v2和v4的特征加起來(lái)。所以你現(xiàn)在學(xué)的鄰接表就是未來(lái)讀懂GNN代碼的“母語(yǔ)”。不必現(xiàn)在就學(xué)GNN但可以做個(gè)標(biāo)記當(dāng)你看到一篇講“GNN如何預(yù)測(cè)用戶是否會(huì)購(gòu)買(mǎi)某商品”的文章時(shí)試著去找到它的圖結(jié)構(gòu)——用戶是點(diǎn)購(gòu)買(mǎi)行為是邊還是商品是點(diǎn)共同購(gòu)買(mǎi)是邊用你剛練熟的“建模三問(wèn)”誰(shuí)是點(diǎn)誰(shuí)是邊邊有權(quán)重嗎去拆解它。這種習(xí)慣會(huì)讓你在未來(lái)接觸前沿技術(shù)時(shí)少一層隔膜。從那以后我每次學(xué)一個(gè)新算法都強(qiáng)制自己用NetworkX造一個(gè)小圖跑一遍再手動(dòng)畫(huà)出結(jié)果。哪怕只是驗(yàn)證一個(gè)度數(shù)我也要看到print()輸出的數(shù)字和我心算的一致。這種“眼見(jiàn)為實(shí)”的確認(rèn)感是驅(qū)散數(shù)學(xué)焦慮最好的后悔藥。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取