---
# System prepended metadata

title: 演算法作業8
tags: [演算法]

---

# 演算法作業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