如何在 PHP 中实现图算法

php 中的图算法提供强大的工具来处理图形数据结构，包括：dijkstra 算法：查找无权重图中从源节点到所有其他节点的最短路径。kruskal 算法：构建指定权重的图中的最小生成树。

如何在 PHP 中实现图算法

图算法是处理由节点和边组成的数据结构的强大工具。在 PHP 中，可以使用不同的算法来解决各种图相关问题。

Dijkstra 算法

立即学习“PHP免费学习笔记（深入）”；

PHP5 和 MySQL 圣经

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。

下载

Dijkstra 算法可用于查找无权重图中一个源节点到所有其他节点的最短路径。以下示例展示了如何使用 PHP 实现 Dijkstra 算法：

class Graph {
    private $nodes = [];
    private $edges = [];

    public function addNode($node) {
        $this->nodes[] = $node;
    }

    public function addEdge($node1, $node2, $weight = 1) {
        $this->edges[$node1][$node2] = $weight;
    }

    public function dijkstra($source) {
        $distances = array_fill_keys($this->nodes, INF);
        $distances[$source] = 0;

        $visited = [];

        while (count($visited) < count($this->nodes)) {
            $minDistance = INF;
            $minDistanceNode = null;

            foreach ($this->nodes as $node) {
                if (!in_array($node, $visited) && $distances[$node] < $minDistance) {
                    $minDistance = $distances[$node];
                    $minDistanceNode = $node;
                }
            }

            if ($minDistanceNode === null) {
                break;
            }

            $visited[] = $minDistanceNode;

            foreach ($this->edges[$minDistanceNode] as $neighbor => $weight) {
                $newDistance = $distances[$minDistanceNode] + $weight;
                if ($newDistance < $distances[$neighbor]) {
                    $distances[$neighbor] = $newDistance;
                }
            }
        }

        return $distances;
    }
}

// 实战案例：计算图中的最短路径
$graph = new Graph();
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');

$graph->addEdge('A', 'B', 6);
$graph->addEdge('A', 'C', 8);
$graph->addEdge('A', 'D', 10);
$graph->addEdge('B', 'C', 3);
$graph->addEdge('B', 'D', 9);
$graph->addEdge('C', 'D', 12);

$distances = $graph->dijkstra('A');

var_dump($distances);

Kruskal 算法

Kruskal 算法可用于构建具有指定权重的图中的最小生成树。以下示例展示了如何使用 PHP 实现 Kruskal 算法：

class Graph {
    private $nodes = [];
    private $edges = [];

    public function addNode($node) {
        $this->nodes[] = $node;
    }

    public function addEdge($node1, $node2, $weight = 1) {
        $this->edges[] = [$node1, $node2, $weight];
    }

    public function kruskal() {
        $parents = array_fill_keys($this->nodes, null);
        $ranks = array_fill_keys($this->nodes, 0);

        usort($this->edges, function($a, $b) {
            return $a[2] - $b[2];
        });

        $mst = [];

        foreach ($this->edges as $edge) {
            $x = $this->find($edge[0], $parents);
            $y = $this->find($edge[1], $parents);

            if ($x != $y) {
                $mst[] = $edge;
                $this->union($x, $y, $parents, $ranks);
            }
        }

        return $mst;
    }

    private function find($node, &$parents) {
        if ($parents[$node] === null) {
            return $node;
        }

        return $this->find($parents[$node], $parents);
    }

    private function union($x, $y, &$parents, &$ranks) {
        $xRoot = $this->find($x, $parents);
        $yRoot = $this->find($y, $parents);

        if ($xRoot == $yRoot) {
            return;
        }

        if ($ranks[$xRoot] > $ranks[$yRoot]) {
            $parents[$yRoot] = $xRoot;
        } else if ($ranks[$xRoot] < $ranks[$yRoot]) {
            $parents[$xRoot] = $yRoot;
        } else {
            $parents[$yRoot] = $xRoot;
            $ranks[$xRoot]++;
        }
    }
}

// 实战案例：生成图的最小生成树
$graph = new Graph();
$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addNode('D');

$graph->addEdge('A', 'B', 6);
$graph->addEdge('A', 'C', 8);
$graph->addEdge('A', 'D', 10);
$graph->addEdge('B', 'C', 3);
$graph->addEdge('B', 'D', 9);
$graph->addEdge('C', 'D', 12);

$mst = $graph->kruskal();

var_dump($mst);