图的实现

图G = (V,E)通常由一组节点V及节点间的边E共同组成。注：节点在图中也称之为顶点。

术语解释

• 有向图

图中每一条边所对应的两个顶点间都指明了方向。下图是一个有向图，图中0到1有一条边，但是1到0没有边。

• 无向图

图中每一条边所对应的两个顶点间都没有方向。下图是一个无向图，图中0到1有一条边，1到0也有一条边。

实现（PHP）

图有邻接表和邻接矩阵两种常用的实现方式。

邻接表

邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。

可以使用一个二维数组来存储各个顶点和其相邻顶点的信息。一维数组中的每一行的下标是每个顶点的名称或编号，这个下标对应的这一行存储的就是该顶点相邻顶点的信息。
下图是一个有向图，分别有0->1, 0->2 , 0->3 三条边。

下面的数组就可以表示出顶点0相邻的顶点有1,2,3。

$graph = [0 => [1, 2, 3]]

完整代码实现

class Graph
{
    /**
     * 存放顶点和边需要的二维数组
     * @var array
     */
    private $g;

    /**
     * 图中的顶点个数
     * @var int
     */
    private $n;

    /**
     * 图中边的数量
     * @var int
     */
    private $e;

    /**
     * 是否是有向图
     * @var bool
     */

    private $directed;

    /**
     * 构造函数
     * @param 顶点个数
     * @param 是否是有向图，默认为无向图
     */
    public function __construct(int $n, bool $directed = false)
    {
        assert($n > 0);
        $this->n = $n;
        $this->e = 0;
        $this->directed = $directed;
        // 使用array_fill填充一个n行的二维数组，数组的每一行是一个空数组。
        $this->g = array_fill(0, $n, array());
	}

    /**
     * 往图中添加一条边
     * @param 边的起点序号
     * @param 边的目的地序号
     */
    public function addEdge(int $v, int $w)
    {
        // 越界检查
        assert($v >= 0 && $v < $this->n);
        assert($w >= 0 && $w < $this->n);
        // 判断该边是否存在，如果存在直接退出
        if ($this->hasEdge($v, $w))
            return;
        // 往数组g的v（顶点v）行中添加一个顶点w，也就意味生成一条从v到w的一条边。
        array_push($this->g[$v], $w);
        // 在不是自环边并且不是有向图的情况下就添加一条w到v的一条边。
        if ($v != $w && !$directed)
            array_push($this->g[$w], $v);
        // 图的边数自增
        $this->e ++;
    }

    /**
     * 是否存在一条顶点v到顶点w的一条边
     * @param 边的起点序号
     * @param 边的目的地序号
     */
    public function hasEdge(int $v, int $w)
    {
        // 越界检查
        assert($v >= 0 && $v < $this->n);
        assert($w >= 0 && $w < $this->n);
        // 如果g的v（顶点v）行中存在w就说明存在一条v到w的边。
        if (in_array($w, $this->g[$v]))
            return true;
        return false;

    }

    /**
     * 显示图中顶点与边的信息
     */
    public function show()
    {
        foreach ($this->g as $key => $v) {
            echo "|{$key}|\t ";
            foreach ($v as $w) {
                echo "{$w}\t ";
            }
            echo "\n";
        }
    }
}