[L 外商面試題] Detect Cycle in a Directed Graph

題目

給有向圖,找出是否有「環 Cycle」存在

範例: v1 v2: 表示 v1 指向 v2
0 1 
0 2 
0 5
1 2
1 3
2 3
4 0 
5 4

return true

思路

用 DFS 走訪每個點,再用 array(以下程式碼用 recTraverse) 記錄每個點走訪,當二次走到時就代表有 cycle 了

程式碼

class Solution {
    
    let count: Int
    var adjList = [[Int]]()
    init(count:Int) {
        self.count = count
        for _ in 0..<count {
            adjList.append([])
        }
    }
    
    func addEdge(v:Int, w:Int) {
        adjList[v].append(w) // Add w to v’s list.
    }
    
    func isCyclicUtil(_ v:Int, _ visited:inout [Bool], _ recTraverse: inout[Bool]) -> Bool {
        if visited[v] == false {
            // Mark the current node as visited and part of recursion stack
            visited[v] = true
            recTraverse[v] = true
            
            for i in adjList[v] {
                print("traverse from \(v) -> \(i)")
                if !visited[i] && isCyclicUtil(i, &visited, &recTraverse) {
                    return true
                } else if recTraverse[i] == true{          
                    return true
                }
            }
        }        
        recTraverse[v] = false  // remove the vertex from recursion stack
        return false
    }
    
    func isCyclic() -> Bool {
        
        var visited:[Bool] = Array(repeating: false, count: count)
        var stack:[Bool] = Array(repeating: false, count: count)
        
        for i in 0..<count {
            if !visited[i] && isCyclicUtil(i, &visited, &stack) {               
                return true
            }
        }
        return false
    }
}
var s = Solution(count: 6)
s.addEdge(v: 0, w: 1)
s.addEdge(v: 0, w: 2)
s.addEdge(v: 0, w: 5)
s.addEdge(v: 1, w: 2)
s.addEdge(v: 1, w: 3)
s.addEdge(v: 2, w: 3)
s.addEdge(v: 4, w: 0)
s.addEdge(v: 5, w: 4)

s.isCyclic() // true 0->5->4->0

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *