最近开始在跟进coursera的算法课程,为明年的实习面试做准备。Sedgewick的这门算法课程非常出名,配套的有一本书叫做《Algorithms》,和Coursera上的课程配套。

第一周课程先以一个案例即union-find算法为例,阐述算法分析的基础。

##动态连通性
union-find算法要解决的是一个连通性问题。首先,问题描述:
给定一个有N个对象的集合,定义如下操作:

  • Union command: 连接两个对象。
  • Find/connected query:两个对象之间是否是连通的。

该问题有许多应用场景,如迷宫寻路,物理化学中的渗流和通信网络中的连通性等等。

算法的API定义:

1
2
3
4
5
6
public class UF
UF(int N) inial union-find data stucture with N objects(0 to N-1)
void union(int p, int q) add connection between p and q
boolean connected(int p, int q) are p and q in the same component?
int find(int p) component identifier for p(0 to N-1)
int count() number of component

动态连通性client

1
2
3
4
5
6
7
8
9
10
11
12
publci static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(N);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (!uf.connected(p, q)) {
uf.union(p, q);
StdOut.println(p + " " + q);
}
}
}

输出实例:

动态连通性

课程实现了两种UnionFind算法,逐渐优化。

Quick-find

第一种使用暴力方法,每次union(p, q),将所有值为q的索引的值更新为q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class QuickFindUF {
private int[] id;
public QuickFindUF(int N) {
id = new int[N];
for(int i = 0; i < N; i++)
id[i] = i;
}
public boolean connected(int p, int q) {
return id[p] = id[q];
}
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}

Quick-uinion

使用数据结构“树”,同一子集有相同的祖先节点(根节点)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class QuickUnionUF {
private int[] id;
public QuickUnionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
private int root(int i) {
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q) {
retur root(p) == root(q);
}
public void union(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}
}

改进一:加权

防止“树枝”过长,根据权重调节树枝长度。

修改union

1
2
3
4
5
6
7
8
9
10
int i = root(p);
int j = root(q);
if (i == j) return;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}

改进二:路径压缩

1
2
3
4
5
6
7
private int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

课程作业——渗透问题(Pecolation)

问题描述的网址在Programming Assignment 1: Pecolation

寒假有空整理下,未完待续……