經典圖論演算法

① 數學圖論中有哪些典型模型

偶圖模型
凡涉及兩類事物間的聯系（即只考慮兩類事物間的聯系，而不考慮同類事物間的聯系），均可抽象成偶圖模型。作圖時，將兩類事物分成兩行或者兩列。這類模型通常被包含在後續的模型中，但因許多現實問題可抽象成該模型，所以單列出來討論。
(1) 倉庫與銷售間
M：點代表倉庫或銷售點，連線代表倉庫與銷售店間的關聯
(2) 上課安排問題
Q：學校有6位教師將開設6門課程。六位教師的代號是Xi（i=1,2,3,4,5,6)，六門課程代號是Yi （i=1,2,3,4,5,6)。已知，教師X1能夠勝任課程Y2和Y3；教師X2能夠勝任課程Y4和Y5；教師X3能夠勝任課程Y2；教師X4能夠勝任課程Y6和Y3；教師Y5能夠勝任課程Y1和Y6；教師X6能夠勝任課程Y5和Y6。
M：點表示教師或者課程，連線表示當且僅當該教師能勝任該課程
2.2 最短路模型
凡涉及到最小狀態轉換問題，均可轉化為最短路模型。點表示允許的狀態，連線表示狀態的轉換（可逆與不可逆分別對應於無向圖、有向圖）。
(1) 最短航線
M：點表示城市，連線表示當且僅當兩城市有直達航線，並在該線上註明兩城市的距離，即權值
A：問題轉化為求兩點間的最短路徑
(2) 狀態轉換
Q：某兩人有一隻8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升。求最少的操作次數能均分酒。
M：設x1,x2,x3分別表示8,5,3升酒壺中的酒量，則
點表示組合(x1,x2,x3) ,連線表示當且僅當可通過倒酒的方式相互變換
A：問題轉化為在該圖中求點(8,0,0)到點(4,4,0)的一條最短路
(3) 狼羊菜渡河
Q：在一河岸有狼，羊和捲心菜。擺渡人要將它們渡過河去，由於船太小，每次只能載一樣東西。由於狼羊，羊捲心菜不能單獨相處。問擺渡人至少要多少次才能將其渡過河？
M：但是以下組合不能允許出現：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。岸上只能允許出現10種組合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。
點表示可允許的組合，連線當且僅當兩種情況可用載人(或加一物)的渡船相互轉變。
A：問題轉化為求由頂點「人狼羊菜」到頂點「空」的一條最短路。
2.3 最小生成樹模型
道路鋪設
Q：道路鋪設，使得任意兩個地方均可達，並且費用最小
M：點表示工廠(假設是工廠)，任意兩點連線，並標出鋪設需要的費用
A：問題轉化為求該圖的最小生成樹
2.4 歐拉圖模型
通俗地講，G是歐拉圖當且僅當G存在經過每條邊恰好一次，並且回到起始點的跡。
(1) 哥尼斯堡七橋問題
Q：能否從一點出發，走遍7座橋，且通過每座橋恰好一次，最後仍回到起始地點
M：點表示陸地，連線表示橋
A：問題轉化為G是否存在E圖
(2) 中國郵遞員問題
Q：郵遞員必須走過他投遞范圍內的每一條街道至少一次，選擇一條盡可能短的路線
M：點表示路口，連線表示當且僅當兩路口有直達街道
A：若G是E圖，通過Fleury演算法構造Euler環游，即為所求。否則，按一定規則添加重復邊，再用Fleury演算法構造Euler環游。
2.5 哈密爾頓圈模型
(1) 旅行售貨員問題——TSP
一售貨員要到若干城市去售貨，每座城市只經歷一次，問如何安排行走路線，使其行走的總路程最短。
例子：
Q：一電腦代理商要從她所在城市出發，乘飛機去六個城市，然後回到出發點，如果要求每個城市只經歷一次，能否辦到？給出行走方案。
M：點表示城市，連線表示兩城市有直達航線
A：該圖是否存在H圈
(2) 圓桌會議座位安排
Q：若幹人圍圓周開會，每個人會不同的語言，如何安排座位，使得每個人能夠和他身邊的交流
M：點表示人，連線表示當且僅當兩個人能交流，即至少會同一種語言。(可能你一下子想到的偶圖模型，的確該問題可以抽象成偶圖模型，但很難轉化為圖論問題)
A：給出該圖的一個H圈
2.6 匹配模型
(1) 旅遊座位安排
Q：有一個旅行團要組織一批人去旅遊，其中一些人是朋友他們要乘坐公共汽車去，而車上的位子是成對的。因此為了讓大家旅途更愉快，旅行團負責人需要將成對的朋友安排在一起。給出一種安排方案。
M：點表示旅行團的人，連線表示當且僅當兩人是朋友
A：求該圖的最大匹配
(2) 研究生找工作
Q：學生能找到理想工作嗎？
M：點表示研究生或者工作，連線表示當且僅當學生申請了該工作
A：問題轉化為求飽和每個頂點的一個匹配，即完美匹配
(3) 最優分派問題
M：點表示工作或者人員，構造完全偶圖，邊的權值表示該工人做此份工作的效率
A：問題轉化為求該圖的最優匹配
2.7 平面圖模型
平面模型可以這樣理解，交通網路，使得不交叉，且無需修高架橋、隧道（這里的隧道顯然跟山洞不同）
(1) 電路板設計問題
Q: 連接電路元件間的導線間不能交叉。否則，當絕緣層破損時，會出現短路故障。
M；點表示電路元器件，連線表示元器件間的連接
A；該圖是否可平面
(2) 景區空調管道的設計
M：點表示景區，連線表示當且僅當兩景點間要鋪設空調管道
A：能否把上圖畫在平面上，使得邊不會相互交叉？
(3) 3間房子和3種設施問題
Q：要求把3種公用設施(煤氣，水和電)分別用煤氣管道、水管和電線連接到3間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？
M：點表示公用設施或者房子，連線表示該類公用設施連接到該房子
A：抽象出來的圖是否可平面嵌入
2.8 著色模型
點著色問題對應於頂點集合的一種劃分方式，對應於分類問題。邊著色對應於邊集合的一種劃分方式，也對應於分類問題。區分點著色模型和邊著色模型，主要在於抽象出來的模型，是相鄰的頂點還是相鄰的邊不能著同一種顏色。
(1) 點著色模型
① 考試時間安排
Q：使得學生們不會有相互沖突的考試，最小安排數
M：點表示待考的課程，連線表示至少有一個學生同時選擇這兩門課
A：問題轉化為求該圖的點色數(把互不沖突的課程、考試安排在同一個時間段完成)
② 課程安排問題
Q: 學生選擇課程中，使得學生選課不會發生沖突，如何制訂一張課時數盡可能小少的課表
M：點表示課程，連線表示當且僅當有某個學生同時選了這兩門課程
A：問題轉化為求該圖的點色數
③ 交通燈的相位設置問題
Q：為了(最終)讓所有的車輛都能夠安全通過路口，對於交通燈來說，所需要的相位的最小數是多少
M：點表示車道，連線當且僅當兩個車道上的車不能同時安全地進入路口
A：問題轉化為求該圖的點色數
(2)邊著色模型
① 排課表問題
Q：設有m位教師，n個班級，其中教師xi要給班級yj上pij節課。求如何在最少節次排完所有課。
M：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi與yj間連pij條邊，得偶圖G=(X, Y)。
A：問題轉化為求該圖的邊著色數
(2) 比賽安排問題
Q：最少天完成比賽
M：點表示參賽人，連線當且僅當兩人有比賽
A:問題轉化為求一種最優邊著色，即用最少色數進行正常邊著色
2.9 覆蓋模型
覆蓋模型，對應於控制問題，通俗地講點覆蓋對應於用最少的點來控制所有邊(即任一邊至少有一個頂點在點獨立集中)，邊覆蓋對應於用最少的邊控制所有的點。均對應於控制問題。
(1) 哨站設計
Q：城市設置哨崗，使得哨兵能監管所有街道的最少哨崗數
M：點表示交叉口，連線表示存在直達街道
A：問題轉化為求該圖的點覆蓋
2.10 強連通性定向圖模型
(1) 城市交通網設計問題
Q：一座城市為某種需要，要把所有街道改為單行道，使得人們在任意兩個位置都可以相互到達。如何設計單行道方向
M：頂點表示街道交叉口，連線當且僅當存在直達街道
A：問題等價於在模型圖中給出其強連通定向
(2) 競賽圖
M：循環比賽的結果可以用所謂的「競賽圖」來表示。u隊戰勝了v隊，則由點u向v畫一條有向邊。顯然，「競賽圖」是完全圖的一種定向圖。

② 求經典圖論教材圖論及其應用（邦迪）清晰點的電子版

郵 箱？？？？？

③ 圖論演算法的教材

我想很多學習圖論的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是圖論教材中的經典，時至今日，仍不失為初學者較好的入門書。還記得蘭州交通大學的張忠輔教授說過，國內第一屆圖論學會就是把大家集中起來學習邦迪的《Graph Theory with Application》，由此可見這本書對國內圖論屆的影響是如此之大。吳望名等人將其譯成中文版本《圖論及其應用》（北京：科學出版社，1984），1988年張克民等人編寫了該書的參考答案《圖論及其應用習題解答》（清華大學出版社，1988）。
在2008年J.A. Bondy和U.S.R. Murty出了新書《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨將其看成是《Graph Theory with Application》的第二版，這本書在內容上做了重新調整，畢竟在第一版出版後的近30年裡涌現出了很多新的結果，所以《Graph Theory》在內容上加進了一些新的結果，這本書我只是讀了其中的幾章，覺得寫的非常棒，建議大家能夠讀讀，這里也值得一提的是將第一版最後提出的50個問題進行了更新，並補充了一些新的問題。總之，我個人認為，《Graph Theory》的確是一部很優秀的圖論教材。
中國科學技術大學出版社出版的《圖論及其演算法》，融有向圖和無向圖為一整體，系統地闡述了圖論的基本概念、理論、方法及其演算法，內容包括圖的基本概念、Euler圖與Hamilton圖、圖論演算法、樹及其應用、平面圖、獨立集與匹配、網路流和Petri網。 書中附有大量例題和習題，而且大部分習題有詳細解答。 該書選材精煉全面，內容處理恰當且有新意，立論嚴謹，敘述條理清晰，語言流暢。 該書可用作高校計算機、電子、信息、管理、數學等專業本科生必修課教材，也可供相關專業的研究人員、教師及圖論工作者參考。

④ 推薦幾本圖論入門教程或者經典書籍

關於圖論的入門書，我之前研究過幾本，對於初學者來講有非常大的幫助的，而且我還覺得，對中級學習的人作為進階學習也是非常不錯的，基本上初中級學習者，可以得到很大的進步，下面我介紹給你，並幫你分析一下緣由。

經過我的研究，我覺得圖與圖之間的相似性可能會受到數據挖掘演算法的影響，雖然我以前從未學過，而數學系理論嚴重的不應該是研究的課題，相似性不是很明確的尺度嗎？但是計算機部門可能有一項研究，可以看看這本書：《挖掘異構信息網路：原則和方法》。

總結：

所以我覺得如果是初學圖論的話，對於這種圖與圖之間的相似計算研究，還是慢慢來學習比較好，一定要打好基礎，不然後面會非常難，很多人就是因為基礎不好，學到一半就放棄了，學習這門學科是要有一定的耐心的，如果不能沉下心來學習，到後面實際操作的時候是非常困難的。

⑤ 理解圖論演算法有什麼意義

隨著計算機的出現和發展，圖論得到了快速的發展，其應用范圍覆蓋了從自然科學到社會科學的廣闊的領域，包括:電信網路、電力網路、可靠性理論、運輸能力、控制論、計算機程序設計、人工智慧、地圖著色、情報檢索、社會結構、運籌學、經濟學、遺傳學等。

⑥ 請問什麼是演算法

也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。 一個演算法應該具有以下五個重要的特徵： 演算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。1、有窮性（Finiteness） 演算法的有窮性是指演算法必須能在執行有限個步驟之後終止2、確切性(Difiniteness) 演算法的每一步驟必須有確切的定義；3、輸入項(Input) 一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件；4、輸出項(Output) 一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；5、可行性(Effectiveness) 演算法中執行的任何計算步都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成。（也稱之為有效性） 計算機科學家尼克勞斯-沃思曾著過一本著名的書《數據結構十演算法= 程序》，可見演算法在計算機科學界與計算機應用界的地位。編輯本段演算法的復雜度 同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。時間復雜度 演算法的時間復雜度是指執行演算法所需要的時間。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法的時間復雜度也因此記做 T(n)=Ο(f(n)) 因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。空間復雜度 演算法的空間復雜度是指演算法需要消耗的內存空間。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。 詳見網路詞條"演算法復雜度"編輯本段演算法設計與分析的基本方法1.遞推法 遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關系，從而達到目的，此方法稱為遞推法。2.遞歸 遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知3.窮舉搜索法 窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。4.貪婪法 貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。5.分治法 分治法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。6.動態規劃法 動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。7.迭代法 迭代法是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法。編輯本段演算法分類 演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法。 演算法可以宏泛的分為三類： 有限的，確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。 有限的，非確定演算法 這類演算法在有限的時間內終止。然而，對於一個（或一些）給定的數值，演算法的結果並不是唯一的或確定的。 無限的演算法 是那些由於沒有定義終止定義條件，或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常，無限演算法的產生是由於未能確定的定義終止條件。編輯本段舉例 經典的演算法有很多，如："歐幾里德演算法，割圓術，秦九韶演算法"。編輯本段演算法經典專著 目前市面上有許多論述演算法的書籍，其中最著名的便是《計算機程序設計藝術》（The Art Of Computer Programming) 以及《演算法導論》（Introction To Algorithms）。編輯本段演算法的歷史 「演算法」即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了演算法這個概念。「演算法」原為"algorism"，意思是阿拉伯數字的運演算法則，在18世紀演變為"algorithm"。歐幾里得演算法被人們認為是史上第一個演算法。 第一次編寫程序是Ada Byron於1842年為巴貝奇分析機編寫求解解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。 因為"well-defined procere"缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用的。 求素數的埃拉托塞尼篩法和求方根的開方的方法公式（演算法不等於公式，公式卻是提供一種演算法）

⑦ 求C++和數據結構經典演算法。

給你個我整理的列表吧，這些書上面的題目都做出來，直接去谷歌、蘋果、Facebook找工作吧。

難度系數3顆星
《挑戰編程》http://book.douban.com/subject/3879470/
《演算法競賽入門經典》http://book.douban.com/subject/4138920/
《程序設計實踐》http://book.douban.com/subject/1173548/
《演算法之道》http://book.douban.com/subject/4249686/
難度系數4顆星
《計算機演算法的設計與分析》http://book.douban.com/subject/1683278/
《演算法導論》http://book.douban.com/subject/1885170/
《編程珠璣》http://book.douban.com/subject/1230206/
《編程珠璣2》http://book.douban.com/subject/3234692/
《編程之美》http://book.douban.com/subject/3004255/
《演算法設計手冊》The Algorithm Design Manual
《演算法設計與分析基礎》http://book.douban.com/subject/1173877/
《演算法引論》http://book.douban.com/subject/1436134/
《演算法.Sedgewick》 http://book.douban.com/subject/1143801/
難度系數5顆星
《演算法藝術與信息學競賽》http://book.douban.com/subject/1154204/
《具體數學》http://book.douban.com/subject/1390010/
《計算機程序設計藝術》http://book.douban.com/subject/1418402/
《計算機程序的構造和解釋》http://book.douban.com/subject/1148282/
《高級數據結構》http://book.douban.com/subject/3328585/

專題類的演算法
《隨機演算法》http://book.douban.com/subject/3269796/
《近似演算法》http://book.douban.com/subject/1823807/
《如何求解問題：現代啟發式方法》http://book.douban.com/subject/1232071/
《組合優化》http://book.douban.com/subject/1823805/
《網路流》http://book.douban.com/subject/1316052/
《計算幾何》http://book.douban.com/subject/1445320/
《概率與計算》http://book.douban.com/subject/2056370/
《柔性字元串匹配》http://book.douban.com/subject/2038862/
《應用密碼學》http://book.douban.com/subject/1088180/

數學類，太多，少推薦幾本
《怎樣解題》http://book.douban.com/subject/1013762/
《陶哲軒教你學數學》http://book.douban.com/subject/3921816/
《什麼是數學》http://book.douban.com/subject/1320282/
《圖論》http://book.douban.com/subject/1921943/
《組合數學》http://book.douban.com/subject/1231452/
《計數組合學》http://book.douban.com/subject/1193832/

⑧ 用圖論做一個求迷宮最短路徑的演算法

01.#include <stdio.h>
02.#define MAXN 10
03.int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
04.char name[] = {'U', 'D', 'L', 'R'};
05.int q[MAXN * MAXN]; //隊列，保存當前結點編號
06.int vis[MAXN][MAXN], nMap[MAXN][MAXN];
07.int m, n; //行、列數
08.int dir[MAXN * MAXN];
09.int fa[MAXN][MAXN], dis[MAXN][MAXN], last_dir[MAXN][MAXN];
10.void funcInit();
11.void bfs(int x, int y);
12.void funcInput();
13.void print_path(int x, int y);
14.int main()
15.{
16. funcInput();
17. funcInit();
18. bfs(0, 0);
19. print_path(m - 1, n - 1);
20. return 0;
21.}
22.void funcInit()
23.{
24. int i, j;
25. for (i = 0; i != m; ++i)
26. {
27. for (j = 0; j != n; ++j)
28. {
29. vis[i][j] = 0;
30. dis[i][j] = 0;
31. }
32. }
33.}
34.void funcInput()
35.{
36. int i, j;
37. scanf("%d %d", &m, &n);
38. for (i = 0; i != m; ++i)
39. {
40. for (j = 0; j != n; ++j)
41. {
42. scanf("%d", &nMap[i][j]);
43. }
44. }
45.}
46.void bfs(int x, int y)
47.{
48. int front = 0, rear = 0;
49. int d, u; //方向標記、結點編號
50.
51. u = x * m + y;
52. vis[x][y] = 1;
53. fa[x][y] = u;
54. q[rear++] = u; //將當前結點編好放入隊列
55.
56. while (front != rear)
57. {
58. u = q[front++];
59. x = u / m; y = u % m;
60. for (d = 0; d != 4; ++d)
61. {
62. int nx = x + dx[d], ny = y + dy[d];
63. if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && !nMap[nx][ny])
64. {
65. int v = nx * m + ny;
66. q[rear++] = v;
67. vis[nx][ny] = 1;
68. fa[nx][ny] = u;
69. dis[nx][ny] = dis[x][y] + 1; //記錄路徑長度
70. last_dir[nx][ny] = d; //記錄移動方向標記
71. }
72. }
73. }
74.}
75.void print_path(int x, int y)
76.{
77. int c = 0;
78.
79. while (1)
80. {
81. int fx = fa[x][y] / m;
82. int fy = fa[x][y] % m;
83. if (fx == x && fy == y) break;
84. dir[c++] = last_dir[x][y];
85. x = fx; y = fy;
86. }
87. while (c--)
88. {
89. putchar(name[dir[c]]);
90. putchar('/n');
91. }
92. printf("最短路徑長度為:%d/n", dis[m-1][n-1]);
93.}

⑨ 網路爬蟲設計類圖論中的哪些經典演算法

根據PageRank的思想，編程在網路爬蟲中實現。它的核心思想是能夠發現權威超鏈接，通常的實現方法是將新分析出來的超鏈接與舊的超鏈接比對，使超鏈接的權重增加，從而抓取權重高的超鏈接。因為我們無法收錄所有的超鏈接只能撿重要的收錄。