DFS

DFS 基础

栈搜索

运行时栈：栈里的是仍在运行的

入栈：函数开始运行

出栈：函数运行结束

DFS 步骤

1. 出栈：函数被调用

2. 捕捉：全局变量捕捉target值

   出队的时候进行目标点的捕捉，如果是目标点就返回，不再继续扩展

3. 扩展

4. 入栈

先序遍历

从已知点开始出发

（写法在本质上与BFS非常相似，可以直接bfs代码将queue改成stack得到）

后序遍历

从未知点开始出发

如果需要求拓扑排序的话，只需要在dp[i] = dfs(i - 1) + dfs(i - 2)后面一行加上topo.add(i)即可，因为这里是后续，dp[i]依赖的边已经访问完了

（本质上还是拓扑排序）

中序遍历

仅存在于二叉树中，且仅在二叉搜索树上有意义，其他情况下没有实际意义

DFS 相对于 BFS 的优势

• 后序传值（DFS没有后序）

• 先序回溯（BFS不能回溯）

• 宽树搜索：

  典型如 IDA*

  如果每层扩展的状态很多，BFS需要把当前层所有状态存在队列，负担很大，DFS只需要存一条路径的在栈中，所以需要的内存很小

递归

Quine，即一个能够打印出自身源代码的程序。

s = 's = %r\nprint(s%%s)'
print(s%s)

首先，将代码本身赋值给变量s，使用%r来表示s的原始字符串形式，包括引号和转义字符。

最后，通过print(s%s)来打印出变量s中的内容，即代码本身。

1. s = %r\nprint(s%%s):

   • %r是Python中的字符串格式化操作符，用于表示将变量以repr()的形式插入到字符串中。
   • \n表示换行符。
   • %%用于在字符串中插入一个百分号%。第一个%负责转译
   • 因此，s = %r\nprint(s%%s)将会被格式化为一个字符串，其中%r会被替换为s的原始字符串形式，然后再加上换行符和print(s%s)这段代码。

2. print(s%s):

   • s表示要打印的字符串，即变量s中的内容。
   • %s是字符串格式化操作符，用于将一个字符串插入到另一个字符串中。
   • 因此，print(s%s)会打印出变量s中的内容，即代码本身。

这里使用了字符串的格式化操作符%来实现字符串的格式化和插值。

---

Java Quine

public class Quine {
    public static void main(String[] args) {
        String s = "public class Quine {%n    public static void main(String[] args) {%n        String s = %c%s%c;%n        System.out.printf(s, 34, s, 34);%n    }%n}";
        System.out.printf(s, 34, s, 34);
    }
}

34是ASCII中的"