javascript - 在自定义数据结构上查找 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. 使用简单 breadth-first-search寻找路径

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

请注意，我了解您输入的内容以形成 directed graph .相反，如果它是一个无向图，则可以稍微简化解决方案。