README

一个PHP库，用于从有向无环图（DAG）中查找最低共同祖先。

见解

这个库是为了从有向无环图（DAG）中查找最低共同祖先而构建的。它首先创建一个图，然后将节点（称为节点1）的父节点存储在一个数组（称为数组1）中。为了找到节点1的父节点，我们使用广度优先搜索（BFS）逆向遍历，即从节点1到根节点。对节点2也执行相同的操作。然后通过数组1和数组2的元素交集找到LCA。交集返回的第一个节点是这两个节点的LCA。

依赖项

此库使用clue/graph来创建图，并使用graphp/algorithms进行广度优先遍历。

安装

此库可以通过composer安装。

{
  "name": "myorg/mylib",
  "description": "A library depending on relaxed/lca",
  "require": {
    "relaxedws/lca": "dev-master"
  }
}

示例

安装后，我们可以按照以下方式执行合并

<?php

require __DIR__ ."/vendor/autoload.php";

use Fhaculty\Graph\Graph;
use Relaxed\LCA\LowestCommonAncestor;

$graph = new Graph();

for ($i=1; $i<=6 ; $i++){
   $vertices['node_'.$i] = $graph->createVertex('node_'.$i);
}

$vertices['node_1']->createEdgeTo($vertices['node_2']);
$vertices['node_1']->createEdgeTo($vertices['node_5']);
$vertices['node_2']->createEdgeTo($vertices['node_3']);
$vertices['node_2']->createEdgeTo($vertices['node_4']);
$vertices['node_5']->createEdgeTo($vertices['node_6']);


$instance = new LowestCommonAncestor($graph);

$lca = $instance->find($vertices['node_3'], $vertices['node_4']);
$base = $lca->getId();

贡献

我们欢迎任何人在此项目中使用、测试或贡献。我们拥有广泛的测试覆盖率，但正如我们所知，软件中总是存在缺陷。请提交问题或带有评论或建议的拉取请求。

relaxedws / lca

维护者

详细信息

README

见解

依赖项

安装

示例

贡献