-----------
通知：如果本站對你學(xué)習(xí)算法有幫助踊淳，請收藏網(wǎng)址，并推薦給你的朋友迂尝。由于 labuladong 的算法套路太火，很多人直接拿我的 GitHub 文章去開付費專欄垄开，價格還不便宜。我這免費寫給你看税肪，多宣傳原創(chuàng)作者是你唯一能做的，誰也不希望劣幣驅(qū)逐良幣對吧益兄？
咱們的公眾號有很多硬核的算法文章，今天就聊點輕松的净捅，就具體聊聊我非常“鼓吹”的《算法4》蛔六。這本書我在之前的文章多次推薦過，但是沒有具體的介紹古今，今天就來正式介紹一下滔以。。
我的推薦不會直接甩一大堆書目你画，而是會聯(lián)系實際生活抵碟，講一些書中有趣有用的知識，無論你最后會不會去看這本書坏匪，本文都會給你帶來一些收獲拟逮。
首先這本書是適合初學(xué)者的∈首遥總是有很多讀者問敦迄，我只會 C 語言，能不能看《算法4》？學(xué)算法最好用什么語言罚屋？諸如此類的問題苦囱。
經(jīng)常看咱們公眾號的讀者應(yīng)該體會到了脾猛，算法其實是一種思維模式撕彤，和你用什么語言沒啥關(guān)系。我們的文章也不會固定用某一種語言猛拴，而是什么語言寫出來容易理解就用什么語言羹铅。再退一步說，到底適不適合你愉昆，網(wǎng)上找個 PDF 親自看一下不就知道了职员？
《算法4》看起來挺厚的，但是前面幾十頁是教你 Java 的跛溉；每章后面還有習(xí)題廉邑，占了不少頁數(shù)；每章還有一些數(shù)學(xué)證明倒谷，這些都可以忽略蛛蒙。這樣算下來，剩下的就是基礎(chǔ)知識和疑難解答之類的內(nèi)容渤愁，含金量很高牵祟，把這些基礎(chǔ)知識動手實踐一遍，真的就可以達(dá)到不錯的水平了抖格。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)诺苹，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄雹拄，持續(xù)更新收奔。建議收藏，按照我的文章順序刷題滓玖，掌握各種算法套路后投再入題海就如魚得水了坪哄。
我覺得這本書之所以能有這么高的評分，一個是因為講解詳細(xì)势篡，還有大量配圖翩肌，另一個原因就是書中把一些算法和現(xiàn)實生活中的使用場景聯(lián)系起來禁悠，你不僅知道某個算法怎么實現(xiàn)，也知道它大概能運用到什么場景粱坤，下面我就來介紹兩個圖算法的簡單應(yīng)用。
一站玄、二分圖的應(yīng)用
我想舉的第一個例子是二分圖蜒什。簡單來說，二分圖就是一幅擁有特殊性質(zhì)的圖：能夠用兩種顏色為所有頂點著色霎冯，使得任何一條邊的兩個頂點顏色不同沈撞。
明白了二分圖是什么缠俺，能解決什么實際問題呢贷岸？算法方面偿警，常見的操作是如何判定一幅圖是不是二分圖。比如說下面這道 LeetCode 題目：
你想想盒使，如果我們把每個人視為一個頂點少办，邊代表討厭英妓；相互討厭的兩個人之間連接一條邊鞋拟，就可以形成一幅圖惹资。那么根據(jù)剛才二分圖的定義褪测，如果這幅圖是一幅二分圖，就說明這些人可以被分為兩組懈叹，否則的話就不行澄成。
這是判定二分圖算法的一個應(yīng)用畏吓，其實二分圖在數(shù)據(jù)結(jié)構(gòu)方面也有一些不錯的特性。
比如說我們需要一種數(shù)據(jù)結(jié)構(gòu)來儲存電影和演員之間的關(guān)系：某一部電影肯定是由多位演員出演的肾砂，且某一位演員可能會出演多部電影宏悦。你使用什么數(shù)據(jù)結(jié)構(gòu)來存儲這種關(guān)系呢？
既然是存儲映射關(guān)系源葫，最簡單的不就是使用哈希表嘛臼氨，我們可以使用一個 HashMap<String, List<String>> 來存儲電影到演員列表的映射芭届，如果給一部電影的名字，就能快速得到出演該電影的演員持隧。
但是如果給出一個演員的名字屡拨，我們想快速得到該演員演出的所有電影，怎么辦呢呀狼？這就需要「反向索引」哥艇，對之前的哈希表進(jìn)行一些操作貌踏，新建另一個哈希表，把演員作為鍵祖乳，把電影列表作為值。
對于上面這個例子蜒秤，可以使用二分圖來取代哈希表作媚。電影和演員是具有二分圖性質(zhì)的：如果把電影和演員視為圖中的頂點伞访，出演關(guān)系作為邊，那么與電影頂點相連的一定是演員弟灼，與演員相鄰的一定是電影田绑，不存在演員和演員相連掩驱，電影和電影相連的情況。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)欧穴，手把手刷 200 道力扣題目涮帘，全部發(fā)布在 labuladong的算法小抄调缨，持續(xù)更新吆你。建議收藏，按照我的文章順序刷題伤哺，掌握各種算法套路后投再入題海就如魚得水了默责。
回顧二分圖的定義咸包，如果對演員和電影頂點著色，肯定就是一幅二分圖：
如果這幅圖構(gòu)建完成媒熊，就不需要反向索引芦鳍，對于演員頂點葛账，其直接連接的頂點就是他出演的電影籍琳，對于電影頂點，其直接連接的頂點就是出演演員喝峦。
當(dāng)然呜达，對于這個問題，書中還提到了一些其他有趣的玩法眉踱，比如說社交網(wǎng)絡(luò)中「間隔度數(shù)」的計算（六度空間理論應(yīng)該聽說過）等等霜威，其實就是一個 BFS 廣度優(yōu)先搜索尋找最短路徑的問題侥祭，具體代碼實現(xiàn)這里就不展開了矮冬。
二、套匯的算法
如果我們說貨幣 A 到貨幣 B 的匯率是 10吆录，意思就是 1 單位的貨幣 A 可以換 10 單位貨幣 B恢筝。如果我們把每種貨幣視為一幅圖的頂點，貨幣之間的匯率視為加權(quán)有向邊此改，那么整個匯率市場就是一幅「完全加權(quán)有向圖」侄柔。
一旦把現(xiàn)實生活中的情景抽象成圖暂题，就有可能運用算法解決一些問題薪者。比如說圖中可能存在下面的情況：
圖中的加權(quán)有向邊代表匯率言津，我們可以發(fā)現(xiàn)如果把 100 單位的貨幣 A 換成 B纺念，再換成 C陷谱，最后換回 A，就可以得到 100×0.9×0.8×1.4 = 100.8 單位的 A渣窜！如果交易的金額大一些的話乔宿，賺的錢是很可觀的访雪，這種空手套白狼的操作就是套匯臣缀。
現(xiàn)實中交易會有種種限制，而且市場瞬息萬變精置，但是套匯的利潤還是很高的番宁，關(guān)鍵就在于如何快速找到這種套匯機(jī)會呢？
借助圖的抽象踱蠢，我們發(fā)現(xiàn)套匯機(jī)會其實就是一個環(huán)播聪，且這個環(huán)上的權(quán)重之積大于 1离陶，只要在順著這個環(huán)交易一圈就能空手套白狼衅檀。
圖論中有一個經(jīng)典算法叫做 Bellman-Ford 算法沉眶，可以用于尋找負(fù)權(quán)重環(huán)谎倔。對于我們說的套匯問題片习，可以先把所有邊的權(quán)重 w 替換成 -ln(w)藕咏，這樣「尋找權(quán)重乘積大于 1 的環(huán)」就轉(zhuǎn)化成了「尋找權(quán)重和小于 0 的環(huán)」孽查，就可以使用 Bellman-Ford 算法在 O(EV) 的時間內(nèi)尋找負(fù)權(quán)重環(huán)盲再，也就是尋找套匯機(jī)會答朋。
《算法4》就介紹到這里绿映，關(guān)于上面兩個例子的具體內(nèi)容丐一，可以自己去看書库车，公眾號后臺回復(fù)關(guān)鍵詞「算法4」就有 PDF柠衍。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)晶乔，手把手刷 200 道力扣題目珍坊，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新正罢。建議收藏阵漏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了翻具。
三履怯、最后說幾句
首先，前文說對于數(shù)學(xué)證明裆泳、章后習(xí)題可以忽略叹洲，可能有人要抬杠了：難道習(xí)題和數(shù)學(xué)證明不重要嗎？
那我想說工禾，就是不重要运提，起碼對大多數(shù)人來說不重要帜篇。我覺得吧，學(xué)習(xí)就要帶著目的性去學(xué)签钩，大部分人學(xué)算法不就是鞏固計算機(jī)知識，對付面試題目嗎拾给？如果是這個目的乒疏，那就學(xué)些基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法窍侧，明白它們的時間復(fù)雜度暇咆，然后去刷題就好了亏镰，何必和習(xí)題、證明過不去耸黑？
這也是我從來不推薦《算法導(dǎo)論》這本書的原因缺菌。如果有人給你推薦這本書，只可能有兩個原因剂陡，要么他是真大佬顽爹，要么他在裝大佬捏题。《算法導(dǎo)論》中充斥大量數(shù)學(xué)證明，而且很多數(shù)據(jù)結(jié)構(gòu)是很少用到的，頂多當(dāng)個字典用。你說你學(xué)了那些有啥用呢，饒過自己唄见转。
另外校焦，讀書在精不在多耸成。你花時間《算法4》過個大半（最后小半部分有點困難），同時刷點題劲件，看看咱們的公眾號文章牵辣，算法這塊真就夠了，別對細(xì)節(jié)問題太較真。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目泳桦，建議收藏浮毯！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star芳誓，歡迎標(biāo)星赂摆！
