札记之图的认识

图（graph）由边（edge）的集合及顶点（vertex）的集合组成。通常记为：G=(V,E)。

图的概念

图

图（graph）由边（edge）的集合及顶点（vertex）的集合组成。通常记为：G=(V,E)。

有向图

札记之图的认识

说明

G=(V1,{E1})，其中：
V1={A, B, C, D, E, F}，V1表示由”A,B,C,D,E,F”几个顶点组成的集合。
E1={<A, B>, <A, C>, <B, C>, <B, D>, <C, D>, <C, E>, <D, F>}。E1是由矢量<A,B>,矢量<A,C>…等组成的集合。其中，<A,C>表示由顶点A指向顶点C的有向边。

无向图

札记之图的认识

说明

G=(V2,{E2})，其中：
V2={A, B, C, D, E, F}，V2表示由”A,B,C,D,E,F”几个顶点组成的集合。
E2={(A, B), (A, C), (B, C), (B, D), (C, D), (C, E), (D, F)}。E2是由边(A,B),边(A,C)…等组成的集合。其中，(A,C)表示由顶点A和顶点C连接成的边。

顶点、邻接点、边、入边、出边

顶点：图中的元素我们就叫作顶点（vertex）
邻接点：一条边上的两个顶点叫做邻接点。
边：图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫作边（edge）。
入边：在有向图中,是指以该顶点为终点的边；
出边：在有向图中,指以该顶点为起点的边。

例如：

在上面的无向图中，顶点A和顶点B就是邻接点；
在上面的有向图中，<A, B>是A的出边、B的入边。

度

一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
对于有向图来说，一个顶点的度可细分为入度和出度。
入度：一个顶点的入度是指与其关联的各边之中，以其为终点的边数；
出度：出度则是相对的概念，指以该顶点为起点的边数。

例如：

在上面的无向图中，顶点A的度为2，顶点C的度为3，顶点D的度为4；
在上面的有向图中，顶点A的入度是0，出度是2；顶点B的入度是1，出度是2；顶点C的入度是2，出度是2。

图的存储结构(邻接矩阵,邻接表)

邻接矩阵 : 邻接矩阵是表示顶点之间相邻关系的矩阵。设图G有n个顶点，则邻接矩阵是一个n*n的方阵;

札记之图的认识

邻接矩阵代码

class Graph 
{
    // 存储节点信息
    public $vertices;
    // 存储边信息
    public $arcs;
    // 图的节点数
    public $vexnum;
 
    // 初始化
    public function __construct($vertices) 
    {
        $this->vertices = $vertices;
        $this->vexnum = count($this->vertices);
        for ($i = 0; $i < $this->vexnum; $i++) {
            for ($j = 0; $j < $this->vexnum; $j++) {
                $this->arcs[$i][$j] = 0;
            }
        }
    }
 
    // 两个顶点间添加边(无向图)
    public function addEdge($a, $b) 
    {
    	// 边的头尾不能为同一节点
        if ($a == $b) { 
            return;
        }
        $this->arcs[$a][$b] = 1;
        $this->arcs[$b][$a] = 1;
    }

    public function removeEdge($a, $b) 
    {
        if ($a >= 0 && $a < $this->vexnum && $b >= 0 && $b < $this->vexnum) {
            $this->arcs[$a][$b] = 0;
            $this->arcs[$b][$a] = 0;
        }
    }

    public function isEdge($a, $b) 
    {
        if ($a >= 0 && $a < $this->vexnum && $b >= 0 && $b < $this->vexnum) {
            return $this->arcs[$a][$b];
        } else {
            return false;
        }
    }
}
 
$vertices = ['v1', 'v2', 'v3', 'v4', 'v5', 'v6', 'v7', 'v8'];
$graph = new Graph($vertices);
$graph->addEdge(0, 1); // v1 v2
$graph->addEdge(0, 2); // v1 v3
$graph->removeEdge(0, 2);
print_r($graph->isEdge(0, 1));

邻接表: 当图中的边数较少时，用邻接矩阵来实现图结构会浪费很多内存空间，使用邻接表更省空间

札记之图的认识

邻接表代码

class Node 
{
    public $linkNodes = [];//连接的节点
    public function __construct($val)
    {
        $this->val = $val;
    }
}

class Graph
{
    public function buildGraph($data)
    {
        $nodes = [];
        $nodeVals = array_keys($data);  

        foreach ($nodeVals as $nodeVal) {
            $nodes[$nodeVal] = new Node($nodeVal);
        }

        foreach ($data as $key => $vals) {
            foreach ($vals as $val) {
                if (isset($nodes[$val])) {
                    $nodes[$key]->linkNodes[] = $nodes[$val];
                }
            }
        }
        return $nodes;
    }
}

$data = [
    'a' => ['b', 'c'],
    'b' => ['a', 'c', 'd'],
    'c' => ['a', 'b', 'd', 'e'],
    'd' => ['b', 'e', 'f'],
    'e' => ['c', 'd'],
    'f' => ['d'],
];

$obj = new Graph();
print_r($obj->buildGraph($data));