【算法】基础

链表

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

结点记录

用一个嵌套类来定义结点的抽象数据类型。一个Node对象含有两个实例变量，类型分别为Item（参数类型）和Node。调用的结果是一个指向Node对象的引用，它的实例变量均被初始化为null。

private class Node{
	Item item;
	Node next;
}

构造链表

在表头插入结点

从表头删除结点

在表尾插入结点

遍历

1
2
3

for (Node x = first; x != null; x = x.next){
	//处理x.item
}

优点

可以处理任意类型的数据
所需的空间总是和集合的大小成正比
操作所需的时间总是和集合的大小无关

栈

栈是一种基于后进先出（LIFO）策略的集合类型。

实现

将栈保存为一条链表，栈的顶部即为表头，实例变量first指向栈顶。

import java.util.Iterator;

public class Stack<E> implements Iterable<E>{
	private int n;
	private Node first;
	
	private class Node{
		E e;
		Node next;
	}
	
	public boolean isEmpty(){
		return n == 0;
	}
	
	public int size(){
		return n;
	}
	
	public void push(E e){
		Node oldFirst = first;
		first = new Node();
		first.e = e;
		first.next = oldFirst;
		
		n++;
	}
	
	public E pop(){
		E e = first.e;
		first = first.next;
		
		n--;
		
		return e;
	}
	
	public Iterator<E> iterator(){
		return new ListIterator();
	}
	
	private class ListIterator implements Iterator<E>{
		Node current = first;
		
		@Override
		public boolean hasNext() {			
			return current != null;
		}

		@Override
		public E next() {
			E e = current.e;
			current = current.next;
			return e;
		}
	}
}

队列

队列是一种基于先进先出（FIFO）策略的集合类型。

实现

将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量first指向队列的开头，实例变量last指向队列的结尾。

import java.util.Iterator;

public class Queue<E> implements Iterable<E>{
	private int n;
	private Node first;
	private Node last;
	
	private class Node{
		E e;
		Node next;
	}
	
	public boolean isEmpty(){
		return n == 0;
	}
	
	public int size(){
		return n;
	}
	
	public void enqueue(E e){
		Node oldLast = last;
		last = new Node();
		last.e = e;
		
		if (isEmpty())
			first = last;
		else
			oldLast.next = last;
		
		n++;
	}
	
	public E dequeue(){
		E e = first.e;
		first = first.next;
		
		if (isEmpty())
			last = first;
		
		n--;
		
		return e;
	}
	
	public Iterator<E> iterator(){
		return new ListIterator();
	}
	
	private class ListIterator implements Iterator<E>{
		Node current = first;
		
		@Override
		public boolean hasNext() {			
			return current != null;
		}

		@Override
		public E next() {
			E e = current.e;
			current = current.next;
			return e;
		}
	}
}

二叉堆

在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。

定义

当一棵二叉树的结点都大于等于它的两个子结点时，它被称为堆有序。

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（不使用数组的第一个位置）。

根结点是堆有序的二叉树中的最大结点
一棵大小为N的完全二叉树的高度为floor(lgN)

示意

由下至上的堆有序化（上浮）

如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么就需要通过交换它和它的父结点来修复堆。

示意

实现

private void swim(int k){
	while (k > 1 && less(k/2, k)){
		exch(k, k/2);
		k /= 2;
	}
}

由上至下的堆有序化（下沉）

如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么可以通过将它和它的两个子结点中的较大者交换来恢复堆。

示意

实现

private void sink(int k){
	while (2 * k <= n){
		int j = 2 * k;
		
		if (j < n && less(j, j+1))
			j++;
		
		if (!less(k, j))
			break;
		
		exch(k, j);
		
		k = j;
	}
}

优先队列

优先队列是一种抽象数据类型，它表示了一组值和对这些值的操作。优先队列最重要的操作就是删除最大元素delMax()和插入元素insert()。

示意

插入元素

将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。

删除最大元素

从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。

实现

public class MaxPQ<Key extends Comparable<Key>> {
	private Key[] pq;
	private int n = 0;
	
	public MaxPQ(int max){
		pq = (Key[]) new Comparable[max+1];
	}
	
	public boolean isEmpty(){
		return n == 0;
	}
	
	public int size(){
		return n;
	}
	
	public void insert(Key k){
		pq[++n] = k;
		swim(n);
	}
	
	public Key delMax(){
		Key k = pq[1];
		
		exch(1, n);
		n--;
		pq[n+1] = null; 
		sink(1);
		
		return k;
	}
	
	private boolean less(int i, int j){
		return pq[i].compareTo(pq[j]) < 0;
	}
	
	private void exch(int i, int j){
		Key t = pq[i];
		pq[i] = pq[j];
		pq[j] = t;
	}
	
	private void swim(int k){
		while (k > 1 && less(k/2, k)){
			exch(k, k/2);
			k /= 2;
		}
	}
	
	private void sink(int k){
		while (2 * k <= n){
			int j = 2 * k;
			
			if (j < n && less(j, j+1))
				j++;
			
			if (!less(k, j))
				break;
			
			exch(k, j);
			
			k = j;
		}
	}
}

特点

对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN+1）次比较，删除最大元素的操作需要不超过2lgN次比较。

二叉树

二叉树由结点组成，结点包含的链接可以指向空（null）或者其他结点。在二叉树中，每个结点只能有一个父结点指向自己（只有一个例外，也就是根结点，它没有父结点），而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点。

示意

二叉查找树

一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个Comparable的键（以及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

示意

查找

插入

向下取整

选择

删除最小键

删除

范围查找

需要一个遍历二叉查找树的基本方法，叫做中序遍历。

平衡查找树

在一棵含有N个结点的树中，树高为～lgN。

2-3查找树

一棵2-3查找树或为一棵空树，或由以下结点组成：

2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
3-结点，含有两个键（及其对应的值）和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

将指向一棵空树的链接称为空链接。

一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。

示意

查找

插入

向2-结点中插入新键

向一棵只含有一个3-结点的树中插入新键

向一个父结点为2-结点的3-结点中插入新键

向一个父结点为3-结点的3-结点中插入新键

分解根结点

特点

在一棵大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个。

2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。
这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。

比较

和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。

需要维护两种不同类型的结点，将被查找的键和结点中的每个键进行比较，将链接和其他信息从一种结点复制到另一种结点，将结点从一种数据类型转换到另一种数据类型等等。实现这些不仅需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。

红黑二叉查找树

红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。将树中的链接分为两种类型：

红链接：将两个2-结点连接起来构成一个3-结点
黑链接：2-3树中的普通链接。

确切的说，将3-结点表示为由一条左斜的红色链接（两个2-结点其中之一是另一个的左子结点）相连的两个2-结点。

示意

定义

红黑树是含有红黑链接并满足下列条件的二叉查找树：

红链接均为左链接
没有任何一个结点同时和两条红链接相连
该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

颜色表示

颜色转换

旋转

实现

private Node rotateLeft(Node h){
	Node x = h.right;
	h.right = x.left;
	x.left = h;
	
	x.color = h.color;
	h.color = RED;
	x.n = h.n;
	h.n = size(h.left) + size(h.right) + 1;
	
	return x;
}

private Node rotateRight(Node h){
	Node x = h.left;
	h.left = x.right;
	x.right = h;
	
	x.color = h.color;
	h.color = RED;
	x.n = h.n;
	h.n = size(h.left) + size(h.right) + 1;
	
	return x;
}

插入

向2-结点中插入新键

向树底部的2-结点插入新键

向一棵双键树（即一个3-结点）中插入新键

向树底部的3-结点插入新键

删除

不仅要在构造临时4-结点时沿着查找路径向下进行变换，还要在分解遗留的4-结点时沿着查找路径向上进行变换。

删除最小键

特点

对于任意的2-3树，只要对结点进行转换，都可以立即派生出一棵对应的二叉查找树。
红黑树既是二叉查找树，也是2-3树。

散列表

示意

散列函数

如果有一个能够保存M个键值对的数组，那么就需要一个能够将任意键转化为该数组范围内的索引（[0, M-1]范围内的整数）的散列函数。要找的散列函数应该易于计算并且能够均匀分布所有的键，即对于任意键，0到M-1之间的每个整数都有相等的可能性与之对应（与键无关）。

特点

散列表是算法在时间和空间上作出权衡的经典例子。不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间作出取舍。

邻接表

将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中。

示意

特点

使用的空间和V+E成正比
添加一条边所需的时间为常数
遍历顶点v的所有相邻顶点所需的时间和v的度数成正比（处理每个相邻顶点所需的时间为常数）

无向图

边仅仅是两个顶点之间的连接。

当两个顶点通过一条边相连时，称这两个顶点是相邻的，并称该连接依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。

当两个顶点之间存在一条连接双方的路径时，称一个顶点和另一个顶点是连通的。

特殊的图：

自环，即一条连接一个顶点和其自身的边
连接同一对顶点的两条边称为平行边

当且仅当一幅含有V个结点的图G满足下列5个条件之一时，它就是一棵树：

G有V-1条边且不含有环
G有V-1条边且是连通的
G是连通的，但删除任意一条边都会使它不再连通
G是无环图，但添加任意一条边都会产生一条环
G中的任意一对顶点之间仅存在一条简单路径

图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中，被连接的顶点对很少；而在稠密图中，只有少部分顶点对之间没有边连接。

二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

定义

图是由一组顶点和一组能够将两个顶点相连的边组成的。

在图中，路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径，简单环是一条（除了起点和终点必须相同之外）不含有重复顶点和边的环。路径或者环的长度为其中所包含的边数。

如果从任意一个顶点都存在一条路径到达另一个任意顶点，称这幅图是连通图。一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图。

树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合。

示意

实现

public class Graph {
	private final int V;
	private int E;
	private Stack<Integer>[] adj;
	
	public Graph(int V){
		this.V = V;
		this.E = 0;
		adj = (Stack<Integer>[]) new Stack[V];
		
		for (int v = 0; v < V; v++)
			adj[v] = new Stack<Integer>();
	}
	
	public int V(){
		return V;
	}
	
	public int E(){
		return E;
	}
	
	public void addEdge(int v, int w){
		adj[v].push(w);
		adj[w].push(v);
		E++;
	}
	
	public Iterable<Integer> adj(int v){
		return adj[v];
	}
}

有向图

边是单向的：每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的。

一个顶点的出度为由该顶点指出的边的总数；一个顶点的入度为指向该顶点的边的总数。

一条有向边的第一个顶点称为它的头，第二个顶点则被称为它的尾。

两个顶点是强连通的当且仅当它们都在一个普通的有向环中。

有向图中的强连通性是一种顶点之间平等关系，因为它有着以下性质：

自反性：任意顶点v和自己都是强连通的。
对称性：如果v和w是强连通的，那么w和v也是强连通的。
传递性：如果v和w是强连通的且w和x也是强连通的，那么v和x也是强连通的。

作为一种平等关系，强连通行将所有顶点分为了一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的，将这些子集称为强连通分量。一个含有V个顶点的有向图含有1～V个强连通分量，一个强连通图只含有一个强连通分量，而一个有向无环图中则含有V个强连通分量。

定义

一幅有方向性的图（或有向图）是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。

在一幅有向图中，有向路径由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。有向环为一条至少含有一条边且起点和终点相同的有向路径。简单有向环是一条（除了起点和终点必须相同之外）不含有重复的顶点和边的环。路径或者环的长度即为其中所包含的边数。

如果两个顶点v和w是互相可达的，则称它们为强连通的。也就是说，既存在一条从v到w的有向路径，也存在一条从w到v的有向路径。如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的。

示意

实现

public class Digraph {
	private final int V;
	private int E;
	private Stack<Integer>[] adj;
	
	public Digraph(int V){
		this.V = V;
		this.E = 0;
		adj = (Stack<Integer>[]) new Stack[V];
		
		for (int v = 0; v < V; v++){
			adj[v] = new Stack<Integer>();
		}
	}
	
	public int V(){
		return V;
	}
	
	public int E(){
		return E;
	}
	
	public void addEdge(int v, int w){
		adj[v].push(w);
		E++;
	}
	
	public Iterable<Integer> adj(int v){
		return adj[v];
	}
	
	public Digraph reverse(){
		Digraph tmp = new Digraph(V);
		
		for (int v = 0; v < V; v++){
			for (int w : adj[v])
				tmp.addEdge(w, v);
		}
		
		return tmp;
	}
}

加权无向图

加权图是一种为每条边关联一个权值或是成本的图模型。

示意

实现

public class Edge implements Comparable<Edge> {
	private final int v;
	private final int w;
	private final double weight;
	
	public Edge(int v, int w, double weight){
		this.v = v;
		this.w = w;
		this.weight = weight;
	}
	
	public double weight(){
		return weight;
	}
	
	public int either(){
		return v;
	}
	
	public int other(int vertex){
		if (vertex == v)
			return w;
		else
			return v;
	}
	
	public int compareTo(Edge that){
		return Double.compare(this.weight, that.weight);
	}
}

public class EdgeWeightedGraph {
	private final int V;
	private int E;
	private Stack<Edge>[] adj;
	
	public EdgeWeightedGraph(int V){
		this.V = V;
		this.E = 0;
		adj = (Stack<Edge>[]) new Stack[V];
		
		for (int v = 0; v < V; v++)
			adj[v] = new Stack<Edge>();
	}
	
	public int V(){
		return V;
	}
	
	public int E(){
		return E;
	}
	
	public void addEdge(Edge e){
		int v = e.either();
		int w = e.other(v);
		adj[v].push(e);
		adj[w].push(e);
		E++;
	}
	
	public Iterable<Edge> adj(int v){
		return adj[v];
	}
	
	public Iterable<Edge> edges(){
		Stack<Edge> stack = new Stack<Edge>();
		
		for (int v = 0; v < V; v++){
			for(Edge e : adj[v]){
				if (e.other(v) > v)
					stack.push(e);
			}
		}
		
		return stack;
	}
}

最小生成树

定义

图的生成树是它的一棵含有其所有顶点的无环连通子图。一幅加权无向图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。

示意

切分定理

把加权图中的所有顶点分为两个集合、检查横跨两个集合的所有边并识别哪条边应属于图的最小生成树。通常，通过指定一个顶点集并隐式地认为它的补集为另一个顶点集来指定一个切分。这样，一条横切边就是连接该集合的一个顶点和不在该集合中的另一个顶点的一条边。

定义

图的一种切分是将图的所有顶点分为两个非空且不重复的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。

示意

贪心算法

使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。

定义

将含有V个顶点的任意加权连通图中属于最小生成树的边标记为黑色：初始状态下所有边均为灰色，找到一种切分，它产生的横切边均不为黑色。将它权重最小的横切边标记为黑色。反复，直到标记了V-1条黑色边为止。

示意

加权有向图

在加权有向图中，每条有向路径都有一个与之关联的路径权重。

示意

实现

public class DirectedEdge {
	private final int v;
	private final int w;
	private final double weight;
	
	public DirectedEdge(int v, int w, double weight){
		this.v = v;
		this.w = w;
		this.weight = weight;
	}
	
	public double weight(){
		return weight;
	}
	
	public int from(){
		return v;
	}
	
	public int to(){
		return w;
	}
}

public class EdgeWeightedDigraph {
	private final int V;
	private int E;
	private Stack<DirectedEdge>[] adj;
	
	public EdgeWeightedDigraph(int V){
		this.V = V;
		this.E = 0;
		adj = (Stack<DirectedEdge>[]) new Stack[V];
		
		for (int v = 0; v < V; v++)
			adj[v] = new Stack<DirectedEdge>();
	}
	
	public int V(){
		return V;
	}
	
	public int E(){
		return E;
	}
	
	public void addEdge(DirectedEdge e){
		adj[e.from()].push(e);
		E++;
	}
	
	public Iterable<DirectedEdge> adj(int v){
		return adj[v];
	}
	
	public Iterable<DirectedEdge> edges(){
		Stack<DirectedEdge> stack = new Stack<DirectedEdge>();
		
		for (int v = 0; v < V; v++){
			for(DirectedEdge e : adj[v])
				stack.push(e);
		}
		
		return stack;
	}
}

最短路径树

最短路径

定义

在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。

示意

定义

给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含s和从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。

示意

边的松弛

放松边v->w意味着检查从s到w的最短路径是否是先从s到v，然后再由v到w。如果是，则根据这个情况更新数据结构的内容。

示意

实现

private void relax(DirectedEdge e){
	int v = e.from();
	int w = e.to();
	
	if (distTo[v] + e.weight() < distTo[w]){
		distTo[w] = distTo[v] + e.weight();
		edgeTo[w] = e;
	}
}

顶点的松弛

放松从一个给定顶点指出的所有边。

示意

实现

private void relax(EdgeWeightedDigraph g, int v){
	for (DirectedEdge e : g.adj(v)){
		int w = e.to();
		
		if (distTo[v] + e.weight() < distTo[w]){
			distTo[w] = distTo[v] + e.weight();
			edgeTo[w] = e;
		}
	}
}

负权重的环

示意

定义

加权有向图中的负权重环是一个总权重（环上的所有边的权重之和）为负的有向环。

当且仅当加权有向图中至少存在一条从s到v的有向路径且所有从s到v的有向路径上的任意顶点都不存在于任何负权重环中时，s到v的最短路径才是存在的。