jciel/pgraph

PHP 图形库，用于处理图

维护者

详细信息

github.com/Jciel/pgraph

源代码

问题

安装: 5

依赖: 0

建议者: 0

安全: 0

星标: 2

关注者: 2

分支: 1

开放问题: 0

dev-master 2018-04-12 16:47 UTC

Requires

  • php: >=7.1

Requires (Dev)

MIT 33040372feea74ebf50eee783e4c671da231156f

  • Jociel Souza <jcielsouza.woop@gmail.com>

This package is not auto-updated.

Last update: 2024-09-29 06:20:54 UTC

README

PHP 中用于处理二叉搜索树（BST）和二叉树（BT）数据结构的库。它可以处理标量值和对象。

安装

执行 composer require

composer require jciel/pgraph @dev

或在 composer.json 的 require 部分

"require": {
    "jciel/pgraph": "@dev"
}

快速入门示例

二叉树

处理标量值和二叉树

该树总是从左到右创建一个完整的树

实例化并定义搜索比较函数

我们首先实例化一个二叉树，对于搜索，我们必须定义 '搜索函数'，这允许用户定义他们正在处理的内容。
由于我们正在处理标量值，函数类似于这样，该函数应返回 true 或 false。
$value 变量是要查找的值。
$currentVertex 变量是搜索过程中的当前顶点/节点。

<?php

    $bt = new BinaryTree();

    $searchCompareTree = function ($value, $currentVertex) {
        return $value == $currentVertex->getValue();
    };
    
    $bt->setSearchCompare($searchCompareTree);

操作

添加顶点

通过参数传递值实例化一个新顶点，然后将顶点传递给创建的二叉树的 addVertex 方法。
传递的第一个顶点将是树的根。
按照相同的过程添加新的顶点。

<?php

    $nv1 = new BinaryVertex(5);
    $nv2 = new BinaryVertex(2);
    $nv3 = new BinaryVertex(3);
    $nv4 = new BinaryVertex(4);
    
    $bt->addVertex($nv1);
    $bt->addVertex($nv2);
    $bt->addVertex($nv3);
    $bt->addVertex($nv4);
搜索值

为了搜索值，我们使用二叉树的 searchValue 方法，传递要查找的值。
此方法返回一个 BinaryVertex，我们可以使用 getValue 方法来检索值。
此方法使用先前定义的 searchCompareTree 函数来查找所需值。

<?php

    $vertex = $bt->searchValue(4);
    
    $value = $vertex->getValue(); // $value = 4
删除值

为了删除值，我们使用方法 deleteValue 传递要删除的值。
此方法返回 true 如果成功删除，否则返回 false。

<?php
    
    $bt->deleteValue(4); // return true
    $bt->deleteValue(20); // return false

树遍历

中序

中序树遍历首先访问左顶点，然后是根顶点，最后是右顶点。
我们使用二叉树的 inOrder 方法实现这一点。
此方法返回一个包含该顺序的值的数组。

<?php
    
    $inOrder = $bt->inOrder(); // $inOrder = [4, 2, 5, 3]
先序

先序遍历首先访问根顶点，然后是左顶点，最后是右顶点。
使用 preOrder 方法，我们得到一个包含该顺序的值的数组。

<?php
    
    $preOrder = $bt->preOrder(); // $preOrder = [5, 2, 4, 3]
后序

在这种遍历方法中，最后访问根顶点，首先访问左顶点，然后是右顶点。
使用 postOrder 方法，我们得到一个后序顺序的值的数组。

<?php
    
    $postOrder = $bt->postOrder(); // $postOrder = [4, 2, 3, 5]

处理对象和二叉树

想象一个类 Person，其代码如下

<?php
    class Person
    {
        private age;
        
        public function __contructor($age)
        {
            $this->age = $age;
        }
        
        public function getAge()
        {
            return $this->age;
        }
    }

并且我们希望将此类的对象存储在二叉树中，通过属性 age 进行比较。
添加时不需要更改任何内容。

<?php

    $bt = new BinaryTree();

    $person1 = new Person(20);
    $person2 = new Person(26);
    $person3 = new Person(18);
    $person4 = new Person(13);
    
    $bt->addVertex($person1);
    $bt->addVertex($person2);
    $bt->addVertex($person3);
    $bt->addVertex($person4);

但为了搜索和删除通过 age 比较的值，我们必须修改并设置搜索的比较函数。

<?php

    $searchCompareTree = function ($value, $currentVertex) {
        $person = $currentVertex->getValue(); // This method return a value, in this case it is a Person
        return $value == $person->getAge();
    };
    
    $bt->setSearchCompare($searchCompareTree);

现在我们可以通过传递一个年龄值来执行搜索和删除方法。

<?php

    $vertex = $bt->searchValue(26);
    $person = $vertex->getValue(); // This returns a Person
    $age = $person->getAge(); // It returns the age of that person
    
    $bt->deleteValue(13); // return true

二叉搜索树

二叉搜索树以这种方式构建，使得树始终保持排序状态。这意味着左子顶点的值小于或等于父顶点的值，而右子顶点的值将大于父顶点的值。

处理标量值和二叉搜索树

我们首先实例化一个 BST，对于搜索，我们必须定义 '搜索函数'，对于添加，我们必须定义 '添加函数'。
“添加函数”应在新的值小于或等于时返回 真，在值大于时返回 假。 “搜索函数”应在传入的参数值小于当前顶点值时返回 -1，两个值相等时返回 0，以及此值大于当前顶点值时返回 1。

<?php

    $bst = new BinarySearchTree();
    
    $addCompare = function ($newVertex, $currentVertex) {
        return ($newVertex->getValue() <= $currentVertex->getValue()) ? true : false;
    };

    $searchCompare = function ($val, $currentVertex) {
        return $val <=> $currentVertex->getValue();
    };
    
    $bst->setAddCompare($addCompare);
    $bst->setSearchCompare($searchCompare);

操作

添加顶点

用于添加新顶点。

<?php

    $nv1 = new BinaryVertex(5);
    $nv2 = new BinaryVertex(7);
    $nv3 = new BinaryVertex(4);
    $nv4 = new BinaryVertex(2);
    $nv5 = new BinaryVertex(8);
    $nv6 = new BinaryVertex(6);
    
    $bst->addVertex($nv1);
    $bst->addVertex($nv2);
    $bst->addVertex($nv3);
    $bst->addVertex($nv4);
    $bst->addVertex($nv5);
    $bst->addVertex($nv6);
搜索值

要搜索值，我们使用二叉搜索树的 searchValue 方法，传递要查找的值。
此方法返回一个 BinaryVertex，我们可以使用 getValue 方法来检索值。
此方法使用之前定义的 searchCompare 函数来查找请求的值。

<?php

    $vertex = $bst->searchValue(4);
    
    $value = $vertex->getValue(); // $value = 4
删除值

为了删除值，我们使用方法 deleteValue 传递要删除的值。
此方法返回 true 如果成功删除，否则返回 false。

<?php
    
    $bst->deleteValue(4); // return true
    $bst->deleteValue(20); // return false
查找最小和最大值

由于二叉搜索树按顺序存储数据，我们总能找到左侧顶点中的较小数据，右侧顶点中的较大数据，这返回一个 BinaryVertex。

<?php
    
    $min = $bst->searchMin();
    $max = $bst->searchMax();
    
    $valueMin = $min->getValue(); // $min = 2
    $valueMax = $max->getValue(); // $max = 8

二叉搜索树遍历

中序

中序树遍历首先访问左顶点，然后是根顶点，最后是右顶点。
我们使用二叉树的 inOrder 方法实现这一点。
此方法返回一个包含该顺序的值的数组。

<?php
    
    $inOrder = $bst->inOrder(); // $inOrder = [2, 4, 5, 6, 7, 8]
先序

先序遍历首先访问根顶点，然后是左顶点，最后是右顶点。
使用 preOrder 方法，我们得到一个包含该顺序的值的数组。

<?php
    
    $preOrder = $bst->preOrder(); // $preOrder = [5, 4, 2, 7, 6, 8]
后序

在这种遍历方法中，最后访问根顶点，首先访问左顶点，然后是右顶点。
使用 postOrder 方法，我们得到一个后序顺序的值的数组。

<?php
    
    $postOrder = $bst->postOrder(); // $postOrder = [2, 4, 6, 8, 7, 5]

与对象和二叉搜索树一起工作

想象一个类 Person，其代码如下

<?php
    class Person
    {
        private age;
        
        public function __contructor($age)
        {
            $this->age = $age;
        }
        
        public function getAge()
        {
            return $this->age;
        }
    }

为了通过比较年龄来搜索、添加和删除值，我们必须更改和设置比较函数以及添加函数。

<?php

    $bst = new BinarySearchTree();

    $addCompare = function ($newVertex, $currentVertex) {
        $person1 = $newVertex->getValue();
        $person2 = $currentVertex->getValue();
        return ($person1->getAge() <= $person2->getAge()) ? true : false;
    };

    $searchCompare = function ($val, $currentVertex) {
        $person = $currentVertex->getValue();
        return $val <=> $person->getAge();
    };
    
    $bst->setAddCompare($addCompare);
    $bst->setSearchCompare($searchCompare);

现在我们可以在树中添加包含顶点内容的对象。

<?php

    $bst = new BinarySearchTree();

    $person1 = new Person(20);
    $person2 = new Person(26);
    $person3 = new Person(18);
    $person4 = new Person(13);
    
    $bst->addVertex($person1);
    $bst->addVertex($person2);
    $bst->addVertex($person3);
    $bst->addVertex($person4);

通过比较属性年龄进行搜索和删除。

<?php

    $vertex = $bst->searchValue(26);
    $person = $vertex->getValue(); // This returns a Person
    $age = $person->getAge(); // It returns the age of that person
    
    $bst->deleteValue(13); // return true