N 元树的 DFS (无环图) 表示为邻接表

引言

在本文中，我们将解释N叉树（有向无环图）的邻接表表示的DFS。在了解这个主题之前，我们需要先了解DFS。

什么是DFS？

DFS的全称是Depth First Search（深度优先搜索）。通过深度优先搜索，我们可以三种方式遍历树。分别是：前序、中序和后序。当一个图不包含环时，这种图被称为有向无环图。当我们连接多个有向无环图时，我们称之为树。当存在可能不连通的有向无环图时，则称为森林。

让我们开始文章。

N叉树的DFS

在解决问题之前，让我们先了解一下什么是N叉树。有向无环图的另一个名称是N叉树。但有向无环图和N叉树之间有一个区别。区别在于，当树有多个节点时，称为N叉树。当需要非线性数据结构，并且我们想创建自己的数据结构时，我们就需要借助N叉树。

N叉树是二叉树的一个子集，它在顶部有一个节点作为根节点。

树有多个子节点。要遍历所有节点非常困难。现在，我们将举一个例子来解决这个问题。

示例

从下面的N叉树，我们需要使用深度优先搜索找出树的最大深度。

上面N叉树的图形表示如下：

图的遍历方式如下：

A -> B -> D -> E -> H -> I -> J -> K -> C -> F -> G

算法

我们需要通过前序遍历方法来解决上述问题。在这种方法中，我们必须从根节点开始遍历，然后按顺序向下遍历子树根节点及其子节点。要解决这个问题，我们需要按照以下步骤进行。

步骤 1

首先，我们必须从根节点开始。

步骤 2

然后，我们必须递归地移动到左子树。

步骤 3

然后，我们必须递归地移动到右子树。

步骤 4

我们必须一直这样做，直到遍历完所有节点。

如果我们提供输入

那么我们会得到如下输出：

A B C D E

我们来做编程部分。

C++ 中的实现

代码

输出

说明

在上面的代码中，我们用C++实现了逻辑，以执行前序遍历方法并解决DFS问题。

Java 实现

代码

输出

说明

在上面的代码中，我们用Java实现了逻辑，以执行前序遍历方法并解决DFS问题。

复杂度分析

时间复杂度

N叉树的遍历时间复杂度为O(V + E)。

原因

在N叉树中，遍历整个树需要花费大量时间。因此，时间复杂度为如此之高。

空间复杂度

N叉树的遍历空间复杂度为O(V)。其中V代表顶点数。