图的实现

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

术语解释

  • 有向图

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

  • 无向图

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

实现(PHP)

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

邻接表

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

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


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

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

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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";
}
}
}
SICP笔记
You need to set install_url to use ShareThis. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×