图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";
}
}
}

定义

1.有且只有一个称为根的节点
2.有若干个互不相交的子树,这些子树本身也是一棵树
3.每个子节点只有一个父节点,但可以有多个子节点
4.没有父节点的节点称为根节点

术语解释

节点:
父节点:最上面
子节点:
子孙:
堂兄弟:
深度:从根节点到最底层节点的层数称为深度,根节点是第一层
叶子节点:没有子节点的节点
非叶子节点:有子节点的节点
度:子节点的个数

树的分类

一般树

任意一个节点的子节点的个数都不受限制

二叉树

任意一个节点的子节点的个数最多两个,且子节点的位置不可更改

分类
满二叉树

每一层的节点数都是最大节点数。
在不增加树的层数的前提下无法再多添加一个节点的二叉树。

完全二叉树

只是删除了满二叉树最底层最右边连续的若干个节点,这样形成的二叉树就是完全二叉树。
完全二叉树包含满二叉树,满二叉树是完全二叉树的一个特例。
特点:
1.知道节点的个数就能得出树的层数。
2.已知一个节点可以得出该节点的父节点和子节点,注:根节点没有父节点,叶子节点没有子节点。

二叉树的存储

通常会把一个二叉树转换成一个满二叉树后再把树的最再进行存储

森林

N个互不相交的树的集合

完全二叉树:每一层的子节点个数必须
叶子节点:没有子节点的节点
第一个非叶子节点:堆元素个数除以2得到的索引就是第一个非叶子节点。count/2(以1开始计数)(count-1)/2(以0开始计数)

节点序号规律:

以1开始计数:每个节点的序号都是父节点序号的2倍,相应的每个节点的左子节点序号都是自身序号的二倍,右子节点序号是自身序号的二倍+1。
parent(i) = i / 2
left child(i) = i 2
right child(i) = i
2 + 1
以0开始计数:
parent(i) = (i - 1) / 2
left child(i) = i 2 + 1
right child(i) = i
2 + 2

最大二叉堆

规则

1.任何一个节点都不大于它的父节点
2.二叉堆是一个完全二叉树

往堆中添加一个元素

把要新加入到堆中的元素添加到堆的尾部,然后以尾部的位置开始执行shiftUp操作,shiftUp操作过程如下:
判断当前节点是否比其父节点大,如果比父节点大并且当前节点序号大于1(以1开始计数)就跟父节点交换位置。一直循环该操作。

在堆中取出一个元素

把堆中根节点的元素取出来然后再把尾节点的元素移到根节点的位置后对根节点做做shiftDown操作
shiftDown操作过程如下:

Heapify

将一个数组建立成一个最大堆的形状的过程叫做Heapify

C语言
1
2
3
4
5
6
7
8
9
void insertSort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int j = 0;
int e = arr[i];
for(j = i; j > 0 && e < arr[j - 1]; j--)
arr[j] = arr[j - 1];
arr[j] = e;
}
}

当一个对象的内在状态改变时允许改变其行为, 这个对象看起来像是改变了其类.
状态模式主要解决的是当控制一个对象状态转换的条件表达式过于复杂时的情况. 把状态的判断逻辑转移到表示不同状态的一系列类当中, 可以把复杂的判断逻辑简化
如果这个状态判断很简单,那就没必要用状态模式了
状态模式使用一个对象可以在不同的状态下表现出不同的行为。

  • 状态的使用:
  • 比如表示一个人在一天不同时刻的工作内容.

跟策略模式的对比

  • 状态模式可以帮助对象来管理它的状态
  • 策略模式使得客户端可以选择不同的行为。
  • 一个不太容易看到的区别是,谁去驱动行为的改变。
  • 在策略模式中,是客户端驱动的,它给上下文信息提供了不同的策略
  • 在状态模式中,状态的迁移是由Context或者State对象自己来管理的
  • 从理论上说,策略模式和状态模式还有一个不同,前者定义的是一个对象“如何”去做一件事情,比如说如何对数据进行排序,而另一方面,状态模式定义的是“什么”以及“何时“,比如说一个对象能做什么,某个时间点它处于哪个状态。

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

<?php

abstract class Request {

abstract function handel();

}

class LogRequest extends Request {

function handel() {
echo "LogRequest\n";
}
}

abstract class RequestDecorator extends Request {

protected $request;

public function __construct(Request $request) {
$this->request = $request;
}
}


class AuthRequestDecorator extends RequestDecorator {

function handel() {
echo "AuthRequestDecorator\n";
$this->request->handel();
}

}


class FormRequestDecorator extends RequestDecorator {

function handel() {
echo "FormRequestDecorator\n";
$this->request->handel();
}

}


$AuthRequestDecorator = new FormRequestDecorator(new AuthRequestDecorator(new LogRequest()));
$AuthRequestDecorator->handel();
Your browser is out-of-date!

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

×