日撸 Java 三百行（40 天: 过去十天总结)

注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明

目录

前言

1.图的抽象与表示

2.不局限与图的关键工具——DFS与BFS

3.结构的深化，从邻接表到十字链表

4.图中的那些贪心思想

5.贪心之处暗藏堆优化

6.同内核方法之间的迁移性：Prim与Dijkstra

7.数据结构的一脉相承

8.信息标记与集合

9.信息标记与去重和删除

10.图示表示的重要性

前言

        第39天去哪了呢？第39天是关键路径的讲解，这部分内容我们在刚开始的特别训练中有所讲解，大家可以在这里跳转：

日撸 Java 三百行（特殊训练：关键路径）_LTA_ALBlack的博客-CSDN博客_求关键路径java这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明https://blog.csdn.net/qq_30016869/article/details/123306868

        今天我们简单聊聊过去十天写博客，了解图这部分知识的一些感想。

1.图的抽象与表示

         数据结构的图论这部分是数据结构中最抽象的部分，因此，在第一次学习的时候就要在脑中建立一个存储结构到现实中的图中的映像才可以，相对应的，通过图中的映像能够构建出来其计算机存储也很关键。

        试着充分去理解图的几种关键的存储表示：邻接表、邻接矩阵，并且能通过这些存储结构推出原始的图逻辑结构的特性，比如我们在讲解图的连通性那部分就利用邻接矩阵的矩阵计算推导出图的连通特性。要明白图与其数据结构都具有可研究的特性。

2.不仅仅局限于图的关键工具——DFS与BFS

        不要认为DFS与BFS仅仅是图的附带工具，必须要时刻灵活对待这两大庞然大物。它们在许多非图的逻辑问题中都具有非常关键的工具，DFS是暴力算法的代名词；是实现递归的最常见套路；是串联复杂数据结构最普遍的思路。动态规划可以用DFS的记忆化搜索来完成，线性结构也可以用DFS完成暴力枚举（比如求子集等操作），二叉树、树、森林也可以DFS。 BFS是很多最短路径的启发点，是实现它们的跳板。从BFS实现无权的单源最短路径问题开始，逐步影响到后来的Dijkstra单源最短路径算法和Prim最小生成树算法思想。其队列的想法被Richard Bellman与Ford发现从而提出了解决负权最短路径问题的Bellman-Ford算法。

        DFS与BFS的这种灵活的使用从某种意义上也与许多问题都可以表示为抽象的图相关的多对多关系有关，比如我们提到的DFS暴力枚举，其实很多暴力枚举问题都可以抽象为结点彼此相连的图的结构。比如第35天的涂色问题。

3.结构的深化，从邻接表到十字链表

        虽然我们在实际案例中很少用到十字链表，但是通过邻接表到十字链表的改进还是非常有意义的，它启发与邻接表关于入边的不足，同时结合了入边邻接表+出边邻接表，避免了冗余。这种对初始数据结构的改进而扩充原本特性的思路是非常有用的，它是灵活运用数据结构并自定义出一个符合自身所需的数据结构的关键。

4.图中的那些贪心思想

        我们在讲述Huffman那部分初步提到了贪心思想，而后续在Dijkstra与Prim处陆续提到了全新的贪心方案。可见，贪心的解释虽然简单：“每步追求局部的最优解直到求到最后一个解”，但是实际在算法的设计过程中要明白从何处贪心？以什么因素为贪心的权？贪心是否能作用于当前的问题，可否保证局部的最优解能构成全局最优。这些问题导致部分贪心问题的隐蔽性。

        虽然贪心是三大算法最简单的，但是又因为其可渗透之深入，万物之可贪，所以它的部分算法又是最难找准切入，需要你去细细观察。

5.贪心之处暗藏堆优化

        我们几次遇见贪心，几次都讨论了一种优化思路：堆优化。为什么呢？

        其实这是由对本身的特性决定的，堆具有非常优良自身维护的特性与本身树形构造的特点决定了其总能确定以\(O(logN)\)的复杂度维护自身以保证堆顶元素的极值特性。这种特性使我们在确定集合内取出极值信息的复杂度由传统的线性\(O(N)\)算法提升到\(O(logN)\)。而集合取极值正好是贪心的核心思想，因为极值具有鲜明的区域最优性，符合贪心要求的局部最优解。

6.同内核方法之间的迁移性：Prim与Dijkstra

        我很长时间其实也是把最短路径问题和MST（最小生成树）问题分开来看的，知道再考研期间重学这两个问题时我才细细发现了其中的相似特性。在曾经的我看来，MST问题不过就是通过Kruskal和Prim维持的图的树形问题体系，包括并查集等一系列寻共同根问题，从来没有尝试与短路径问题的体系建立过联系。但是我发现我认知还是过于浅显了。

         MST问题中采用的Prim算法，采用的数组表征树形的结点集合，并且通过集合与外界逐步的贪心（边最短原则）扩展。Dijkstra算法中，采用数组表征源点可达的最短顶点集合，通过逐步地向外集合的贪心（松弛原则）扩展来逐步扩大此集合的占比。仔细对比可以发现方法都采用相同的集合贪心扩展的思想，唯一的不同就仅仅有贪心原则的差异性。这两个算法的正式提出都集中在计算机基础算法爆发的上个世纪50年代（Prim最早在30年代有类似的发现，但是当时计算机还未成体系），可见，优秀的算法总是能提供比算法本身更加重要的内核去影响其他类似领域的研究。

7.数据结构的一脉相承

        其实在学习过程中我们能发现一个非常有趣的地方，只要你细细想：线性结构的在应用领域的两架马车——栈与队列；图结构作为工具应用的两面——DFS与BFS。DFS通过栈实现回溯结点的暂存于不顾一切埋头向下的深度，BFS通过队列来暂存一系列的当前层次的结点从而为BFS保证了层次的连续，所以巧合得来看，图的两大工具刚好分别继承于线性结构在应用邻域的两大受限线性结构。这也许不是一种巧合，再庞大的数据结构算法究其本质总是从那些基础的结构延展开来并逐步深化的。而这些DFS与BFS又构成了其他大型算法的思路和若干个微小的分支，可见，数据结构总是一脉相承的。

8.信息标记与集合

        在图这部分，我们接触了利用集合来推进的一些算法，比如在Dijkstra算法中我们初步采用dist[ ]数组来模拟了源点分支而出最短路径顶点集合。但是若在顺序表中利用传统的\(O(N)\)删除与添加元素来模拟集合无序地\(O(1)\)添加和删除元素似乎不是很方便，因此我们额外采用了一个boolean数组来进行标记删除。这就像个掩码一样屏蔽掉无关的干扰信息，说明了数据的存在性情况。

9.信息标记与去重和删除

        信息标记这种方法还在去重与删除方面有一定运用。在递归的DFS中，标记法可以防止元素的重复访问的作用；在传统哈希表的除留余数法中，采用线性探测查询关键字时为了避免因为截断查询路径导致关键字丢失的现象，我们往往采用标记删除法；虽然这种方法存在冗余，但是对于某些静态方案中确实有着至关重要节省开销的效益，比如邻接矩阵的结点删除中使用额外的信息数组来说明无效的结点也是一种可取的办法。

        这种类似的删除方法还有更高级的运用，比如，我们可以放弃boolean数组而采用更高级有效信息数组，来直接存储结点的更多有意义的信息从而辅助问题的解决。这类问题可能往往一次的遍历无法考虑全局的信息，这时我们可以采用标记数组来记录本次的局部最优解。从而在下次遍历时利用这些数组记录来为新回合的最优解求解提供辅助信息，更进一步推导新回合的最优局部最优解，具体的例子可见39日的关键路径等方法。总结来看，使用信息标记数组记录某次的信息是迭代DP的一种基本的启发式方法。

        此外，关于去重还有个高级用法。我们还可以改变标记数组的维数，从而以不同维度分摊不同的信息从而扩大标记的含义，相当于构成一个简易的多维哈希。这里常见的例题有八皇后问题的巧解，这里我贴出一个我在leetcode写的一个关于此问题采用此方法的解法：

力扣https://leetcode-cn.com/problems/n-queens-ii/solution/cai-yong-flaglai-biao-ji-20xing-zuo-you-by-alblack/

10.图示表示的重要性

        在学习计算机的算法的过程中，随着算法的深入，我们发现我们作图的环境越来越多了。可以发现，若这几日的图学习（包括前几周学习树相关内容）时缺乏了画图的辅助，那么代码分析将会寸步难行。特别是在最短路径和关键路径这些极端依靠图的信息关系而驱动的问题中，图成为解决问题的关键。有时候，我们花费最多的时间可能不是在写代码，而是盯着那些画出的图结构反复琢磨。也许也只有真正学习计算机的人才懂得一个道理：所谓的“程序员”或者“计算机研究者”并不是时时刻刻都在敲代码的一群人，而是时刻会盯着电脑和图纸发呆的一群人。