如何在 PHP 中实现图算法

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

如何在 PHP 中实现图算法

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

Dijkstra 算法

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);