共计 2470 个字符，预计需要花费 7 分钟才能阅读完成。
———–
告诉：如果本站对你学习算法有帮忙，请珍藏网址，并举荐给你的敌人 。因为 labuladong 的算法套路太火，很多人间接拿我的 GitHub 文章去开付费专栏，价格还不便宜。我这收费写给你看， 多宣传原创作者是你惟一能做的，谁也不心愿劣币驱赶良币对吧？
咱们的公众号有很多硬核的算法文章，明天就聊点轻松的，就具体聊聊我十分“宣扬”的《算法 4》。这本书我在之前的文章屡次举荐过，然而没有具体的介绍，明天就来正式介绍一下。。
我的举荐不会间接甩一大堆书目，而是会联系实际生存，讲一些书中乏味有用的常识，无论你最初会不会去看这本书，本文都会给你带来一些播种。
首先这本书是适宜初学者的。总是有很多读者问，我只会 C 语言，能不能看《算法 4》？学算法最好用什么语言？诸如此类的问题。
常常看咱们公众号的读者应该领会到了，算法其实是一种思维模式，和你用什么语言没啥关系。咱们的文章也不会固定用某一种语言，而是什么语言写进去容易了解就用什么语言。再退一步说，到底适不适宜你，网上找个 PDF 亲自看一下不就晓得了？
《算法 4》看起来挺厚的，然而后面几十页是教你 Java 的；每章前面还有习题，占了不少页数；每章还有一些数学证实，这些都能够疏忽。这样算下来，剩下的就是基础知识和疑难解答之类的内容，含金量很高，把这些基础知识入手实际一遍，真的就能够达到不错的程度了。
我感觉这本书之所以能有这么高的评分，一个是因为解说具体，还有大量配图，另一个起因就是书中把一些算法和现实生活中的应用场景分割起来，你不仅晓得某个算法怎么实现，也晓得它大略能使用到什么场景，上面我就来介绍两个图算法的简略利用。
一、二分图的利用
我想举的第一个例子是 二分图。简略来说，二分图就是一幅领有非凡性质的图：可能用两种色彩为所有顶点着色，使得任何一条边的两个顶点色彩不同。
明确了二分图是什么，能解决什么理论问题呢？算法方面，常见的操作是如何断定一幅图是不是二分图。比如说上面这道 LeetCode 题目：
你想想，如果咱们把每个人视为一个顶点，边代表厌恶；互相厌恶的两个人之间连贯一条边，就能够造成一幅图。那么依据方才二分图的定义，如果这幅图是一幅二分图，就阐明这些人能够被分为两组，否则的话就不行。
这是断定二分图算法的一个利用，其实二分图在数据结构方面也有一些不错的个性。
比如说咱们须要一种数据结构来贮存电影和演员之间的关系：某一部电影必定是由多位演员出演的，且某一位演员可能会出演多部电影。你应用什么数据结构来存储这种关系呢？
既然是存储映射关系，最简略的不就是应用哈希表嘛，咱们能够应用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射，如果给一部电影的名字，就能疾速失去出演该电影的演员。
然而如果给出一个演员的名字，咱们想疾速失去该演员上演的所有电影，怎么办呢？这就须要「反向索引」，对之前的哈希表进行一些操作，新建另一个哈希表，把演员作为键，把电影列表作为值。
对于下面这个例子，能够应用二分图来取代哈希表。电影和演员是具备二分图性质的：如果把电影和演员视为图中的顶点，出演关系作为边，那么与电影顶点相连的肯定是演员，与演员相邻的肯定是电影，不存在演员和演员相连，电影和电影相连的状况。
回顾二分图的定义，如果对演员和电影顶点着色，必定就是一幅二分图：
如果这幅图构建实现，就不须要反向索引，对于演员顶点，其间接连贯的顶点就是他出演的电影，对于电影顶点，其间接连贯的顶点就是出演演员。
当然，对于这个问题，书中还提到了一些其余乏味的玩法，比如说社交网络中「距离度数」的计算（六度空间实践应该据说过）等等，其实就是一个 BFS 广度优先搜寻寻找最短门路的问题，具体代码实现这里就不开展了。
二、套汇的算法
如果咱们说货币 A 到货币 B 的汇率是 10，意思就是 1 单位的货币 A 能够换 10 单位货币 B。如果咱们把每种货币视为一幅图的顶点，货币之间的汇率视为加权有向边，那么整个汇率市场就是一幅「齐全加权有向图」。
一旦把现实生活中的情景形象成图，就有可能使用算法解决一些问题。比如说图中可能存在上面的状况：
图中的加权有向边代表汇率，咱们能够发现如果把 100 单位的货币 A 换成 B，再换成 C，最初换回 A，就能够失去 100×0.9×0.8×1.4 = 100.8 单位的 A！如果交易的金额大一些的话，赚的钱是很可观的，这种空手套白狼的操作就是套汇。
事实中交易会有种种限度，而且市场瞬息万变，然而套汇的利润还是很高的，要害就在于如何 疾速 找到这种套汇机会呢？
借助图的形象，咱们发现套汇机会其实就是一个环，且这个环上的权重之积大于 1，只有在顺着这个环交易一圈就能空手套白狼。
图论中有一个经典算法叫做 Bellman-Ford 算法，能够用于寻找负权重环。对于咱们说的套汇问题，能够先把所有边的权重 w 替换成 -ln(w)，这样「寻找权重乘积大于 1 的环」就转化成了「寻找权重和小于 0 的环」，就能够应用 Bellman-Ford 算法在 O(EV) 的工夫内寻找负权重环，也就是寻找套汇机会。
《算法 4》就介绍到这里，对于下面两个例子的具体内容，能够本人去看书，公众号后盾回复关键词「算法 4」就有 PDF。
三、最初说几句
首先，前文说对于数学证实、章后习题能够疏忽，可能有人要抬杠了：难道习题和数学证实不重要吗？
那我想说，就是不重要，起码对大多数人来说不重要。我感觉吧，学习就要带着目的性去学，大部分人学算法不就是坚固计算机常识，凑合面试题目吗？如果是这个目标，那就学些根本的数据结构和经典算法，明确它们的工夫复杂度，而后去刷题就好了，何必和习题、证实过不去？
这也是我从来不举荐《算法导论》这本书的起因。如果有人给你举荐这本书，只可能有两个起因，要么他是真大佬，要么他在装大佬。《算法导论》中充斥大量数学证实，而且很多数据结构是很少用到的，顶多当个字典用。你说你学了那些有啥用呢，饶过本人呗。
另外，读书在精不在多。你花工夫《算法 4》过个大半（最初小半局部有点艰难），同时刷点题，看看咱们的公众号文章，算法这块真就够了，别对细节问题太较真。