活動網路（Activity Network）
My vault 資料結構筆記：活動網路（Activity Network）。
AOV（Activity on Vertex）
-
定義：AOV 網路是有向圖 $G$。頂點＝任務或活動；邊＝先後關係。
-
前驅 / 後繼：若從 $i$ 有有向路徑到 $j$，則 $i$ 是 $j$ 的前驅，$j$ 是 $i$ 的後繼。
-
直接前驅：若邊 $\langle i,j\rangle\in E$，則 $i$ 為 $j$ 的「直接前驅」。
-
遞移（transitive）：若 $i\to j$ 且 $j\to k$，則 $i\to k$。
-
反自反（irreflexive）：對所有 $i$，不成立 $i\to i$。
-
偏序（partial order）：同時具備「傳遞」與「反自反」的先後關係。
-
可行性：若網路無有向環（即為 DAG），則可行。
拓撲序（Topological Order）
-
定義：一個線性序，使得任意兩頂點 $i,j$，若 $i$ 是 $j$ 的前驅，則 $i$ 在序中先於 $j$。
-
一個 AOV 可能有多個拓撲序。
拓撲排序
目標：輸出一個拓撲序；若偵測到環則回報「不可行」。
資料結構：
-
以adj list表示圖；每個頂點保留in-degree 計數（count）。
-
維護一個堆疊存放入度為 $0$ 的頂點。
步驟：
-
計算所有頂點的 in-degree。將 in-degree $=0$ 的頂點依序推入堆疊 $S$。
-
重複 $n$ 次：
-
若 $S$ 為空，則每個頂點都有前驅 ⇒ 圖含環 ⇒ 報告失敗。
-
否則彈出一頂點 $j$ 並輸出之；
-
對 $j$ 的每個後繼 $k$：將 $k$ 的入度 $count[k]{-}{-}$；若變為 $0$，則把 $k$ 推入 $S$。
-
-
全部輸出完即得一個拓撲序。
時間複雜度：$O(e+n)$。空間：鄰接表與計數陣列 $O(e+n)$。
參考樣式（貼近課本 C 風格）
void topsort(Graph g, int n){
int i, j, k; Node* p;
int top = -1; // 堆疊 top（用整數鏈結法）
for(i=0;i<n;i++) // 建立初始堆疊：入度為 0 的頂點
if(g[i].count==0){ g[i].count = top; top = i; }
for(i=0;i<n;i++){
if(top==-1){ error("Network has a cycle"); return; }
j = top; // 彈出
top = g[top].count;
print(j); // 輸出 j
for(p=g[j].link; p; p=p->link){
k = p->vertex;
if(--g[k].count==0){ // 新成為入度 0
g[k].count = top;
top = k; // 推入堆疊
}
}
}
}
AOE （Activity on Edge）
-
模型：頂點=事件；邊=活動；權重 $w_{uv}$=工期；必要時加「虛擬活動」（工期 $0$）表額外依賴。
-
目標：專案最短完工時間、關鍵路徑、各活動最早/最遲時刻與浮時。
-
流程（先取事件的拓撲序）：
-
正向傳播（最早事件時間）：$ve[s]=0$，$ve[v]=\max_{(u,v)\in E}(ve[u]+w_{uv})$；工期 $T^*=ve[t]$。
-
反向傳播（最遲不延誤時間）：$vl[t]=T^*$，$vl[u]=\min_{(u,v)\in E}(vl[v]-w_{uv})$。
-
活動指標：
-
最早開工 $e_{uv}=ve[u]$。
-
最遲開工 $l_{uv}=vl[v]-w_{uv}$。
-
$s_{uv}=l_{uv}-e_{uv}=(vl[v]-w_{uv})-ve[u]$。
-
-
關鍵活動與路徑：$s_{uv}=0$ 的邊與其連成的 $s\to t$ 路徑（可多條）。
-
-
複雜度：鄰接表＋拓撲序實作皆為 $O(|V|+|E|)$。
範例
-
Q3｜Critical task 判定
-
定義：位於任一關鍵路徑的活動；浮時 $s=0$。
-
作法：跑 CPM，找所有邊 $(u,v)$ 使 $s_{uv}=0$。
-
例：關鍵路徑 $A1\to a4 \to a7\to a10$、$A1\to a4 \to a8\to a11$
→ critical tasks $={A1,a4,a7,a8,a10,a11}$。
-
-
Q4｜縮短工期要加速哪裡
-
先列出全部關鍵路徑，取其交集＝bottleneck tasks。
-
只要縮短交集中的活動，專案總工期一定下降；只縮某一路徑上的非交集活動，可能不降。
-
-
Q5｜哪些活動可延遲？可延遲多久
-
非 critical task 可延遲；可延遲量＝浮時 $s$。
-
事件最早時間（正向）：
-
$ee(s)=0$
-
$ee(v)=\max_{(u,v)\in E}\big(ee(u)+w_{uv}\big)$
-
-
事件最遲時間（反向）：
-
$T^=ee(t)$，$le(t)=T^$
-
$le(u)=\min_{(u,v)\in E}\big(le(v)-w_{uv}\big)$
-
例：$le(y)=15,\ le(z)=16,\ w_{xy}=6,\ w_{xz}=10 \Rightarrow le(x)=\min(15-6,16-10)=6$
-
-
活動指標與浮時：
-
最早開工：$e_{uv}=ee(u)$
-
最遲開工：$l_{uv}=le(v)-w_{uv}$
-
浮時：$s_{uv}=l_{uv}-e_{uv}=(le(v)-w_{uv})-ee(u)$
-
例：$ee(x)=5$，若某活動 $l=7$，則 $s=7-5=2$（可延 2 天不影響完工）
-
-