🥳每日一练-BFS算法求最短路径-JS简易版

思想

找最短路径的过程用到了图的广度优先遍历 BFS，每次往下遍历一层，表示遍历到的节点距离开始节点就多一。循环遍历，直到遍历完所有的节点

下面开始

准备数据

这个图来自王道考研的数据结构视频课程中的截图。B 站可搜王道考研数据结构

准备一个描述上面👆无向图的数据结构，并用邻接表的方式表示

/**@type {number[]} */
let graphNodes = Array(9)
    .fill(0)
    .map((item, index) => index);

/**@type {number[][]} */
const graphEdges = {
    1: [2, 5],
    2: [6],
    6: [3, 7],
    3: [7, 4],
    7: [4, 8],
    4: [8],
};

/**
*
* @param {number[]} graphNodes
* @param {number[][]} graphEdges
* @returns {nodeType[]}
*/
const generateGraph = (graphNodes, graphEdges) => {
    // 将 graphNodes 数组转换为节点对象数组
    graphNodes = graphNodes.map((item, index) => {
        const tempNode = { value: index, next: null };
        return tempNode;
    });

    // 定义 addNode 函数，用于在图的 fromNode 和 toNode 之间添加一条边
    const addNode = (graph, fromNode, toNode) => {
        // 如果 fromNode 和 toNode 之间已经存在边，则不添加
        let currentNode = graph[fromNode];
        while (currentNode.next) {
            if (currentNode.next.value == toNode) return;
            currentNode = currentNode.next;
        }
        currentNode.next = { value: toNode, next: null };

        // 如果 toNode 和 fromNode 之间已经存在边，则不添加
        currentNode = graph[toNode];
        while (currentNode.next) {
            currentNode = currentNode.next;
        }
        currentNode.next = { value: fromNode, next: null };
    };

    // 遍历 graphEdges 对象的键值对，将每个键值对传递给 addNode 函数
    Object.entries(graphEdges).map(([value, edges]) => {
        edges.map((toNode) => {
            addNode(graphNodes, value, toNode);
        });
    });

    // 返回生成的无向图
    return graphNodes;
};

// 调用 generateGraph 函数，生成无向图
const graph = generateGraph(graphNodes, graphEdges);

• 首先，创建一个长度为 9 的空数组 graphNodes，用来表示无向图的节点集合
• 创建一个对象 graphEdges，其中键是节点值，值是该节点指向的节点值数组。例如，{ 1: [2, 5], 2: [6], ... } 表示节点 1 指向节点 2 和 5，节点 2 指向节点 6，以此类推。
• 定义 generateGraph 函数，该函数接收两个参数：graphNodes 和 graphEdges。其中使用 graphNodes.map() 方法创建一个新的数组 graphNodes，其中每个元素都是一个包含 value 和 next 属性的对象。value 属性表示节点的值，next 属性表示下一个节点。
• 定义 addNode 函数，该函数接收三个参数：graph、fromNode 和 toNode。该函数用于在图的 fromNode 和 toNode 之间添加一条边。
• 使用 Object.entries() 方法遍历 graphEdges 对象的键值对，并使用 map() 方法将每个键值对传递给 addNode 函数。
• 最后，调用 generateGraph() 函数，并将结果赋值给 graph 变量。

最后生成的数据就是表示图的邻接表

具体结构如下：

因图中的节点只有序号 1，所以邻接表节点从下标 1 开始，下标 0 废弃不用

[
  {
    value: 0,
    next: null,
  },
  {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 5,
        next: null,
      },
    },
  },
  {
    value: 2,
    next: {
      value: "1",
      next: {
        value: 6,
        next: null,
      },
    },
  },
  {
    value: 3,
    next: {
      value: 7,
      next: {
        value: 4,
        next: {
          value: "6",
          next: null,
        },
      },
    },
  },
  {
    value: 4,
    next: {
      value: "3",
      next: {
        value: 8,
        next: {
          value: "7",
          next: null,
        },
      },
    },
  },
  {
    value: 5,
    next: {
      value: "1",
      next: null,
    },
  },
  {
    value: 6,
    next: {
      value: "2",
      next: {
        value: 3,
        next: {
          value: 7,
          next: null,
        },
      },
    },
  },
  {
    value: 7,
    next: {
      value: "3",
      next: {
        value: "6",
        next: {
          value: 4,
          next: {
            value: 8,
            next: null,
          },
        },
      },
    },
  },
  {
    value: 8,
    next: {
      value: "4",
      next: {
        value: "7",
        next: null,
      },
    },
  },
]

BFS 求最短路径

const findPathBFS = (graph, startNode) => {
    // 定义四个数组：pathPower、beforeNode、isVisited 和 queue
    const pathPower = Array(9).fill(-1);
    const beforeNode = Array(9).fill(-1);
    const isVisited = Array(9).fill(false);
    const queue = [];

    // 将起始节点添加到队列中，并将 isVisited 数组中该节点的值设置为 true
    queue.push(startNode);
    isVisited[startNode] = true;
    pathPower[startNode] = 0;

    // 使用一个 while 循环来遍历队列中的节点
    while (queue.length !== 0) {
        // 从队列中弹出一个节点 currentNode
        const currentNode = queue.pop();

        // 遍历当前节点的所有下一个节点 node
        for (let node = graph[currentNode].next; node !== null; node = node.next) {
            // 如果该节点未被访问过
            if (isVisited[node.value] === false) {
                // 将路径权重设置为当前节点的路径权重加 1
                pathPower[node.value] = pathPower[currentNode] + 1;
                // 将前一个节点设置为当前节点
                beforeNode[node.value] = currentNode;
                // 将 isVisited 数组中该节点的值设置为 true
                isVisited[node.value] = true;
                // 将该节点添加到队列中
                queue.push(node.value);
            }
        }
    }

    // 返回包含两个元素的数组：pathPower 和 beforeNode
    return { pathPower, beforeNode };
};

思想：

找最短路径的过程用到了图的广度优先遍历 BFS，每次往下遍历一层，表示遍历到的节点距离开始节点就多一。循环遍历，直到遍历完所有的节点

详细解释：

1. 定义四个数组：pathPower、beforeNode、isVisited 和 queue。pathPower 数组用于存储每个节点的到初始节点的距离，beforeNode 数组用于存储每个节点的前一个节点，isVisited 数组用于记录每个节点是否已被访问过，queue 数组用于存储待访问的节点。
2. 将起始节点 startNode 添加到队列 queue 中，并将 isVisited 数组中该节点的值设置为 true，表示该节点已被访问过。
3. 使用一个 while 循环来遍历队列中的节点。在每次循环中，从队列中弹出一个节点 currentNode，并将其作为当前节点。
4. 遍历当前节点的所有邻接 node，并检查它们是否未被访问过。如果是，则将路径权重设置为当前节点的路径权重加 1，并将该节点添加到队列中，并将 isVisited 数组中该节点的值设置为 true。
5. 重复步骤 3 和 4，直到队列为空。
6. 最后，findPathBFS 函数返回一个包含两个元素的数组，第一个元素是 pathPower 数组，第二个元素是 beforeNode 数组。

执行代码：

const pathRes = findPathBFS(graph, 2);
console.log(pathRes);
// {
//   pathPower: [ -1, 1, 0, 2, 3, 2, 1, 2, 3 ],
//   beforeNode: [ -1,  2, -1, 6, 7, 1, 2, 6, 7 ]
// }

输出结果是两个数组，一个数组代表每个节点的到初始节点的距离，另一个数组用于存储每个节点的前一个节点

具体来说，pathPower 数组中的值表示从节点 2 到每个节点的路径长度。对于节点 2，长度为 0，因为它是起始节点，没有更短的路径。对于节点 3，权重为 2，因为从节点 2 到节点 3 的路径长度为 1（即从节点 2 直接到节点 3）。对于节点 6，权重为 1，因为从节点 2 到节点 6 的路径长度为 2（即从节点 2 到节点 6 的路径需要经过节点 3）。

beforeNode 数组中的值表示每个节点的前一个节点。对于节点 2，没有前一个节点，所以值为 -1。对于节点 3，前一个节点是节点 2，所以值为 2。对于节点 6，前一个节点是节点 7，所以值为 7。

const pathRes2 = findPathBFS(graph, 3);
console.log(pathRes2);
// {
//   pathPower: [ -1, 3, 2, 0, 1, 4, 1, 1, 2],
//   beforeNode: [ -1, 2, 6, -1, 3, 1, 3, 3, 4 ]
// }

这个输出结果是从节点 3 开始的，大家可以自己找找从开始节点到节点 7 的路径，或者到节点 4 的路径

相信大家肯定发现了💇，虽然数组中已经包含了最短路径所需要的全部信息，但是我们来人工读取，还是很不方便的。所以可以再写一个函数，帮助我们读取这两个数组

打印出开始节点到某个节点的路径

const getShortestPath = (pathPower, beforeNode, node) => {
  // 创建一个空数组 path
  const path = [];

  // 获取 node 的最短路径长度 shortestLen
  const shortestLen = pathPower[node];

  // 使用 while 循环遍历从 node 到起始节点的路径
  while (beforeNode[node] !== -1) {
    // 将当前节点添加到 path 数组的头部
    path.unshift(node);

    // 将 node 设置为前一个节点
    node = beforeNode[node];
  }

  // 将起始节点添加到 path 数组的头部
  path.unshift(node);

  // 输出 node 的最短路径长度和路径
  console.log("the shortest length is :", shortestLen);
  console.log("the shortest path is :", path);
};

getShortestPath 函数首先创建一个名为 path 的空数组。然后，使用一个 while 循环来遍历从 node 到起始节点的路径，直到找到一个节点 node，它没有前一个节点（即前一个节点为 -1）。没有前一个节点就说明找到了起始节点，要结束寻找了

在每次迭代中，将当前节点 node 添加到 path 数组的头部，并将前一个节点设置为当前节点的前一个节点。最后，将起始节点添加到 path 数组的头部。

接下来，输出最短路径的长度和路径。在这里，我们使用 pathPower[node] 获取 node 的路径长度，并将其输出。然后，使用 path 数组输出最短路径。

// 输出起始节点 7 的最短路径长度和路径
getShortestPath(pathRes.pathPower, pathRes.beforeNode, 7);
// the shortest length is : 2
// the shortest path is : [ 2, 6, 7 ]

// 输出起始节点 8 的最短路径长度和路径
getShortestPath(pathRes.pathPower, pathRes.beforeNode, 8);
// the shortest length is : 3
// the shortest path is : [ 2, 6, 7, 8 ]

大家可以对照着图片来看，结果那是相当正确

总结

这篇文章分享了如何用 JS 代码实现 BFS 求最短路径。本文代码清晰，注释详细，解释也很到位，相信大家学习起来肯定很简单。

之前在大学学的时候，不明觉厉，现在用代码实现一遍，发现还是很简单的。

下篇文章分享用 JS 代码实现 dijkstra 算法求有权图的最短路径，关注一下叭