LeetCode 133 Clone Graph

思路

【BFS遍历有向图（树）不需要visit，无向图上需要visit】
思路1：bfs遍历整张图，注意需要加上visit来判断节点是否被访问过。在放入queue的时候就标记visit。如果visit过，那么就在neighbor列表上加上它；否则就需要建立新node+建立映射+加入neighbor列表。

时间复杂度O(n+m)
空间复杂度O(n)

思路2:同样是bfs遍历整张图，不同的是：首先把所有的node保存下来，然后一个node一个node的建立边。

时间复杂度O(n+m)
空间复杂度O(n)

代码

思路1

/* // Definition for a Node. class Node {public int val;public List<Node> neighbors;public Node() {}public Node(int _val,List<Node> _neighbors) {val = _val;neighbors = _neighbors;} }; */
class Solution {
    public Node cloneGraph(Node node) {
    if (node == null) {
    return null;}Queue<Node> queue = new LinkedList<>();HashMap<Node, Node> map = new HashMap<>();HashSet<Node> visit = new HashSet<>();queue.offer(node);Node root = new Node(node.val, new ArrayList<>());map.put(node, root);visit.add(node);while (!queue.isEmpty()) {
    Node t = queue.poll();for (Node n : t.neighbors) {
    if (visit.contains(n)) {
    map.get(t).neighbors.add(map.get(n));} else {
    queue.offer(n);visit.add(n);Node newNode = new Node(n.val, new ArrayList<>());map.put(n, newNode);map.get(t).neighbors.add(newNode);}}}return root;}
}

思路2

/* // Definition for a Node. class Node {public int val;public List<Node> neighbors;public Node() {}public Node(int _val,List<Node> _neighbors) {val = _val;neighbors = _neighbors;} }; */
class Solution {
    public Node cloneGraph(Node node) {
    if (node == null) {
    return null;}List<Node> nodes = getNode(node);HashMap<Node, Node> map = new HashMap<>();// copying nodesfor (Node n : nodes) {
    map.put(n, new Node(n.val, new ArrayList<>()));}//copying edgesfor (Node n : nodes) {
    Node newNode = map.get(n);if (n.neighbors.size() == 0) {
    continue;}for (Node neigh : n.neighbors) {
    Node newNeighbor = map.get(neigh);newNode.neighbors.add(newNeighbor);}}return map.get(node);}public ArrayList getNode(Node node) {
    HashSet<Node> visit = new HashSet<>();Queue<Node> queue = new LinkedList<>();queue.offer(node);visit.add(node);while (!queue.isEmpty()) {
    Node t = queue.poll();for (Node n : t.neighbors) {
    if (!visit.contains(n)) {
    queue.offer(n);visit.add(n);}}}return new ArrayList<>(visit);}
}