在 JavaScript 中根据自定义数据结构查找两个节点之间的路径

Question

您好，我有一个连接数组，如下所示：

var connections =[

    {
      "source": "l1",
      "target": "l2"
    },
    {
      "source": "l2",
      "target": "l4"
    },
    {
      "source": "l2",
      "target": "l3"
    },
    {
      "source": "l4",
      "target": "l5"
    },   

]

它继续源和目标。现在想要使用某些函数找到两个节点之间的路径。假设函数findConnections("l2", "l5")将返回如下所示的数组

var answer =[

        {
          "source": "l2",
          "target": "l4"
        },
        {
          "source": "l4",
          "target": "l5"
        }, 
]

我不知道如何才能实现这一目标？我尝试了简单的 JavaScript 但失败了。我认为使用underscore.js或lodash.js我们可以实现这一点？如果有人提供解决方案或给出提示，这真的会有帮助吗？

Answer 1

我参加聚会有点晚了，但这里有一个简单的解决方案：

1. 从给定的边构建一个图：

   

2. 使用简单的广度优先搜索来查找路径

const addNode = (graph, node) => {
  graph.set(node, {in: new Set(), out: new Set()});
};

const connectNodes = (graph, source, target) => {
  graph.get(source).out.add(target);
  graph.get(target).in.add(source);
};

const buildGraphFromEdges = (edges) => edges.reduce(
  (graph, {source, target}) => {
    if (!graph.has(source)) {
      addNode(graph, source);
    }

    if (!graph.has(target)) {
      addNode(graph, target);
    }

    connectNodes(graph, source, target);

    return graph;
  },
  new Map()
);

const buildPath = (target, path) => {
  const result = [];

  while (path.has(target)) {
    const source = path.get(target);
    result.push({source, target});
    target = source;
  }

  return result.reverse();
};

const findPath = (source, target, graph) => {
  if (!graph.has(source)) {
    throw new Error('Unknown source.');
  }

  if (!graph.has(target)) {
    throw new Error('Unknown target.');
  }

  const queue = [source];
  const visited = new Set();
  const path = new Map();

  while (queue.length > 0) {
    const start = queue.shift();

    if (start === target) {
      return buildPath(start, path);
    }

    for (const next of graph.get(start).out) {
      if (visited.has(next)) {
        continue;
      }

      if (!queue.includes(next)) {
        path.set(next, start);
        queue.push(next);
      }
    }

    visited.add(start);
  }

  return null;
};

//  A --* B
//      / | \
//     *  |  *
//    C   |   D --* E
//     \  |  /     *
//      * * *     /
//        F------/

const graph = buildGraphFromEdges([
  { source: 'A', target: 'B' },
  { source: 'B', target: 'C' },
  { source: 'B', target: 'D' },
  { source: 'B', target: 'F' },
  { source: 'C', target: 'F' },
  { source: 'D', target: 'E' },
  { source: 'D', target: 'F' },
  { source: 'F', target: 'E' },
]);

console.log('A -> A', findPath('A', 'A', graph)); // []
console.log('A -> F', findPath('A', 'F', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'F'}]
console.log('A -> E', findPath('A', 'E', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'D'}, {source: 'D', target: 'E'}]
console.log('E -> A', findPath('E', 'A', graph)); // null

请注意，我理解您的输入以形成有向图。如果它是一个无向图，那么解决方案可以稍微简化一些。