DFS逻辑不变

Question

老师好，本节课基于邻接矩阵的DFS，惊艳到我了。真没想到，DFS的主要逻辑不用改变，不管是邻接矩阵还是邻接表。最关键的还是实现了adj()方法，也就是实现了求邻接顶点的方法，复用了这个方法，居然可以不修改DFS的逻辑。之前我总是把图的表示和图的算法，搅和到一起，总是觉得理不清，过一段时间就忘记了。现在看，您这个先封装图类，再封装各个算法类，让两个类组合，设计方式也是很巧妙。这些背后的框架逻辑，真是令人叹为观止。不知道这方面的内功平时该怎么修炼。

Answer 1

liuyubobobo 2025-01-06 03:31:14

其实这种所谓的“框架逻辑”不是算法学习的重点，甚至在有的时候会让算法学习“失焦”。如果不使用这种框架，面对不同的图表示，就无法实现出正确的 dfs，说明对 dfs 的理解是不透彻的。我倒是建议将这一点作为一个练习，来看自己是不是真的理解了图的 dfs。不使用课程中的图的类，直接使用一个二维数组或者数组链表作为图的表示，看自己能否正确实现 dfs。leetcode 上有大量 dfs 相关的练习，也可以作为训练素材。

使用这种“框架”其实是进一步的学习，是对算法的框架封装。在大学计算机的课程体系中，这种框架或者软件工程的方式，不管是国内外，都是更进一步高年级计算机专业的学习内容。如果你以后有机会不仅仅是实现算法，还要封装算法供别人使用，这类思想将至关重要。

继续加油！：）