克隆图

题目链接: https://leetcode.cn/problems/clone-graph

解题思路：

1. 深度遍历图，从queue中取出待遍历节点，对每个节点的Neighbors进行遍历，对于每个neighbor

2. 判断每个neighbor是否为之前遍历过，若遍历过，则从tmpMap中取出克隆节点，加入临时的neighbors中

3. 否则，构建一个克隆节点，并存入tmpMap及queue中，加入neighbors中

4. 将临时neighbors赋值给当前的节点在tmpMap中的克隆节点

5. 直至queue为空

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
    if node==nil{
        return nil
    }
	res := &Node{Val: node.Val}
	tmpMap := map[*Node]*Node{node.Val: res}
	queue := []*Node{node}
	for len(queue) > 0 {
		item := queue[0]
		queue = queue[1:]
		neighbors := make([]*Node, len(item.Neighbors))
		for idx, sub := range item.Neighbors {
			if tmpMap[sub.Val] != nil {
				neighbors[idx] = tmpMap[sub.Val]
			} else {
				subNode := &Node{Val: sub.Val}
				tmpMap[subNode.Val] = subNode
				neighbors[idx] = subNode
				queue = append(queue, sub)
			}
		}
        tmpMap[item.Val].Neighbors=neighbors
	}
	return res
}

复杂度分析

• 时间复杂度： 时间复杂度为$O(n)$,$n$为图的节点个数
• 空间复杂度： 空间复杂度为$O(n)$,$n$为图的节点个数