基本的图算法

图的表示

图 G=(V,E) 可以用两种标准表示方法表示。

1. 邻接链表：由一个包含 |V| 条链表的数组 Adj 构成，每个结点有一条链表。

   权重图：直接将边 (u,v) 的权重值 w(u,v) 存放在 u 的邻接链表里。 邻接链表表示 稀疏图（边的条数|E|远小于$|V|^2$）时非常紧凑。

2. 邻接矩阵：由$|V|\times |V|$的矩阵 $A=(a_{ij})$ 表示： $a_{ij}= \begin{cases} 1,~if~(i,j)\in E\
   0,~other \end{cases} $

   邻接矩阵更适合表示 稠密图、需要快速判断任意两个点是否相连的图。

B树

• B树类似于红黑树。他们在降低磁盘I/O操作数方面更好一些。因为B树的分支因子可以非常大，所以其高度要比红黑树小得多。
• B树是以一种自然的方式推广了的二叉搜索树。

B树的定义

我们假定，任何与 关键字相联系的 卫星数据将与关键字一样存放在同一结点中，并随着关键字一起移动。一棵B树T是具有以下性质的有根树（根为T.root）：

B+树是B树的变种。

1. 每个结点x有如下属性： a. x.n，表示结点x中的关键字个数 b. x.n个关键字以非降序排列 c. x.leaf，表示x是否为叶结点
2. 每个内部结点包含 x.n+1 个指针指向孩子们 c[i]
3. x 中的关键字 x.key[i] 对子树中的关键字 k[i] 进行分割，n个关键字，n+1个子树
4. 每个叶结点有相同的深度，即树的高度h
5. 每个结点的关键字数由 最小度数（minimum degree）t>=2控制： a. 除根节点外，每个结点至少含 t-1 个关键字 b. 每个结点至多含 2t-1 个关键字

如果 n>=1，那么对任意一棵包含n个关键字、高度为h、最小度数t>=2 的B树T，有 $h\leq \log_t \frac{n+1}{2}$

动态规划

动态规划方法通常用来求解 最优化问题（optimization problem），通常有四个步骤：

1. 刻画一个最优解的特征
2. 递归地定义最优解的值
3. 计算最优解的值
4. 利用计算出的信息构造一个最优解

动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题。区别在于分治法的子问题互不相交，而动态规划应用于子问题重叠的情况。

栈和队列

栈（stack）实现的是一种后进先出策略。

STACK-EMPTY(S)
	if S.top == 0
		return TRUE
	else return FALSE
	
 PUSH(S, x)
	S.top = S.top + 1
	S[S.top] = x

POP(S)
	if STACK-EMPTY(S)
		error "underflow"
	else S.top = S.top - 1
		return S[S.top +1]

• 待排序的项称为 记录（record），每个记录包含一个 关键字（key），即排序问题中要重排的值，记录的剩余部分由 卫星数据（statellite data）组成。
• 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则称排序算法是 原址的（in place）。插入排序可以在$\Theta(n^2)$时间内将n个数排好序，是一种非常快的原址排序算法；归并排序有更好的渐近运行时间$\Theta(n\lg n)$，但它使用的MERGE过程并不是原址的。

算法基础

插入排序

//INSERTION-SORT(A)
for j = 2 to A.length
	key = A[j]
	//Insert A[j] into the sorted sequence A[1..j-1]
	i = j - 1 
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i+1] = key

• 循环不变式：初始化、保持、终止

###分析算法

• 单处理器计算模型：随机访问机（random-access machine，RAM）：算数指令、数据移动指令、控制指令。
• 最坏情况、平均情况、增长量级

Introduction

multiprocessor

A computer system with at least two processors. This is in contrast to a uniprocessor , which has one.

job-level parallelism or process-level parallelism

Utilizing multiple processors by running independent programs simultaneously.

parallel processing program

A single program that runs on multiple processors simultaneously.

cluster

A set of compters connected over a local area network (LAN) that functions as a single large message-passing multiprocessor.

multicore microprocessor

A microprocessor containing multiple processors (“cores”) in a single integrated circuit.