PHP图数据结构与算法实现

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虽然不是做算法的最佳语言，但理解这些算法对日常开发中的复杂数据处理很有帮助。比如在分析用户关系、构建推荐系统或者处理任务依赖时，都能用到图算法的思想。