时间戳

首页 > 解决方案 > 关于 PHP 中可能最快的关系图算法的问题

php - 关于 PHP 中可能最快的关系图算法的问题

问题描述

早上好，这是我的问题。如果我的英语不完美，请提前道歉。无论如何，我在这样形成的数字之间有大量的关系：

$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];

每个数组代表两个数字之间的关系。我需要做的是合并关系以获得结果，例如：

$result1 = [1, 2, 3, 6, 7];
$result1 = [4, 5];

我已经在 PHP 中开发了一个算法来做到这一点，问题是对于总共超过 50000 个关系，程序需要很长时间才能执行。当我完成创建不需要很多时间的直接关系后：

$temporary_result1 = [1, 2, 3];
$temporary_result2 = [4, 5];
$temporary_result3 = [6, 7, 2];

然后我需要合并第 1 组和第 3 组，但是之前创建了大约 20 000 个组，这个过程需要很长时间，因为我需要迭代 20 000 * 20 000 次（400 000 000），这已经花费了大约 30 分钟。由于预计关系的数量会随着时间的推移而增长，我担心执行时间会成倍增长，因为我需要每天执行程序。

我只是想知道是否有一个现有的算法可以做到这一点，同时更有效，在任何我可以尝试在 PHP 中重新编码的编程语言中。

标签： phpalgorithm

解决方案

您可以将这些关系视为 Composer 包。每个包都有它自己的依赖项。

例如，

$relation1 = [1, 2];
$relation2 = [2, 3];

  • 在上面的例子中，你可以说 package1依赖于 package2并且 package2依赖于 package 3。

  • 同样，我们必须找到所有连接的组件。两个包之间的关系不一定是自反的，这意味着包A依赖于包B 并不一定意味着包B依赖于包A。

  • 但是对于这个问题的范围，我们可以使关系自反以通过depth first search. 如果你愿意，你可以适应一个非反身的想法，使用union find by path compression将值与单亲合并，但在我的回答中，我会坚持使用 DFS。

您的输入：

$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];

对于上述输入，邻接列表如下所示：

1 => 2
2 => 1,3,7
3 => 2
4 => 5
5 => 4
6 => 7
7 => 6,2

片段：

function getConnectedComponents($relations,$total_nodes){
    $result = [];
    $nodes = [];
    $visited = [];

    for($i=1;$i<=$total_nodes;++$i){
        $nodes[$i] = [];
        $visited[$i] = false;
    }

    foreach($relations as $relation){
        $nodes[$relation[0]][] = $relation[1];
        $nodes[$relation[1]][] = $relation[0];
    }

    for($i=1;$i<=$total_nodes;++$i){
        if(!$visited[$i]){
            $temp = [];
            dfs($nodes,$i,$visited,$temp);
            $result[] = $temp;
        }
    }

    return $result;
}

function dfs($nodes,$node,&$visited,&$temp){
    if($visited[$node]) return;
    $visited[$node] = true;
    $temp[] = $node;
    foreach($nodes[$node] as $child_node){
        dfs($nodes,$child_node,$visited,$temp);
    }
}

演示： https ://3v4l.org/JWAF6

在上述算法中，我们构建了邻接表，并在每个节点上进行深度优先搜索。我们沿途将节点标记为已访问，以确保我们没有访问我们已经处理过的东西。

推荐阅读