Graph Algorithm¶
Preliminary: Dynamic Programming¶
(Note: content of this part is different from dynamic programming in combination optimization)
- Longest common subsequence, LCS
input: \(x=\{x_i\}_{i=1}^m\), \(y=\{y_i\}_{i=1}^n\),
output: their LCS.
For example, if we have two sequences
then LCS\((x,y)=\{BDAB,BCAB,BCBA\}\).
- solve the length of LCS.
- \(x[i]=y[j]\), if \(C[i,j]=k\), denote one element \(z[1,\cdots,k]\in\) LCS\([i,j]\). then \(z[k]=x[i]=y[j]\). So \(z[1,\cdots,k-1]\in LCS[i-1,j-1]\).
Assume \(w\in\) LCS\([i-1.j-1]\) and \(|w|>k-1\), then connect \(w\) and \(z[k]\), \(w+z[k]\) satisfies
contradicts!
- optimal substructure
\(\forall z[1,\cdots,k]\in\) LCS\([m,n]\), then \(z[1,\cdots,s]\), \(s< k\) must be LCS of their prefix.
LCS(x,y,i,j)
if(i==-1||j==-1)
return 0
else if (x[i]==y[j])
c[i,j]=LCS(x,y,i-1.j-1)+1
else
c[i,j]=max(LCS(x,y,i,j-1),LCS(x,y,i-1.j))
return c[i,j]
- cut off
write a note of LCS that has been calculated. So next time we encounter a same item, directly use it. In fact we use a 2 dimension array.
LCS(x,y,i,j)
if (c[i,j]==nil)
if (x[i]==y[j])
c[i,j]=LCS(x,y,i-1.j-1)+1
else
c[i,j]=max(LCS(x,y,i,j-1),LCS(x,y,i-1.j))
return c[i,j]
time cost \(O(mn)\).
自顶向下 top down.
自底向上 bottom up.
Gragh theory¶
Definitions¶
A graph \(G=(V,E)\) consists a set of vertices, \(V\) and a set of edges \(E\). for \(u,w\in V\), \((u,w)\in E\).
If \((u,w)\neq(w,u)\), then we call the graph is directed, or digraph. Otherwise we call the graph undirected.
We call \(u,w\in V\) are adjacent iff \((u,w)\in E\). A map from \(E\) to \(\mathbb{R}\) is called weight, or cost.
A path is a sequence of vertices \(\{w_1,w_2,\cdots,w_N\}\), such that \((w_i,w_{i+1})\in E\), \(\forall i\in [1,N-1]\). When there is not weight defined, the length of the path is \(N-1\).
自环路径(Loop).
A simple path is a path such that all vertices are distinct, except that the first and the last could be the same.
A cycle path(循环路径) in a directed graph is a path of length at least 1 such that \(w_1=w_N\).
A directed graph is acyclic if it has no cycles.
Directed Acyclic Graph(有向无环图).
An undirected graph is connected, if \(\forall u,w\in V\), \((u,w)\in E\). A directed graph with this property is called strongly connected.
Representation of Graph¶
- Use 2 dimension array. Adjacency matrix.
If \(|E|= \Theta(|V|^2)\), then the graph is dense.
If \(|E|= \Theta(|V|)\), then the graph is sparse.
- Use linked-list. Adjacency list.
For each vertex, we keep a list of all adjacent vertices.
Space cost \(O(|V|+|E|)\).
Topological Sort¶
Definition of Topological Sort
- 拓扑序 | Topological Sort
\(\forall v_i,v_j\in V\), we say \(v_i\leq v_j\), if there exists
(i) a path from \(v_i\) to \(v_j\)
(ii) \(v_i\) is before \(v_j\)
- 拓扑排序 | Topological Sorting
list \(\{v_i\}_{i-1}^n\) into a queue
such that, \(\forall v'_i\neq v'_j\), we have
(i) \(v_i\leq v_j\)
(ii) there exists no path from \(v_i\) to \(v_j\).
- 入度 | indegree
there must exist a node with indegree = 0.
topsort()
{
for(i=0;i<n_vertex;i++)
v = FindNextVertexIndegreeZero() // actually we could only do this for the first time.
v.tp=i;
for each w adjacent to v
w.indegree --;
}
void Graph::topsort()
{
Queue<vertex> q;
int counter = 0;
q.makeEmpty();
for each vertex in V:
if v.indegree==0:
q.enqueue(v); // O(|V|)
while(!q.empty()){
vertex v= q.dequeue();
v.tp=++counter;
for each vertex w adjacent to v:
if(--w.indegree==0):
q.enqueue(w);
} // O(|E|+|V|)
if(counter != NUM_VERTICES)
throw CYclwFoundException();
}
Shortest-Path Algorithm¶
Input is a weighted Graph.
Assume weight is positive.
Theorem
If \(P_{(u,v)}\) is the shortest path between u and v, then \(\forall x,y\in P_{(u,v)}\), \(P_{(x,y)}\subset P_{(u,v)}\) is the shortest path bwtween x and y.
Or triangle inequality. forall \(x,y,z \in V\)
By contradiction. If there exists another path \(P'_{(x,y)}\neq P_{(x,y)}\) and
then
that is, we find a path that is smaller than the shortest path, which contradicts!
We also call the above problem Single-Source shortest path.
The method is known as Dijlstra's Algorithm.
Unweighted graph¶
This is actually BFS.
void Graph::unweighted(Vertex s)
{
Queue<Vertex> q;
for each Vertex v
{
v.dist = INFTY;
v.known = false;
}
s.dist=0;
q.enqueue(s);
while(!q.isEmpty())
{
Vertex v = q.dequeue();
for each Vertex w adjacent to v:
if(w.dist == INFTY):
{
w.dist = v.dist + 1;
w.path = v;
q.enqueue(w);
}
}
}
Cost: \(O(|E|+|V|)\)
Weighted Graph¶
This time, we cannot say that the neighberhood is the shortest, which may be longer than some path with more vertices but less weight cost.
s.d=0;
for each v in V-{s}
v.d=INFTY;
Queue=V;
while(!q.isEmpty()){
u = q.pop_min(); // smallest heap
for each v adjacent to u:
if v.d>u.d+w(u,v):
v.d = u.d+w(u,v);
v.p = u;
}
All-pair shortest path¶
use adjacent matrix \(A=(a_{ij})_{n\times n}\), with \(a_{ij}\) denotes the weight from \(v_i\) to \(v_j\) and \(a_{ii}=0\).
use \(d_{ij}^{(m)}\) to denote the shortest path weight from \(v_i\) to \(v_j\) with passing \(m\) edges.
Graph with negative costs¶
Theorem of Bellman-Fond Algorithm
v.d is the shortest path from s to v.
v.d is homotonically decreasing and has lower bound.
bounded graph¶
solve shortest path between all vertices¶
Assume G is a dense graph.
\(a_{ij}\) denotes the weight form i to j.
\(d_{ij}^{(m)}\) denotes the shortest path with length \(m\) from i to j.
(i) \(d_{ij}^{(0)}=\begin{cases}0,\quad i=j\\ \infty,\quad \text{else}\end{cases}\)
(ii) \(d_{ij}^{(k)}\)
FLoyd-Worshall Algorithm¶
define \(c_{ij}^{(n)}\) the shortest path with length at most \(n-1\) from i to j, and only passes vertices \(\{1,2,\cdots, k\}\)
Remapping¶
then
Theorem
\(\forall u,v \in V\), \(P_{uv}\) is the path, then
Corollary
\delta_h(u,v) = \delta(u,v)+h(u)-h(v)
How to get \(h\)?
notice that \(w_h(u,v)=w(u,v)+ h(u)-h(v)\geq 0 \Rightarrow\)
which is a difference bounded system. So we can use Bellman-Fond Algorithm. Then the cost of weight is all positive, so we can use Dijkstra Algorithm. So here comes Johnsen Algorithm.
- Johnsen Algorithm
(i) find \(h:V\rightarrow \mathb{R}\), such that
use Bellman-Fond Algorithm to solve \(h\).
(ii) use w_h to run Dijkstra Algorithm, get \(\delta_h(u,v)\).
(iii)
Minimum spanning trees¶
Theorem
delete one edge from a MST, denoted by T1, T2, and the subgraph of G denoted by G1, G2. Then T1, T2 is the MST of G1, G2 respectively.
Assume we delete (u,v), then
w(T) = w(u,v) + w(T1)+w(T2)
If we find another tree T1', s.t. w(T1')<w(T1)
then T'=T1'\cup (u,v)\cup T2
which satisfies w(T')<w(T), contracdicts!
Convex!
Theorem
Assume T is the MST of G(V,E), A\subset V, assume (u,v)\in E is the smallest edge which can connect A and V\ A, then
(u,v)\in T
Assume (u,v)\nin T