Swift solution - DFS, BFS


  • 0
    class Solution {
        func cloneGraph(_ node: UndirectedGraphNode?) -> UndirectedGraphNode? {
            var map = [Int: UndirectedGraphNode]()
            return DFS(node, &map)
        }
        
        private func DFS(_ node: UndirectedGraphNode?, _ map: inout [Int: UndirectedGraphNode]) -> UndirectedGraphNode? {
            guard let node = node else {
                return nil
            }
            
            if map.keys.contains(node.label) {
                return map[node.label]
            }
            
            var clone = UndirectedGraphNode(node.label)
            map[clone.label] = clone
            for neighbor in node.neighbors {
                if let node = DFS(neighbor, &map) {
                    clone.neighbors.append(node)
                }
            }
            
            return clone
        }
        
        func cloneGraph_BFS(_ node: UndirectedGraphNode?) -> UndirectedGraphNode? {
            guard let node = node else {
                return nil
            }
            
            let newNode = UndirectedGraphNode(node.label)
            var map = [Int: UndirectedGraphNode]()
            var queue = [node]
    
            map[newNode.label] = newNode
            while !queue.isEmpty {
                let node = queue.removeFirst()
                for neighbor in node.neighbors {
                    if !map.keys.contains(neighbor.label) {
                        map[neighbor.label] = UndirectedGraphNode(neighbor.label)
                        queue.append(neighbor)
                    }
                    map[node.label]?.neighbors.append(map[neighbor.label]!)
                }
            }
            
            return newNode
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.