背景
⽹络爬⾍；
地图应⽤：⾼德地图，百度地图（最短路径推荐，最短时⻓推荐）；
社交⽹络分析：好友推荐，垃圾⽤户分析，社交关系分析；
推荐、精准营销；
舆情控制，信息传播；
防欺诈（⽹络诈骗和电信诈骗）；
计算⽣物学：模拟分⼦运动；
图的分类
有向图
⽆向图
权重图
图的基本概念
顶点集合（vex-set）：如上图S(vex) = {'A', 'B', 'C', 'D', 'E', 'F'}
边集合（arc-set）：如上图S(arc) = {<'A', 'B'>, <'A', 'C'>, <'A', 'D'>, <'B', 'F'>, <'B', 'C'>, <'C', 'E'>, <'D', 'E'>, <'E', 'F'>}
度（degree）：⽆向图中从⼀个点延伸出去的边数就是该点的度；有向图中包含出度和⼊度；
出度（out-degree）：有多少条边指向某点就是该点的出度；
⼊度（in-degree）：从某点出发向外指向延伸的边数就是该点的⼊度；
图的存储
存储的关键是点集合和边集合；
邻接矩阵：顶点信息存储在⼀维数组中，边信息存储在⼆维数组中；
优点：很容易算出边邻接关系；以及节点的度（不管是出度还是⼊度）；
缺点：边集合存储空间复杂度⽐较⼤，图中⼤量0，空间利⽤率不⾼（尤其在点多边少的情况
下）；对于⽆向图，邻接矩阵是对称的，可以只存下半部分。
连接表：顶点集合依然存储在⼀维数组当中，边集合存储在连接表当中；
有向图
⽆向图
权重⽆向图
优点：很容易算出邻接关系；以及节点的出度；
缺点：很难算出⼊度，需要遍历整张表；可以同时建⽴⼀张逆连接表（相当于记录⼊度的
表）；
图的遍历
从图中某⼀个顶点出发，访问图中其余顶点，使每个顶点被访问⼀次且只被访问⼀次；
可以从图中任意⼀个顶点出发进⾏遍历；
需要解决的问题：
确定⼀条搜索路径；
确保每个顶点被访问到；
确保每个顶点只能被访问⼀次；
设置辅助数组visited，数组元素的初始值均为false，⼀旦遍历过就置为true；
深度优先搜索
应⽤：
检测连通分量的个数；
两个点是否在⼀个连通分量中；
检测是否构成环；从⼀个点出发能否回到出发点；
⼴度优先搜索
关键数据结构：
队列；
应⽤：
游戏中找寻路径问题；
迪杰斯特拉算法（dijkstra）
该算法主要解决最短路径问题，采⽤是贪⼼思想；
对象：权重图；
该算法核⼼思想是，每次从路径最短的点出发遍历相邻边，检测修改路径值（确保相邻点也是最
短），从未被确认路径最短的顶点集合中选择最短路径的点，将该点加⼊确认路径最短的顶点集
合，并将该点作为下次遍历相邻边的出发点；
核⼼步骤：更新，扫描，修改；
动态规划
0/1背包问题：给定n件物品，物品重量为w[i]，物品价值c[i]，背包能承受最⼤重量为V；问如何选
择物品放⼊背包，使得背包中物品的总价值最⼤？
暴⼒解法：尝试所有可能的物品组合，找出价值最⾼的组合；因为每⼀种物品都有选择和不选择的
可能，那么该算法的时间复杂度为
;
动态规划：先将问题拆分成⼩问题，再逐步解决⼤问题；
动态规划的必要步骤：画⽹格；从画⽹格中找出状态转移⽅程；
例⼦：背包可承受最⼤重量为7，物品的价值分别为（1，4，5，7），物品的重量分别为（1，3、4，5）。
推导：
0/1背包解释：0/1的意思是某物品要么不选择，要么只选择⼀次；
注意：
c为物品价值，w为物品重量，下⾯描述直接⽤字⺟来代替；
如上图：
蓝⾊区域为背包能承受的总重量；
绿⾊区域为不同的物品，描述了该物品的价值以及重量；
红⾊区域为纵坐标对应的背包承受重量下，纳⼊背包物品的总价值；
⻩⾊区域为背包承受重量为5的时候，此时可选物品为[c(1)w(1)],[c(4)w(3)],[c(5)w(4)]，
从这些物品中选择并纳⼊背包，此时背包的物品最⼤价值为6；
1. 从第⼆⾏[c(1)w(1)] 出发，只选择[c(1)w(1)] 物品，分别尝试选择承受重量为(1，2，
3，4，5，6，7)的背包；可知，背包价值只能为1，不管背包可承受的重量；
2. 从第三⾏[c(4)w(3)] 出发，此时可选择[c(1)w(1)],[c(4)w(3)] 两件物品，分别尝试选
择承受重量为(1，2，3，4，5，6，7) 的背包；背包承受重量⼩于3时，跟相邻上⼀格⼀致，因为
只能选择[c(1)w(1)] 物品；背包承受重量为3时，此时可以选择[c(4)w(3)] 物品；当背包承受
重量⼤于3时，此时可以同时选择两件物品，所以后⾯都为5；
3. 从第四⾏[c(5)w(4)] 出发，此时可选择[c(1)w(1)],[c(4)w(3)],[c(5)w(4)] 三件物 品，分别尝试选择承受重量为 (1，2，3，4，5，6，7) 的背包；背包承受重量⼩于4时，跟相邻上 ⼀格⼀致；当背包承受重量等于4时，此时多了⼀种选择；（重点来了）如果不选择[c(5)w(4)] 那 么选择相邻上⼀格，值为5；如果选择[c(5)w(4)]，那么此时价值为5，背包可承受重量为4- 4=0，那么此时背包最⼤价值为5；可以看出都是5。往后背包可承受重量为5，如果不选择，相邻上 ⼀格价值为5；如果选择，背包剩余重量为1，还可以选择[c(1)w(1)] 物品；那么此时背包总价值 为 5+1=6 。再往后⼀格，此时背包重量6；如果不选择，跟相邻上⼀格⼀致；如果选择，背包剩余重 量为2，只能选择[c(1)w(1)] 物品，此时背包只能还有重量为1的剩余，但是不能选择任何物品 了。再往后⼀格，此时背包重量7；如果不选择，相邻上⼀格价值为5；如果选择，背包剩余重量为3， ⽽之前已经计算，背包重量为3的最⼤价值为4，所以此时背包价值总和为5（已选择）+4 = 9； 4. 最后⼀⾏与前⾯推导⼀致，我们强调最后⼀格的选择；如果不选择[c(7)w(5)]，那么最⼤价值 为相邻上⼀格，此时背包最⼤价值为9；如果选择[[c(7)w(5)]]，背包剩余重量为7-5=2；⽽之前 已经算出背包重量为2时，最⼤价值为1，所以此时背包最⼤价值为7+1 = 8；显然不选择
[c(7)w(5)] 物品时，背包价值最⾼为9；
状态转移⽅程：
dp[i][k] = max(c[i] + dp[i-1][k-w[i]], dp[i-1][k]);
