php实现图

PHP 实现图数据结构

在 PHP 中实现图数据结构可以通过多种方式完成。图通常由顶点（节点）和边（边）组成，可以使用邻接表或邻接矩阵来表示。

邻接表实现

邻接表是一种常见的图表示方法，适用于稀疏图。每个顶点维护一个列表，存储与之相连的其他顶点。

class Graph {
    private $adjacencyList = [];

    public function addVertex($vertex) {
        if (!isset($this->adjacencyList[$vertex])) {
            $this->adjacencyList[$vertex] = [];
        }
    }

    public function addEdge($vertex1, $vertex2) {
        $this->adjacencyList[$vertex1][] = $vertex2;
        $this->adjacencyList[$vertex2][] = $vertex1; // 无向图需要双向添加
    }

    public function getVertices() {
        return array_keys($this->adjacencyList);
    }

    public function getNeighbors($vertex) {
        return $this->adjacencyList[$vertex] ?? [];
    }
}

邻接矩阵实现

邻接矩阵适用于稠密图，使用二维数组表示顶点之间的连接关系。

class Graph {
    private $vertices = [];
    private $adjacencyMatrix = [];

    public function addVertex($vertex) {
        if (!in_array($vertex, $this->vertices)) {
            $this->vertices[] = $vertex;
            $size = count($this->vertices);
            foreach ($this->adjacencyMatrix as &$row) {
                $row[] = 0;
            }
            $this->adjacencyMatrix[] = array_fill(0, $size, 0);
        }
    }

    public function addEdge($vertex1, $vertex2) {
        $index1 = array_search($vertex1, $this->vertices);
        $index2 = array_search($vertex2, $this->vertices);
        if ($index1 !== false && $index2 !== false) {
            $this->adjacencyMatrix[$index1][$index2] = 1;
            $this->adjacencyMatrix[$index2][$index1] = 1; // 无向图需要对称设置
        }
    }
}

图的遍历算法

实现图的深度优先搜索（DFS）和广度优先搜索（BFS）是常见的需求。

// DFS 实现
public function dfs($start, &$visited = []) {
    $visited[$start] = true;
    echo $start . " ";
    foreach ($this->getNeighbors($start) as $neighbor) {
        if (!isset($visited[$neighbor])) {
            $this->dfs($neighbor, $visited);
        }
    }
}

// BFS 实现
public function bfs($start) {
    $visited = [];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $visited[$start] = true;
    while (!$queue->isEmpty()) {
        $vertex = $queue->dequeue();
        echo $vertex . " ";
        foreach ($this->getNeighbors($vertex) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }
}

加权图的实现

对于加权图，可以在邻接表中存储边的权重信息。

class WeightedGraph {
    private $adjacencyList = [];

    public function addVertex($vertex) {
        if (!isset($this->adjacencyList[$vertex])) {
            $this->adjacencyList[$vertex] = [];
        }
    }

    public function addEdge($vertex1, $vertex2, $weight) {
        $this->adjacencyList[$vertex1][$vertex2] = $weight;
        $this->adjacencyList[$vertex2][$vertex1] = $weight; // 无向图需要双向添加
    }
}

最短路径算法

Dijkstra 算法可以用于寻找加权图中的最短路径。

public function dijkstra($start) {
    $distances = [];
    $previous = [];
    $queue = new SplPriorityQueue();

    foreach ($this->adjacencyList as $vertex => $edges) {
        $distances[$vertex] = INF;
        $previous[$vertex] = null;
    }
    $distances[$start] = 0;

    $queue->insert($start, 0);

    while (!$queue->isEmpty()) {
        $current = $queue->extract();
        foreach ($this->adjacencyList[$current] as $neighbor => $weight) {
            $alt = $distances[$current] + $weight;
            if ($alt < $distances[$neighbor]) {
                $distances[$neighbor] = $alt;
                $previous[$neighbor] = $current;
                $queue->insert($neighbor, -$alt); // 使用负数模拟最小堆
            }
        }
    }
    return ['distances' => $distances, 'previous' => $previous];
}

以上代码展示了在 PHP 中实现图数据结构的基本方法，包括邻接表、邻接矩阵、图的遍历以及最短路径算法。根据具体需求选择合适的实现方式。