# 演算法作業8
###### tags: `演算法`
1. Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?
Answer:
假設此adjacency-list都是紀錄該vertex所指向的vertex，計算全部vertex的out degree的時間會是$O(|V|+|E|)$，計算所有vertex的時間同樣是$O(|V|+|E|)$，因為同樣需要將每個vertex的list都歷遍。
```cpp=
input: G//G為一個graph
Out_Deg(G){
for each u in G.V
u.out_deg=0
for each v in G.Adj[u]
u.out_deg+=1
}
In_Deg(G){
for each u in G.V
u.in_deg=0
for each u in G.V
for each v in G.Adj[u]
v.in_deg+=1
}
```
2. The transpose of a directed graph $G = (V, E)$ is the graph $G^T = (V, E^T)$, where $E^T = { (v,u) ∈ V x V : (u,v) ∈ E }$. Thus, $G^T$ is G with all its edges reversed. Describe efficient algorithms for computing $G^T$ from G, for both the adjacency-list and adjacencymatrix representations of G. Analyze the running times of your algorithms.
Answer:
對於adjacency matrix來說，將G做transpose相當於將adjacency matrix做transpose，可以經由以下pseudo code看到總共會做兩層1~n的迴圈，因此時間複雜度是$O(n^2)$，也就是$O(|V|^2)$
對於adjacency list來說，做transpose相當於在計算各vertex的in degree的變形，可經由以下pseudo code看到雖然有兩層迴圈，但是實際上做的事情就是把原本的adj_list全部歷遍一次，相當於把每個點跟邊都走過一次，因此時間複雜度是$O(|V|+|E|)$
```cpp=
G.Adj為原圖的adj matrix，G.T_Adj為轉換過的adj matrix
Transpose(G){
let G.T_Adj be a new matrix
for i=1:|G.V|
for j=1:|G.V|
G.T_Adj[j][i]=G.Adj[i][j]
return G.T_Adj[][]
}
G.Adj為原圖的adj list，G.T_Adj為轉換過的adj list
Transpose(G){
let G.T_Adj be a new adj list
for each u in G.V
for each v in G.Adj[u]
G.T_Adj[v].add(u)
return G.T_Adj
}
```
3. The square of a directed graph G = (V, E) is the graph $G^2 = (V, E^2)$ such that $(u, v) ∈ E^2$ if and only if G contains a path with at most two edges between u and v.Describe efficient algorithms for computing $G^2$ from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
Answer:
$(u,v) ∈ E^2$，代表(u,v)在G當中相隔的邊數不超過2
adjacency list的square中每次u碰到自己的鄰近vertex，就會把該vertex的adjacency list再搜索一次
假設$(u,v) ∈ E$，那在找Square的過程中，(u,v)會被碰到的情況有，找u的square_list的時候會碰到1+v.out_degree次，任何$(w,u) ∈ E$也都會各找(u,v)一次，會有u.in_degree次，所以對於任意$(u,v) ∈ E$來說，計算Square過程總共會碰到它 1+(u.in_degree+v.out_degree)，將全部的邊碰到的次數加起來會是$\sum{(1+u.In+v.Out)}=|E|+\sum{(u.In+v.Out)}=|E|+\sum{(u.In)(u.Out)}$
最糟的情況會是每個vertex的子vertex都是|V|-1個，代表每次都必須將整個adjacency list走過一遍，複雜度會是$O(|E|)$，總共有|V|個vertex所以複雜度是$O(|V||E|)$
adj_matrix則是除了將原本的matrix走過一遍之外，如果碰到有邊的元素，會將該j的row也挑出來走一次，最糟情況就是每個j都被挑出來走一次，所以時間複雜度是$O(n^3)$也就是$O(|V|^3)$。
```cpp=
input: G
Square(G){
let G.Square be a new adj matrix
for i=1:|G.V|
for j=1:|G.V|
G.Square[i][j]=0
for k=1:|G.V|
G.Square[i][j]=G.Square[i][j] or (G.Adj[i][k] and G.Adj[k][j])
return G.Square
}
Square(G){
let G.Square be a new adj list
for each u in G.V
for each v in G.Adj[u]
G.Square[u].add(v)
for each w in G.Adj[v]
G.Square[u].add(w)
return G.Square
}
```
4. There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If is it possible to perform such a designation, your algorithm should produce it.
Answer:
將每個wrestler當成vertex，將rivalries當成edge，可以組出一張對戰圖，使用BFS來將此圖走訪一次，如果有sibling之間的edge那就不可能組成一個完整的對戰，如果沒有那就會得到一個對戰圖
使用BFS因此時間複雜度是$O(|V|+|E|)$，在此題中也就是$O(n+r)$。
可以看到pseudo code第30行的地方，如果遇到一個vertex是灰色，且該vertex的深度和自己相同，代表該vertex是自己的sibling，也就是說此graph當中有sibling之間有邊，只要有sibling之間有邊那就沒辦法讓每個邊的兩的vertex都是babyface對上heels，所以直接回傳NULL，表示沒有這可能，如果能一直執行到結束，將每個node也就是每個wrestler訂好他們的type，那就將此圖回傳。
*延伸練習: uva10004 Bicoloring*
```cpp=
struct Wrestler{
id;
type;//babyface or heels，0代表babyface，1代表heels
depth;//在bfs tree中的深度，root深度為0
parent;//紀錄父節點
color;//紀錄顏色
};
BFS_designation(G,root){
for each v in G.V //for each vertex in the vertexs in Graph
v.color=WHITE
v.depth=INF
v.parent=NULL
root.type=0
root.color=GRAY
root.depth=0
Q={} //let Q be a new empty queue
Q.push(root)
while(!Q.empty()){
u=Q.pop()
for each v ∈ G.Adj[u]
if v.color==WHITE
v.color=GRAY
v.depth=u.depth+1
v.parent=u
v.type=(!u.type)
Q.push(v)
else if v.depth==u.depth
return NULL
u.color=BLACK
}
return G
}
```
5. Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. (Your algorithm needs only to count the simple paths, not list them.)
Answer:
因為給定的是DAG，所以任意兩vertex之間若存在path，那一定是simple path，如果不是那代表此圖有路徑會形成cycle，那就不是DAG。所以在DAG中找到任意兩點的simple paths數量就用DFS稍微修改就可以了，時間複雜度和DFS一樣是$O(|V|+|E|)$
另外可以用topologocal sort或bfs也都能夠解此題，時間複雜度也都是$O(|V|+|E|)$
```cpp=
input: DAG,start,end //DAG為一個graph的資料結構，start和end為vertex
FIND_PATHs(DAG,start,end){
for each v in DAG.V
v.paths=0
return BFS(DAG,start,end) //start是dfs的root
}
BFS(G,start,end){
start.paths=1
Q={}//init a FIFO queue
Q.push(start)
while(!Q.empty()){
u=Q.pop() //取得front的元素
for each v in G.V
v.paths+=u.paths
Q.push(v)
}
return end.paths
}
//Topolocal sort method
Simple(G,s,t){
G.V=Topological_Sort(G) //將vertex按照topological sort來排列
for each v in G.V
v.paths=0
s.paths=1
for each u in G.V
for each v in G.Adj[u]
v.paths+=u.paths
return t.paths
}
```
6. Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|.
Answer:
**undirected graph中的edge不是tree edge就是back edge**
無向圖如果沒有環代表此圖也是一顆樹，或是forests，也就是說$|E|=|V|-|T|$，$|T|$是樹的數量，如果是單一顆樹就是1，如果是forests那|T|就是此forests當中的tree數量，所以$|T|>=1$，所以沒有環且每個vertex degree都大於等於1的時候$|E| \le |V|-1$，但我們不能確定是不是每個vertex degree都大於0，不過我們可以確定的是如果$|E|>|V|-1$，那肯定有環，我們可以用DFS做檢查，因為DFS的複雜度是$O(|V|+|E|)$決定，但我們知道不需要檢查$|E|$超過$|V|$次，所以 $|E|=O(|V|)$，若 $|E|<=|V|-1$，則檢查有沒有back edge，若存在back edge則為有環。
所以總時間複雜度就是DFS的時間複雜度 $O(|V|+|E|)=O(|V|+|V|-1)=O(|V|)$
**假設此圖不是multigraph**
```cpp=
input: G//G為一個graph
global variable:edge_num,vertex_num
Cyclic(G){
if |G.E|>=|G.V|
return true
for each v in G.V
v.visit=false
v.parent=NULL
for each v in G.V
if v.visit==false
v.visit=true
if(DFS_check(G,v))
return true //有環
return false //如果整個圖都跑過一遍且沒環回傳false
}
DFS_check(G,v){
for each u in G.Adj[v]
if !u.visit
u.visit=true
u.parent=v
if DFS_check(G,u)
return true
else if v.parent!=u //back edge, v.parent==u代表此edge是tree edge，只是因為undirected graph會重複走一次
return true
return false //以v為root做dfs沒有找到環
}
```
如果是directed graph，那不可能在O(|V|)的時間內檢查此圖有沒有cycle，因為沒有辦法確定|E|>|V|-1就代表有環，必須將edge走過一遍或是使用topological sorting來判別。
7. Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains an euler circuit,and if the answer is positive your algorithm should output an euler circuit.
Answer:
如果一個graph有euler circuit，代表至少可以從任意一個node，以它為起點出發，每個邊都剛好只經過一次且能繞回到該node。代表每個node的degree都必須是偶數且大於等於2，因為每個node都要可以走進去再走出來，只要檢查每個node的degree看有沒有符合此條件就行，如果用adjacency list則時間複雜度會是$O(|V|+|E|)$
```cpp=
input: G
Euler_Cir(G,root){ //randomly choose a vertex to be root
for each u in G.V
u.visit=false
count=DFS_count(G,root) //計算從root能到達且合法的vertex數量
if count<|G.V|
return false
stack S_cur,S_e
S_cur.push(root)
for each edge (u,v) in G.E
(u,v).visit=false
while(!S_cur.empty()){
u=S_cur.top()
done=true
for each v in G.Adj[u]
if !(u,v).visit
S_cur.push(v)
(u,v).visit=true
(v,u).visit=true
done=false
if done
S_e.push(u)
S_cur.pop()
}
while(!S_e.empty())
print S_e.top()
S_e.pop()
return true
}
DFS_count(G,u){
count=0
for each v in G.Adj[u]
if !v.visit
v.visit=true
count+=DFS_count(G,u)
if u.degree%2==0 and u.degree>=2
count+=1
return count
}
```
=======================================================
補充:
DFS所得到每個vertex的discover time還有endtime，如果將vertex用discover time排序，會得到這個DFS forest的preorder，如果用end time排序，會得到postorder
Sign in with Wallet
Connect another wallet