JavaScript - 图算法

图是一种由节点和边组成的数据结构。节点就是顶点，连接它们的线就是边。图是非线性数据结构。

JavaScript 中的图算法用于解决图相关问题。这些算法用于遍历图、寻找最短路径等。我们可以使用这些算法来解决寻找最短路径、寻找连通分量等问题。

图的类型

在深入本章之前，让我们先了解图的类型。

• 有向图 : 有向图是一种边具有方向的图。换句话说，我们可以称之为 Digraph。这些边可能是单向或双向，也可能有环。箭头用于表示边的方向。
• 无向图: 无向图与有向图完全相反，即图的边没有方向。我们也可以称之为简单图。
• 带权图: 带权图意味着图的边具有权重，即值。它帮助我们定义顶点之间的成本、距离等。
• 无权图: 无权图与带权图相反，即图的边没有任何权重。

图的表示

有两种方式表示图：

• 邻接矩阵: 在这种表示中，我们使用二维数组表示图。数组的元素为 0 或 1。如果两个顶点之间有边，则置为 1，否则为 0。
• 邻接表: 在这种表示中，我们使用链表数组表示图。数组的每个元素代表一个顶点，链表代表该顶点的边。

图算法

谈到图算法时，有很多算法可用。我们主要使用这些算法来解决图问题。下面列出了一些：

• Breadth First Search (BFS)
• Depth First Search (DFS)
• Topological Sorting

Breadth First Search (BFS) 算法

此算法可用于遍历图。它对于解决许多问题非常有用。在该算法中，我们从根节点开始遍历，然后逐层向下，遍历当前层的所有节点，然后移动到下一层。我们使用 queue 数据结构来实现此算法。

算法

我们可以使用以下步骤实现 BFS：

• 首先，创建一个 queue，并将根节点添加到 queue 中。
• 然后创建一个 visited 数组，并将根节点标记为已访问。
• 然后循环遍历 queue，直到它为空。
• 然后从 queue 中出队节点并打印它。
• 之后，获取出队节点的所有相邻节点，如果它们未被访问，则标记为已访问并入队。
• 重复上述步骤，直到 queue 为空。

实现

以下是 JavaScript 中 BFS 算法的实现：

function BFS(graph, root) {
   let visited = [];
   let queue = [];
   queue.push(root);

   while (queue.length > 0) {
      let node = queue.shift();

      if (!visited[node]) {
         console.log(node); // 处理节点
         visited[node] = true;
      }

      // 确保 neighbours 已定义
      const neighbours = graph[node] || [];
      for (let i = 0; i < neighbours.length; i++) {
         let neighbour = neighbours[i];
         if (!visited[neighbour]) {
            queue.push(neighbour);
         }
      }
   }
}

let graph = [[1, 2], [3, 4], [5], [6], [6], [7], [8], []];
BFS(graph, 0);

以上程序的输出如下 −

以上代码的输出如下

0
2
5
7
1
4
6
8
3

深度优先搜索 (DFS) 算法

类似于 BFS，该算法也用于遍历图，但方式不同。在该算法中，我们从根节点开始，然后移动到左子节点或右子节点，深入直到到达叶子节点，然后回溯并移动到下一个子节点。

算法

我们可以使用以下步骤来实现 DFS：

• 首先，我们需要创建一个 stack，并将根节点添加到 stack 中。
• 然后我们将创建一个 visited 数组，并将根节点标记为已访问。
• 然后循环遍历 stack，直到它为空。
• 然后从 stack 中弹出节点并打印它。
• 之后，获取弹出节点的所有相邻节点，如果它们未被访问，则将它们标记为已访问并推入 stack。
• 重复上述步骤直到 stack 为空。

实现

以下是 JavaScript 中 DFS 算法的实现：

function DFS(graph, root) {
   let visited = [];
   let stack = [];
   stack.push(root);

   while (stack.length > 0) {
      let node = stack.pop();
      if (!visited[node]) {
         console.log(node);
         visited[node] = true;
      }

      // 如果 graph[node] 未定义，则设置默认值
      const neighbours = graph[node] || [];
      for (let i = 0; i < neighbours.length; i++) {
         let neighbour = neighbours[i];
         if (!visited[neighbour]) {
            stack.push(neighbour);
         }
      }
   }
}

let graph = [[1, 2], [3, 4], [5], [6], [6], [7], [8], []];
DFS(graph, 0);

输出

以下是上述代码的输出

0
2
5
7
1
4
6
8

拓扑排序算法

使用该算法，我们可以将图的顶点排序，使得对于从顶点 u 到顶点 v 的每条边，u 在排序中出现在 v 之前。

算法

我们可以使用以下步骤来实现 Topological Sorting：

• 我们将创建一个 visited 数组，并将所有顶点标记为未访问。
• 然后，我们将创建一个 stack 来存储顶点。
• 然后我们将循环遍历所有顶点并调用递归函数。
• 然后我们将创建一个递归函数，并将当前节点标记为已访问。
• 然后我们将循环遍历当前节点的所有相邻节点，如果它们未被访问，则调用递归函数。
• 然后将当前节点推入 stack。
• 重复上述步骤直到所有顶点都被访问。
• 最后，打印 stack。

实现

以下是 JavaScript 中 Topological Sorting 算法的实现：

function topologicalSort(graph) {
   let visited = [];
   let stack = [];
   for (let i = 0; i < graph.length; i++) {
      if (!visited[i]) {
         topologicalSortUtil(graph, i, visited, stack);
      }
   }
   while (stack.length > 0) {
      console.log(stack.pop());
   }
}

function topologicalSortUtil(graph, node, visited, stack) {
   visited[node] = true;
   const neighbours = graph[node] || [];
   for (let i = 0; i < neighbours.length; i++) {
      let neighbour = neighbours[i];
      if (!visited[neighbour]) {
         topologicalSortUtil(graph, neighbour, visited, stack);
      }
   }
   stack.push(node);
}

// 有效的 DAG
let graph = [
   [1, 2], // 节点 0 -> 1, 2
   [3],    // 节点 1 -> 3
   [3, 4], // 节点 2 -> 3, 4
   [],     // 节点 3 -> 无出边
   [5],    // 节点 4 -> 5
   []      // 节点 5 -> 无出边
];
topologicalSort(graph);

输出

以下是上述代码的输出

5
4
3
2
1
0