PHP图数据结构与算法实现

张

张建站

2026/6/4 7:34:58

10分钟阅读

PHP图数据结构与算法实现图是计算机科学中非常重要的数据结构。PHP虽然主要用于Web开发但理解图算法对处理复杂关系数据很有帮助。今天说说常见的图算法在PHP中的实现。图的表示方式有邻接矩阵和邻接表两种。邻接表在PHP中实现更自然。php// 图的邻接表实现class Graph{private array $adjacencyList [];private bool $directed;public function __construct(bool $directed false){$this-directed $directed;}public function addVertex(string $vertex): void{if (!isset($this-adjacencyList[$vertex])) {$this-adjacencyList[$vertex] [];}}public function addEdge(string $from, string $to, int $weight 1): void{$this-addVertex($from);$this-addVertex($to);$this-adjacencyList[$from][] [node $to, weight $weight];if (!$this-directed) {$this-adjacencyList[$to][] [node $from, weight $weight];}}public function getVertices(): array{return array_keys($this-adjacencyList);}public function getNeighbors(string $vertex): array{return $this-adjacencyList[$vertex] ?? [];}// 广度优先搜索public function bfs(string $start): array{$visited [];$queue [$start];$result [];while (!empty($queue)) {$vertex array_shift($queue);if (isset($visited[$vertex])) continue;$visited[$vertex] true;$result[] $vertex;foreach ($this-adjacencyList[$vertex] ?? [] as $neighbor) {if (!isset($visited[$neighbor[node]])) {$queue[] $neighbor[node];}}}return $result;}// 深度优先搜索public function dfs(string $start): array{$visited [];$result [];$this-dfsRecursive($start, $visited, $result);return $result;}private function dfsRecursive(string $vertex, array $visited, array $result): void{if (isset($visited[$vertex])) return;$visited[$vertex] true;$result[] $vertex;foreach ($this-adjacencyList[$vertex] ?? [] as $neighbor) {$this-dfsRecursive($neighbor[node], $visited, $result);}}// 拓扑排序public function topologicalSort(): array{if (!$this-directed) {throw new RuntimeException(拓扑排序只能用于有向图);}$inDegree [];foreach ($this-adjacencyList as $vertex $neighbors) {if (!isset($inDegree[$vertex])) $inDegree[$vertex] 0;foreach ($neighbors as $neighbor) {$inDegree[$neighbor[node]] ($inDegree[$neighbor[node]] ?? 0) 1;}}$queue [];foreach ($inDegree as $vertex $degree) {if ($degree 0) {$queue[] $vertex;}}$result [];while (!empty($queue)) {$vertex array_shift($queue);$result[] $vertex;foreach ($this-adjacencyList[$vertex] ?? [] as $neighbor) {$inDegree[$neighbor[node]]--;if ($inDegree[$neighbor[node]] 0) {$queue[] $neighbor[node];}}}if (count($result) ! count($this-adjacencyList)) {throw new RuntimeException(图中存在环无法进行拓扑排序);}return $result;}// 最短路径Dijkstra算法public function shortestPath(string $start, string $end): array{$distances [];$previous [];$unvisited [];foreach ($this-adjacencyList as $vertex $neighbors) {$distances[$vertex] INF;$previous[$vertex] null;$unvisited[$vertex] true;}$distances[$start] 0;while (!empty($unvisited)) {// 选取距离最小的未访问节点$current null;$minDist INF;foreach ($unvisited as $vertex $_) {if ($distances[$vertex] $minDist) {$minDist $distances[$vertex];$current $vertex;}}if ($current null || $current $end) break;unset($unvisited[$current]);foreach ($this-adjacencyList[$current] ?? [] as $neighbor) {$alt $distances[$current] $neighbor[weight];if ($alt $distances[$neighbor[node]]) {$distances[$neighbor[node]] $alt;$previous[$neighbor[node]] $current;}}}// 重建路径$path [];$current $end;while ($current ! null) {array_unshift($path, $current);$current $previous[$current];}return [path $path,distance $distances[$end],];}}$graph new Graph(true);// 构建有向图$graph-addEdge(A, B, 4);$graph-addEdge(A, C, 2);$graph-addEdge(B, C, 1);$graph-addEdge(B, D, 5);$graph-addEdge(C, D, 8);$graph-addEdge(C, E, 10);$graph-addEdge(D, E, 2);echo DFS: . implode( - , $graph-dfs(A)) . \n;echo BFS: . implode( - , $graph-bfs(A)) . \n;$result $graph-shortestPath(A, E);echo 最短路径: . implode( - , $result[path]) . \n;echo 距离: {$result[distance]}\n;?图算法在社交网络、路径规划、依赖管理等场景中很有用。PHP虽然不是做算法的最佳语言但理解这些算法对日常开发中的复杂数据处理很有帮助。比如在分析用户关系、构建推荐系统或者处理任务依赖时都能用到图算法的思想。