数据结构基础(九)

Chapter 6 Graph - Shortest Path

BFS (for unweighted shortest path)

void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S ){
  Vertex V, U;
  NodePtr ptr;

  dist[S] = 0;
  Enqueue(S, Q);
  while ( !IsEmpty(Q) ) {
    V = Dequeue( Q );
    for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) {
      U = ptr->AdjV;
      if ( dist[U] == INFINITY ) {
         dist[U] = dist[V] + 1;
         path[U] = V;
         Enqueue(U, Q);
      }
    }
  }
}

Dijkstra’s Algorithm (for weighted shortest path)

算法非常简单

void Dijkstra(Table T){
	Vertex V, W;
	for(;;){
		V = smallest unknown distance vertex;
		if(V is not a vertex){
			break;
		}
		T[V].Known = true;
		for(each W adjacent to V){
			if(T[W].Known == false){
				if(T[V].Dist + Cvw < T[W].Dist){
					Decrease(T[W].Dist to T[V].Dist + Cvw);
					T[W].Path = V;
				}
			}
		}
	}
}

$T=O(|V|)*O(\mathrm{inner\ algo.})$

Not work for negative weight edge

Different Implenentation

1. Array
   Good if the graph is dense
   $O(|V|^2+|E|)$
2. Priority Queue
   Good if the graph is sparse
   $O(|V|\log|V|+|E|\log|V|)=O(|E|\log|V|)$

SPFA (for graph with negative edge costs)

当遇到负环就无法终止

Topologic Sort (for acylic graphs / DAG)

$T=O(|E| +|V|)$ and no priority queue is needed

AOE Netwoks

See also

$EC[w]=\displaystyle\max_{(v,w)\in E}\{EC[v]+C_{v,w}\}$

$LC[v]=\displaystyle\min_{(v,w)\in E}\{LC[w]-C_{v,w}\}$

$Slave Time=LC[w]-EC[v]-C_{v,w}$

Critical Path

All-Pairs Shortest Path

Network Flow Problem

Biconnected Component

See also here

Defination

• Articulation Point
• Biconnected Component

DFS Solution

1. Use DFS to obtain a spanning tree of G
2. Find the articulation points in G
   • The root which has at least 2 children
   • The vertex which has at least 1 child and it is impossible to move down and reach its ancestor via back edge

Define $Low(u)=\min\{Num(u),\min\{Low(w)\},\min\{Num(v)\}\}$

• w is child of u
• (u, v) is a back edge

其中Low[u]表示含有 u 的双连通分量第一个被访问的节点的时间戳Num[u]

Therefore, u is an articulation point iff

• u is the root with at least 2 children
• u has at least 1 child v which Low[v] >= Num[u]

Euler Circuit

一笔画 Introduction see also here

• Eular circuit - 欧拉图
• Eular tour - 欧拉路径

DFS Solution

recursive DFS, until all edge visited