给定两个节点，如何找出他们之间的所有路径？

Question

给定一个数组，数组描述是两个点之间的连接关系，给定两个点，需要找出两个点之间的所有“路径”，如何写这个算法？

数据结构如下，描绘图形如下：

//原始数据结构

let arr = [
    //第一条路径
    {source: 'node-1', target: 'node-2'},
    {source: 'node-2', target: 'node-5'},
    {source: 'node-5', target: 'node-6'},
    {source: 'node-6', target: 'node-8'},
    //第二条路径
    {source: 'node-5', target: 'node-7'},
    {source: 'node-7', target: 'node-8'},
    //第三条路径
    {source: 'node-1', target: 'node-3'},
    {source: 'node-3', target: 'node-4'},
    {source: 'node-4', target: 'node-7'},
]

现在假设给定两个节点：node1、node8，需要求出他们之间的所有路径，用二维数组表示：

返回结果如下：

let result = [
    //第一条路径
    [
        {source: 'node-1', target: 'node-2'},
        {source: 'node-2', target: 'node-5'},
        {source: 'node-5', target: 'node-6'},
        {source: 'node-6', target: 'node-8'},
    ],
    //第二条路径
    [
        {source: 'node-1', target: 'node-2'},
        {source: 'node-2', target: 'node-5'},
        {source: 'node-5', target: 'node-7'},
        {source: 'node-7', target: 'node-8'},
    ],
    //第三条路径
    [
        {source: 'node-1', target: 'node-3'},
        {source: 'node-3', target: 'node-4'},
        {source: 'node-4', target: 'node-7'},
        {source: 'node-7', target: 'node-8'},
    ]
]

Answer 1

let arr = [
    {source: 'node-1', target: 'node-2'},
    {source: 'node-2', target: 'node-5'},
    {source: 'node-5', target: 'node-6'},
    {source: 'node-6', target: 'node-8'},
    {source: 'node-5', target: 'node-7'},
    {source: 'node-7', target: 'node-8'},
    {source: 'node-1', target: 'node-3'},
    {source: 'node-3', target: 'node-4'},
    {source: 'node-4', target: 'node-7'},
];

// 查找所有从 start 到 end 的路径
function findAllPaths(graph, start, end) {
    let paths = []; // 存储所有路径
    let stack = [[start, []]]; // 使用栈进行深度优先搜索
    let adjacencyList = {}; // 邻接表

    // 构建邻接表
    for (let edge of graph) {
        if (!adjacencyList[edge.source]) {
            adjacencyList[edge.source] = [];
        }
        adjacencyList[edge.source].push(edge.target);
    }

    // 深度优先搜索
    while (stack.length > 0) {
        let [node, path] = stack.pop();
        path = path.concat(node); // 更新路径

        if (node === end) {
            paths.push(path); // 找到一条完整路径
        } else if (adjacencyList[node]) {
            for (let neighbor of adjacencyList[node]) {
                if (!path.includes(neighbor)) {
                    stack.push([neighbor, path]); // 继续搜索
                }
            }
        }
    }

    return paths;
}

// 将路径转换为边的形式
function convertPathsToEdges(paths) {
    return paths.map(path => {
        let edges = [];
        for (let i = 0; i < path.length - 1; i++) {
            edges.push({source: path[i], target: path[i + 1]});
        }
        return edges;
    });
}

let paths = findAllPaths(arr, 'node-1', 'node-8'); // 查找所有路径
let result = convertPathsToEdges(paths); // 转换为边的形式

console.log(result); // 输出结果

Answer 2

const arr = [
    { source: 'node-1', target: 'node-2' },
    { source: 'node-2', target: 'node-5' },
    { source: 'node-5', target: 'node-6' },
    { source: 'node-6', target: 'node-8' },

    { source: 'node-5', target: 'node-7' },
    { source: 'node-7', target: 'node-8' },

    { source: 'node-1', target: 'node-3' },
    { source: 'node-3', target: 'node-4' },
    { source: 'node-4', target: 'node-7' }
]

interface Node {
    name: string
    to: Set<Node>
}

const graph = new Map<string, Node>()

arr.forEach(({ source, target }) => {
    if (!graph.has(target))
        graph.set(target, {
            name: target,
            to: new Set()
        })
    if (!graph.has(source))
        graph.set(source, {
            name: source,
            to: new Set([graph.get(target)!])
        })
    else graph.get(source)?.to.add(graph.get(target)!)
})

function findPath(from: Node, to: Node): Node[][] {
    return from === to
        ? [[to]]
        : Array.from(from.to)
                .map(node => findPath(node, to))
                .flat()
                .map(path => [from, ...path])
}

const result = findPath(graph.get('node-1')!, graph.get('node-8')!).map(path =>
    path
        .slice(0, -1)
        .map((node, idx) => ({ source: node.name, target: path[idx + 1].name }))
)

console.log(result)