在图论中，最短路径问题是在图中找到两个顶点（或节点）之间路径的问题，使得其组成边的权重之和最小化。在这里，我们需要修改我们的添加边和添加有向方法，以允许也向边添加权重。让我们看看如何添加它-示例/**    * 在任一方向上添加 2 条具有相同权重的边    *    *             权重    * 节点1 节点2    *           ... 阅读更多

有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 UV，u 在排序中都出现在 v 之前。这仅在有向图中才有意义。在许多地方，拓扑排序都很有意义。例如，假设您正在遵循食谱，其中一些步骤必须才能进入下一步。但其中一些可以并行执行。类似地，在大学选择课程时，有一些先决条件 ... 阅读更多

DFS 在访问兄弟顶点之前访问子顶点；也就是说，它在探索其广度之前遍历任何特定路径的深度。在实现算法时，通常使用堆栈（通常是程序的调用堆栈通过递归）。以下是 DFS 的工作原理-访问相邻的未访问顶点。将其标记为已访问。显示它。将其压入堆栈。如果找不到相邻顶点，则从堆栈中弹出顶点。（它将从堆栈中弹出所有没有相邻顶点的顶点。）重复规则 1 和规则 2，直到堆栈为空。让我们 ... 阅读更多

BFS 在访问子顶点之前访问邻居顶点，并且在搜索过程中使用队列。以下是 BFS 的工作原理-访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。如果找不到相邻顶点，则从队列中删除第一个顶点。重复规则 1 和规则 2，直到队列为空。让我们来看一下 BFS 遍历如何工作的示例：步骤遍历描述1初始化队列。2我们首先访问 S（起始节点）并将其标记为已访问。3然后我们从 S 看到一个未访问的相邻节点。在本例中，我们有三个 ... 阅读更多

图遍历（也称为图搜索）是指访问（检查和/或更新）图中每个顶点的过程。此类遍历按访问顶点的顺序进行分类。

我们将创建一个支持权重和有向和无向类型的图类。这将使用邻接表实现。当我们转向更高级的概念时，图的权重和有向特性都将派上用场。邻接表是一个单独列表的数组 A。数组 Ai 的每个元素都是一个列表，其中包含与顶点 i 相邻的所有顶点。我们使用 2 个成员来定义它，节点和边。让我们通过定义我们的类和一些我们将用于添加节点和边的的方法来设置图类 ... 阅读更多

图是一组对象的图形表示，其中某些对象对通过链接连接。相互连接的对象由称为顶点的点表示，连接顶点的链接称为边。正式地，图是一对集合 (V, E)，其中 V 是顶点集，E 是连接顶点对的边集。查看以下图形-在上图中，V = {a, b, c, d, e} E = {ab, ac, bd, cd, de}术语数学图可以在数据中表示 ... 阅读更多

以下是 AVL 树类的完整实现-示例类 AVLTree {    构造函数() {       // 将根元素初始化为 null。       this.root = null;    }    getBalanceFactor(root) {       返回 this.getHeight(root.left) - this.getHeight(root.right);    }    getHeight(root) {       让高度 = 0;       如果 (root === null || typeof root == "undefined") {          高度 = -1;       } 否则 {          高度 = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;       }     ... 阅读更多

我们可以学习如何在 AVL 树中插入节点。AVL 树中的插入与 BST 相同，我们只需要在每次向下移动树时执行一个额外的步骤，称为平衡树。这需要计算我们之前已经看到的平衡因子。根据配置，我们需要调用适当的旋转方法。通过上述解释，这些方法非常直观。我们再次创建一个类方法和一个用于递归调用的辅助函数- 示例insert(data) {    让节点 = new this.Node(data);    // 检查树 ... 阅读更多

为了平衡自身，AVL 树可以执行以下四种旋转-左旋转右旋转左右旋转右左旋转前两种旋转是单旋转，后两种旋转是双旋转。要有一个不平衡的树，我们至少需要一个高度为 2 的树。有了这棵简单的树，让我们逐一了解它们。左旋转如果在右子树的右子树中插入节点时树变得不平衡，则我们执行一次左旋转-在我们的示例中，节点 A 变得不平衡，因为在右子树的 ... 阅读更多