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);
登录后复制
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);
登录后复制
PHP免费学习笔记（深入）：立即学习
踏上前端学习之旅，开启通往精通之路！从前端基础到项目实战，循序渐进，一步一个脚印，迈向巅峰！
以上就是如何在 PHP 中实现图算法的详细内容，更多请关注php中文网其它相关文章！