如何在 PHP 中实现图算法-码农资源网

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

如何在 PHP 中实现图算法

如何在 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);

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