---
title: homework X
---
# P1
- [ ][name=昱]

[CLRS 3rd] Exercise 22.3-5
## topic
Show that edge (u,v) is

a. a tree edge or forward edge if and only if $u.d<v.d<v.f<u.f$,

b. a back edge if and only if $v.d \le u.d < u.f \le v.f$, and

c. a cross edge if and only if $v.d<v.f<u.d<u.f$.

## Solution
以下的u皆為未visit的點
### a.
tree edge和forward edge指向子孫
<pre>
->
u為祖先, v為子孫(tree edge則v未visit, forward edge則v已visit): u.d < v.d
u的所有子樹(包括v)visit完, u才會離開: v.f < u.f
所以tree edge和forward edge: u.d < v.d < v.f < u.f
<-
u.d < v.d: u比v早visit
v.f < u.f: v比u早離開
所以u.d < v.d < v.f < u.f: (u, v)為tree edge或forward edge
</pre>
### b.
back edge指向祖先
<pre>
->
u為子孫, v為祖先: v.d <= u.d
v的所有子樹(包括u)visit完, v才會離開: u.f <= v.f
所以back edge: v.d ≤ u.d < u.f ≤ v.f
<-
v.d <= u.d: v比u早visit
u.f <= v.f: u比v早離開
所以v.d <= u.d < u.f <= v.f: (u, v)為back edge
</pre>
### c.
cross edge指向旁系
<pre>
->
u為非root點, v為旁系的點(非祖先非子孫但已visit): v.d < v.f
v的所有子樹visit完, v才離開, 之後才會visit u: v.d < v.f < u.d
所以cross edge: v.d < v.f < u.d < u.f
<-
v.d < v.f < u.d: v的visit在u之前完成
v.d < v.f < u.d < u.f: (u, v)為cross edge(否則u的visit會在v的visit內完成, 或相反)
</pre>
# P2
- [ ][name=民]

[CLRS 3rd] Exercise 22.4-3
## Topic
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|.
## Solution
Pseudocode

CHECK_CYCLE(graph, u){//graph's E < V-1, else it
    u.color = gray
    for v in Adj[u]
        if v is white
            v.parent = u
            CHECK_CYCLE(graph, v)
        else if u.parent != v
            print "Yes" //found cycle and quit
            return
    u.color = black
}

檢查一個無向圖有沒有cycle
若沒有cycle,graph最多只會有v-1個edges。
若有cycle, cycle最大也只會由v個edges所組成。
<ins>
|E| > |V| - 1必定有迴圈
|E| <= |V| - 1則不一定, 要做DFS確定 (O(|V| + |E|) = O(|V|))
</ins>
因此:

時間複雜度: $O(|V|)$

# P3
- [ ][name=民]

[CLRS 3rd] Exercise 22.5-2
## topic
Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5–7 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.


## Solution
### 1.we do the DFS to see the finishing time
我們先選擇q,接著走向s,v,w,到達w時,沒有點可以搜尋了所以就往回一直到q。
往回到q後,接著走t,x,z,到達z時,沒有點可以搜尋了所以往回到t。
往回到t後,接著走y,發現y也沒有點可以搜尋了,於是回到t再回到q。
這些點搜尋完後,再選擇一個沒有搜尋過的點,我們選擇r。
r開始搜尋,走到u發現沒有點可以搜尋了,接著回到r,結束DFS。
藉由點的結束時間(finishing time),我們將先結束搜尋的點放進stack。
### 2.we can get the stack below

### 3.we do another DFS with the graph reverse
先創建一個array,儲存strongly connected component。
接著我們藉由stack,先pop stack中top的點,也就是r,開始搜尋。
選擇r後,沒有點可以搜尋了,於是再pop stack中top的點,也就是u。
u也沒有點可以搜尋了,再pop stack中top的點,也就是q。
選擇q後,走向y,t, t沒有點可以搜尋了,回到y再回到q。
pop stack中top的點,找到x,x走向z又回到x。
pop stack中top的點,找到s,走向w,v。
v沒有可以搜尋的點,回到w再回到s,結束DFS。
### 4.we get the array of the reverse graph
將剛剛DFS中,只要找到點沒有其他可以搜尋的點,就將這些點放進array空間裡。
舉例來說,我們選擇r,而r並沒有其他可以搜尋的點,於是就將r放進array裡。
藉由上述的方法,得到

[r],[u],[q,y,t],[x,z],[s,w,v]

而這個結果就是graph裡所有的strongly connected component。
### 5.we get the simple graph of above

# P4
- [ ][name=Joe]

[CLRS 3rd] Exercise 22.5-7
## topic
A directed graph G=(V,E) is semiconnected if, for all pairs of vertices $u, v \in V$, we have $u \leadsto v$ or $v \leadsto u$. Give an efficient algorithm to determine whether or not G is semiconnected. Prove that your algorithm is correct, and analyze its running time.
## Solution
先找出所有的strongly-connected-components，然後做一次topological sorting做成DAG，最後從root開始檢查DAG，如果有分岔(out-degree>1)檢查其分歧後的SCC有沒有相通，如果都相通或沒有分岔則為semiconnected。
時間複雜度:$O=(V+E)$

semiconnected(G){
    SCC = strongly-connected-components(G)//find SCC in O(|V| + |E|)
    topological-sort(SCC) //turn SCC to DAG //adjacency list //O(|V| + |E|)
    while(DAG is not traveled)
        if(now_SCC out-degree==1)
            go on next SCC
        else if(now_SCC out-degree>1)
            check its childred are all connected or not //O(V+E)
            if(not connected)
                return false
    return true
}

# P5
- [ ][name=Joe]
## topic
A DFS forest can be generated by perform DFS on a directed graph. There are 4 types of edges in a DFS forest: tree edge, forward edge, back edge and cross edge. Modify DFS so that it can determine the type of each edge
## Solution
tree edge:travel到未發現的vetice(白色)
back edge:travel到被發現但未完成的vertice(灰色)
forward edge:travel到已經完成的vertice(黑色)
cross edge:travel到其他tree的edge(另一棵tree不會指向這個tree 黑色)

DFS_tree(graph){
    tree_number[v]
    struct edge{start_vertice,end vertice,edge_type}
    while(not travel all vertices)
        do DFS on graph
             if(end_vertice_color is white)
                edge_type=tree_edge
              else if(end_vertice_color is gray)
                edge_type=back_edge
              else if(end_vertice_color is black)
                if (end_vertice.d < start_vertice.d)// vertice.d is discover time
                    edge_type=forward_edge
                else
                    edge_type=cross_edge
        travel to next vertice  //next tree
}

# P6
- [ ][name=賴]
## topic
在投影片Unit 7 P. 39的地方有提到另一個DFS的實作，但其輸出的order可能 會不同，試問該DFS的實作是否可以用來解Topological Sorting以及StronglyConnected-Components?
## Solution
### Topological Sorting
只要能依次輸出in degree為0的點, 就能解Topological Sorting

topo (){ 
    Q is a stack 
    Q.push(all 0 in-degree node)
    while(!Q.empty())
        u = Q.pop() 
        for v in Adj[u]
            if v hasn't been reached
                mark v as reached
                Q.push(v)
        output Q       
    }
}

輸出順序為 7 6 5 4 3 2 1 0
### Strongly Connected-Components
雖然輸出順序不同, 但是StronglyConnected-Components是由輸入決定的, 所以無論DFS的順序為何, 都能找到正確的StronglyConnected-Components

DFS(Graph){
    u= stack.pop();
    for each v belongs to Adj[u]
        if v hasn't yet been reached 
            mark v as reached
            stack.push(v)
    Q.push(u);
}

SCC(){
    Q and stack are empty stack
    
    DFS(G)//get the result of the first DFS 
    calculate GT (transpose of the graph)
    while (Q.top()!=empty){
        stack.push(Q.top());
        DFS(GT);//write the result of traversal in array
        while(Q.top() is written into array)
            Q.pop();
     }
    output->array;
}

# P7
- [ ][name=天]
## topic
Given an undirected graph G = (V, E), if we remove the cut-vertex, the graph will be disconnected. Design an algorithm to find the set of cut-vertices.
## Solution

DFS(G);                      //先求depth
Find(){                      //找cut-vertex
    v from 1 to n
       low[v]=depth[v]
    v from n to 1            //逆遍歷次序
       for each u 屬於 Adj[v]
          if(u!=parent[v])
             low[v]=min(low[v],low[u])    //low[v]:v所在的環裡最小的depth
          if(depth[v]<=low[u])
             cut_vertex <- v
    if(children[0]>=2)                //root
       cut_vertex <- 0
}