当前位置：首页 > PHP

php实现图算法

2026-02-16 08:51:35PHP

PHP实现图算法的基础方法

图算法在PHP中可以通过邻接表或邻接矩阵实现。邻接表适合稀疏图，内存占用较少；邻接矩阵适合稠密图，查询效率更高。

邻接表实现示例：

class Graph {
    private $adjList = [];

    public function addEdge($src, $dest) {
        if (!isset($this->adjList[$src])) {
            $this->adjList[$src] = [];
        }
        $this->adjList[$src][] = $dest;
    }

    public function getAdjList() {
        return $this->adjList;
    }
}

邻接矩阵实现示例：

class GraphMatrix {
    private $matrix = [];
    private $size;

    public function __construct($size) {
        $this->size = $size;
        $this->matrix = array_fill(0, $size, array_fill(0, $size, 0));
    }

    public function addEdge($src, $dest) {
        $this->matrix[$src][$dest] = 1;
    }
}

广度优先搜索（BFS）实现

BFS适用于无权图的最短路径查找，使用队列数据结构：

function bfs($graph, $start) {
    $visited = [];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $visited[$start] = true;

    while (!$queue->isEmpty()) {
        $vertex = $queue->dequeue();
        echo $vertex . " ";

        foreach ($graph[$vertex] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }
}

深度优先搜索（DFS）实现

DFS适用于拓扑排序或连通分量检测，使用递归或栈：

function dfs($graph, $vertex, &$visited) {
    $visited[$vertex] = true;
    echo $vertex . " ";

    foreach ($graph[$vertex] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            $this->dfs($graph, $neighbor, $visited);
        }
    }
}

Dijkstra最短路径算法

适用于带权有向图的最短路径查找，需要优先队列：

function dijkstra($graph, $source) {
    $dist = [];
    $visited = [];
    $pq = new SplPriorityQueue();

    foreach ($graph as $v => $adj) {
        $dist[$v] = INF;
    }
    $dist[$source] = 0;
    $pq->insert($source, 0);

    while (!$pq->isEmpty()) {
        $u = $pq->extract();
        if (isset($visited[$u])) continue;
        $visited[$u] = true;

        foreach ($graph[$u] as $v => $weight) {
            if ($dist[$u] + $weight < $dist[$v]) {
                $dist[$v] = $dist[$u] + $weight;
                $pq->insert($v, -$dist[$v]);
            }
        }
    }
    return $dist;
}

图的拓扑排序

对有向无环图（DAG）进行线性排序：

php实现图算法

function topologicalSort($graph) {
    $stack = [];
    $visited = [];

    foreach ($graph as $vertex => $adj) {
        if (!isset($visited[$vertex])) {
            topologicalSortUtil($vertex, $visited, $stack, $graph);
        }
    }

    return array_reverse($stack);
}

function topologicalSortUtil($v, &$visited, &$stack, $graph) {
    $visited[$v] = true;
    if (isset($graph[$v])) {
        foreach ($graph[$v] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                topologicalSortUtil($neighbor, $visited, $stack, $graph);
            }
        }
    }
    array_push($stack, $v);
}