JavaScript - 图的算法

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

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

图的类型

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

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

图的表示

图的表示方法有两种:

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

图算法

当我们谈论图算法时，有很多可用的算法。我们主要使用这些算法来解决图问题。我们在下面列出了其中一些:

• 广度优先搜索 (BFS)
• 深度优先搜索 (DFS)
• 拓扑排序

广度优先搜索 (BFS) 算法

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

算法

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

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

实现

以下是 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); // Process the node
         visited[node] = true;
      }

      // Ensure neighbours is defined
      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):

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

实现

以下是 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 之前。

算法

我们可以使用以下步骤实现拓扑排序:

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

实现

以下是拓扑排序算法在 JavaScript 中的实现:

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], // Node 0 -> 1, 2
   [3],    // Node 1 -> 3
   [3, 4], // Node 2 -> 3, 4
   [],     // Node 3 -> No outgoing edges
   [5],    // Node 4 -> 5
   []      // Node 5 -> No outgoing edges
];
topologicalSort(graph);

输出

以下是上述代码的输出

0
1
2
3
4
5
6
7
8