考虑下图:

由以下数组结构表示:

$graph = array
(
    'a' => array(),
    'b' => array('a'),
    'c' => array('a', 'b'),
    'd' => array('a'),
    'e' => array('d'),
    'f' => array('a', 'b', 'c', 'd'),
    'g' => array('d'),
    'h' => array('c'),
    'i' => array('c', 'g'),
    'j' => array(),
);

找到从节点 X 到节点 Y 的所有路径(不仅仅是最短路径)的最有效算法是什么？没有重复节点？例如，从节点 C 到节点 A 的路径是:

C --> A
C --> B --> A
C --> F --> A
C --> F --> B --> A
C --> F --> D --> A
C --> I --> G --> D --> A

使用节点 X 的父节点查找所有路径(A 和 B，在节点 C<>) 是微不足道的，但我很难在后代/混合方向上遍历节点。

有人可以帮帮我吗？

更新:按照@JackManey 的建议，我尝试移植 IDDFS (迭代深化深度优先搜索)基于维基百科伪代码，这或多或少是我的代码的样子:

$graph = directed2Undirected($graph);

function IDDFS($root, $goal) {
    $depth = 0;

    while ($depth <= 2) { // 2 is hard-coded for now
        $result = DLS($root, $goal, $depth);

        if ($result !== false) {
            return $result;
        }

        $depth++;
    }
}

function DLS($node, $goal, $depth) {
    global $graph;

    if (($depth >= 0) && ($node == $goal)) {
        return $node;
    }

    else if ($depth > 0) {
        foreach (expand($node, $graph) as $child) {
            return DLS($child, $goal, $depth - 1);
        }
    }

    else {
        return false;
    }
}

下面是它使用的辅助函数:

function directed2Undirected($data) {
    foreach ($data as $key => $values) {
        foreach ($values as $value) {
            $data[$value][] = $key;
        }
    }

    return $data;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

    return array_unique(flatten(array_intersect_key($data, array_flip((array) $id))));
}

function flatten($data) {
    $result = array();

    if (is_array($data) === true) {
        foreach (new RecursiveIteratorIterator(new RecursiveArrayIterator($data)) as $value) {
            $result[] = $value;
        }
    }

    return $result;
}

调用上面的代码会产生奇怪或不完整的结果:

var_dump(IDDFS('c', 'a')); // a -- only 1 path?
var_dump(IDDFS('c', 'd')); // NULL -- can't find this path?!

我想我从伪代码中忽略了一些东西，但我不确定它是什么。

我也试过this DFS class这是在另一个问题中推荐的，虽然它似乎总能找到从节点 X 到节点 Y 的 一个 路径，但我无法让它返回所有路径(演示 C -> A 和 C -> D ) .

因为我不需要知道实际采用的路径，所以只需要有多少条路径需要n步数才能从节点 X 到达节点 Y，我想到了这个函数(使用上面的 directed2Undirected):

$graph = directed2Undirected($graph);

function Distance($node, $graph, $depth = 0) {
    $result = array();

    if (array_key_exists($node, $graph) === true) {
        $result = array_fill_keys(array_keys($graph), 0);

        foreach (expand($node, $graph, $depth - 1) as $child) {
            if (strcmp($node, $child) !== 0) {
                $result[$child] += $depth;
            }
        }

        $result[$node] = -1;
    }

    return $result;
}

function expand($id, $data, $depth = 0) {
    while (--$depth >= 0) {
        $id = flatten(array_intersect_key($data, array_flip((array) $id)));
    }

    // no array_unique() now!
    return flatten(array_intersect_key($data, array_flip((array) $id)));
}

对于 Distance('c', $graph, 0) , Distance('c', $graph, 1)和 Distance('c', $graph, 2)这会正确返回 C 和任何其他节点之间的距离总和。问题是，Distance('c', $graph, 3) ( and higher ) 它开始重复节点并返回错误的结果:

Array
(
    [a] => 12
    [b] => 9
    [c] => -1
    [d] => 9
    [e] => 3
    [f] => 12
    [g] => 3
    [h] => 3
    [i] => 6
    [j] => 0
)

索引 a 应该仅为 6 (3 + 3)，因为我可以使用 3 从 C 到 A 的唯一方法步骤是:

C --> F --> B --> A
C --> F --> D --> A

然而，它似乎正在考虑两个(仅？)重复节点的附加路径:

C --> A --> C --> A
C --> B --> C --> A
C --> F --> C --> A
C --> H --> C --> A
C --> I --> C --> A

当然，索引 a 不是唯一错误的。问题似乎是 expand() 但我不确定如何解决它，array_diff(expand('c', $graph, $i), expand('c', $graph, $i - 2)) 似乎修复了这个特定错误，但这不是正确的修复...帮助？

_{^{再次强调，因此您无需滚动}}

最佳答案

一般来说，你可以做一个depth-first search或 breadth-first search ，尽管两者都不优于另一个(因为很容易举出一个优于另一个的示例)。

编辑:在重新阅读问题并稍作思考后，由于您想要从 C 到 A 的所有路径，因此 DFS 从 C 可能最有意义。在此过程中，您必须存储边序列并丢弃序列(如果它们没有以 A 结束)。

关于php - 在无向图中查找路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10804148/