DFS 扫描一个完整的图
DFS scan on a completed graph
我有一些有趣的问题想得到你的帮助：
假设我有一个具有 n(n-1)/2 条边的图（数据结构），这意味着完整的图。
我可以从图中某个随机元素的一次 DFS 扫描中得到多少种可能的不同 DFS 树？
你的问题很有趣。我相信您正在谈论具有 n 个顶点和 n(n-1)/2 个顶点的完整图。
如果我们从任何顶点开始深度优先搜索 (DFS)，它最终将恰好访问 n 个顶点。在 DFS 中，我们跟踪访问过的顶点，以便一旦访问它们就不会访问它们，因此只要 DFS 进行，传出选项就会减少。我们可以总结为：
- 共有n个选项可以选择第一个顶点。
- 因为已经访问了 1 个顶点，所以共有 n-1 个选项可以选择第二个顶点。
- 共有 n-2 个选项可以选择第三个顶点，因为已经访问了 2 个顶点。
共有n-3个选项可以选择第三个顶点，因为已经访问了3个顶点。
等等。 . .
只有1个选项可以选择第n个顶点
因此，我们可以从此类图中的 DFS 获得的不同可能的 DFS 树是：
Total ways = n*(n-1)*(n-2)*(n-3)*....*1
= n! ( n factorial )
实际上它不是树，而是给定完整图的节点列表。因此，问题是：图中的 n 个节点有多少排列？显然，答案是 n!.
我有一些有趣的问题想得到你的帮助：
假设我有一个具有 n(n-1)/2 条边的图（数据结构），这意味着完整的图。
我可以从图中某个随机元素的一次 DFS 扫描中得到多少种可能的不同 DFS 树？
你的问题很有趣。我相信您正在谈论具有 n 个顶点和 n(n-1)/2 个顶点的完整图。
如果我们从任何顶点开始深度优先搜索 (DFS)，它最终将恰好访问 n 个顶点。在 DFS 中，我们跟踪访问过的顶点，以便一旦访问它们就不会访问它们，因此只要 DFS 进行，传出选项就会减少。我们可以总结为：
- 共有n个选项可以选择第一个顶点。
- 因为已经访问了 1 个顶点，所以共有 n-1 个选项可以选择第二个顶点。
- 共有 n-2 个选项可以选择第三个顶点，因为已经访问了 2 个顶点。
共有n-3个选项可以选择第三个顶点，因为已经访问了3个顶点。
等等。 . .
只有1个选项可以选择第n个顶点
因此，我们可以从此类图中的 DFS 获得的不同可能的 DFS 树是：
Total ways = n*(n-1)*(n-2)*(n-3)*....*1
= n! ( n factorial )
实际上它不是树，而是给定完整图的节点列表。因此，问题是：图中的 n 个节点有多少排列？显然，答案是 n!.