匍匐在背景上； 地图应：德地图、百度地图(推荐最短路线、最短时间)； 社会分析：朋友推荐、垃圾宅邸分析、社会关系分析； 推荐，精准营销； 舆论控制、信息发布； 防止诈骗(诈骗和转账诈骗)； 计算物学：模拟分运动； 图的分类有向图
有向图
权重贴图
图的基本概念顶点集合(vex-set )上图s(vex ) ) a、) b、) c、) d、) e、) f ) }边集合) arc-set )上图s ) arc ) ) a 'e '、' d、' e、' e、' e、) 有向图包括出度和度； 出度(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 ]);