10k

133. Clone Graph

Published on

topic

Given a graph with nodes as Nodes, deep copy it. That is, the structure of the copied graph and the value of each node are the same as the original graph, but the nodes are all new nodes and do not refer to any original nodes.

algorithm

This topic involves the entire graph, and the idea is to copy each node while maintaining their relative relationship (neighbors) during the traversal process. The graph can be traversed using DFS or BFS algorithms.

code

/*
// Definition for a Node.
class Node {
     public int val;
     public List<Node> neighbors;
     public Node() {
         val = 0;
         neighbors = new ArrayList<Node>();
     }
     public Node(int _val) {
         val = _val;
         neighbors = new ArrayList<Node>();
     }
     public Node(int _val, ArrayList<Node> _neighbors) {
         val = _val;
         neighbors = _neighbors;
     }
}
*/

class Solution {
     public Node cloneGraph(Node node) {
         if (node == null) return null;
         Map<Node, Node> map = new HashMap<>();
         Node newNode = new Node(node. val);
         map. put(node, newNode);
         Stack<Node> stack = new Stack();
         stack. push(node);
         while (!stack. isEmpty()) {
             Node cur = stack. pop();
             Node newCur = map. get(cur);
             for (Node neighbor : cur. neighbors) {
                 if (!map. containsKey(neighbor)) {
                     map.put(neighbor, new Node(neighbor.val));
                     stack.push(neighbor);
                 }
                 newCur.neighbors.add(map.get(neighbor));
             }
            
         }
         return newNode;
     }
}

Implementation of recursion and iteration of DFS and BFS

DFS

GraphNode represents the graph

recursion
package graph;

import java.util.HashSet;


public class RecursionGraphDFS {
     public static void dfs(GraphNode node) {
         dfs(node, new HashSet<GraphNode>());
     }

     private static void dfs(GraphNode node, HashSet visited) {
         System.out.println(node.val);
         visited. add(node);
         for (GraphNode neighbor : node. neighbors) {
             if (!visited. contains(neighbor)) {
                 dfs(neighbor, visited);
             }
         }
     }

     public static void main(String[] args) {
         GraphNode root = constructGraph();
         dfs(root); // 0, 1, 2, 4, 3, 5
     }

     private static GraphNode constructGraph() {
         GraphNode node0 = new GraphNode(0);
         GraphNode node1 = new GraphNode(1);
         GraphNode node2 = new GraphNode(2);
         GraphNode node3 = new GraphNode(3);
         GraphNode node4 = new GraphNode(4);
         GraphNode node5 = new GraphNode(5);
         node0.neighbors.add(node1);
         node0.neighbors.add(node3);
         node0.neighbors.add(node5);

         node1.neighbors.add(node0);
         node1.neighbors.add(node2);
         node1.neighbors.add(node4);

         node2.neighbors.add(node1);
         node2.neighbors.add(node4);

         node3.neighbors.add(node0);
         node3.neighbors.add(node4);

         node4.neighbors.add(node1);
         node4.neighbors.add(node3);
         node4.neighbors.add(node2);

         node5.neighbors.add(node0);
         return node0;
     }
}
iteration
package graph;

import java.util.HashSet;
import java.util.Stack;


public class IterationGraphDFS {
     public static void dfs(GraphNode node) {
         HashSet<GraphNode> visited = new HashSet<>();
         Stack<GraphNode> stack = new Stack<>();
         visited. add(node);
         stack. add(node);
         while (!stack. isEmpty()) {
             GraphNode cur = stack. pop();
             System.out.println(cur.val);
             for (GraphNode neighbor : cur. neighbors) {
                 if (!visited. contains(neighbor)) {
                     visited. add(neighbor);
                     stack.push(neighbor);
                 }
             }
         }
     }


     public static void main(String[] args) {
         GraphNode root = constructGraph();
         dfs(root); // 0, 5, 3, 4, 2, 1
     }

     private static GraphNode constructGraph() {
         GraphNode node0 = new GraphNode(0);
         GraphNode node1 = new GraphNode(1);
         GraphNode node2 = new GraphNode(2);
         GraphNode node3 = new GraphNode(3);
         GraphNode node4 = new GraphNode(4);
         GraphNode node5 = new GraphNode(5);
         node0.neighbors.add(node1);
         node0.neighbors.add(node3);
         node0.neighbors.add(node5);

         node1.neighbors.add(node0);
         node1.neighbors.add(node2);
         node1.neighbors.add(node4);

         node2.neighbors.add(node1);
         node2.neighbors.add(node4);

         node3.neighbors.add(node0);
         node3.neighbors.add(node4);

         node4.neighbors.add(node1);
         node4.neighbors.add(node3);
         node4.neighbors.add(node2);

         node5.neighbors.add(node0);
         return node0;
     }
}

Matrix representation graph (adjacency matrix)

recursion
package Graph;


public class RecursionMatrixDFS {

    public static void main(String[] args) {
        int[][] matrix = constructMatrix();
        dfs(matrix); // 0, 1, 2, 4, 3, 5
    }

    private static void dfs(int[][] matrix, int[] visited, int vertex) {
        System.out.println(vertex);
        visited[vertex] = 1;
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[vertex][j] == 1) {
                if (visited[j] == 0) {
                    dfs(matrix, visited, j);
                }
            }
        }
    }

    private static void dfs(int[][] matrix) {
        int[] visited = new int[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            if (visited[i] == 0) {
                dfs(matrix, visited, i);
            }
        }
    }

    private static int[][] constructMatrix() {
        int[][] matrix = new int[6][6];
        matrix[0] = new int[]{0, 1, 0, 1, 0, 1};
        matrix[1] = new int[]{1, 0, 1, 0, 1, 0};
        matrix[2] = new int[]{0, 1, 0, 0, 1, 0};
        matrix[3] = new int[]{1, 0, 0, 0, 1, 0};
        matrix[4] = new int[]{0, 1, 1, 1, 0, 0};
        matrix[5] = new int[]{1, 0, 0, 0, 0, 0};
        return  matrix;
    }
}
Iteration
package Graph;

import java.util.Stack;


public class IterationMatrixDFS {

    public static void main(String[] args) {
        int[][] matrix = constructMatrix();
        dfs(matrix); // 0, 5, 3, 4, 2, 1
    }

    private static void dfs(int[][] matrix) {
        int[] visited = new int[matrix.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < matrix.length; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                stack.push(i);
                while (!stack.isEmpty()) {
                    int vertex = stack.pop();
                    System.out.println(vertex);
                    for (int j = 0; j < matrix.length; j++) {
                        if (matrix[vertex][j] == 1) {
                            if (visited[j] == 0) {
                                stack.push(j);
                                visited[j] = 1;
                            }
                        }
                    }
                }
            }
        }
    }

    private static int[][] constructMatrix() {
        int[][] matrix = new int[6][6];
        matrix[0] = new int[]{0, 1, 0, 1, 0, 1};
        matrix[1] = new int[]{1, 0, 1, 0, 1, 0};
        matrix[2] = new int[]{0, 1, 0, 0, 1, 0};
        matrix[3] = new int[]{1, 0, 0, 0, 1, 0};
        matrix[4] = new int[]{0, 1, 1, 1, 0, 0};
        matrix[5] = new int[]{1, 0, 0, 0, 0, 0};
        return  matrix;
    }
}

BFS

GraphNode represents the graph

Iteration
package Graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class IterationGraphBFS {

    public static void bfs(GraphNode root) {
        HashSet<GraphNode> visited = new HashSet<>();
        Queue<GraphNode> queue = new LinkedList<>();
        visited.add(root);
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            System.out.println("level:" + String.valueOf(level++));
            for (int i = 0; i < size; i++) {
                GraphNode node = queue.poll();
                System.out.println(node.val);
                for (GraphNode neighbor : node.neighbors) {
                    if (!visited.contains(neighbor)) {
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        GraphNode root = constructGraph();
        bfs(root); //0, 1, 3, 5, 2, 4
    }

    private static GraphNode constructGraph() {
        GraphNode node0 = new GraphNode(0);
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);
        GraphNode node5 = new GraphNode(5);
        node0.neighbors.add(node1);
        node0.neighbors.add(node3);
        node0.neighbors.add(node5);

        node1.neighbors.add(node0);
        node1.neighbors.add(node2);
        node1.neighbors.add(node4);

        node2.neighbors.add(node1);
        node2.neighbors.add(node4);

        node3.neighbors.add(node0);
        node3.neighbors.add(node4);

        node4.neighbors.add(node1);
        node4.neighbors.add(node3);
        node4.neighbors.add(node2);

        node5.neighbors.add(node0);
        return node0;
    }
}

Matrix representation graph (adjacency matrix)

Iteration
package Graph;

import java.util.LinkedList;
import java.util.Queue;


public class IterationMatrixBFS {
    public static void main(String[] args) {
        int[][] matrix = constructMatrix();
        bfs(matrix); //0, 1, 3, 5, 2, 4
    }

    private static void bfs(int[][] matrix) {
        int[] visited = new int[matrix.length];
        Queue<Integer> queue = new LinkedList<>();
        int level = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int size = queue.size();
                    System.out.println("level:" + String.valueOf(level++));
                    for (int x = 0; x < size; x++) {
                        int vertex = queue.poll();
                        System.out.println(vertex);
                        for (int j = 0; j < matrix[vertex].length; j++) {
                            if (matrix[vertex][j] == 1) {
                                if (visited[j] == 0) {
                                    visited[j] = 1;
                                    queue.offer(j);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    private static int[][] constructMatrix() {
        int[][] matrix = new int[6][6];
        matrix[0] = new int[]{0, 1, 0, 1, 0, 1};
        matrix[1] = new int[]{1, 0, 1, 0, 1, 0};
        matrix[2] = new int[]{0, 1, 0, 0, 1, 0};
        matrix[3] = new int[]{1, 0, 0, 0, 1, 0};
        matrix[4] = new int[]{0, 1, 1, 1, 0, 0};
        matrix[5] = new int[]{1, 0, 0, 0, 0, 0};
        return  matrix;
    }
}

题目

给一个以节点为Node的图，deep copy它。即复制出来的图的结构以及每个节点的数值和原图一样，但是节点都是新节点，不引用原来任何的节点。

算法

这个题目涉及到整个图，思路是在遍历过程中，对每一个节点进行复制，同时维护他们的相对关系（邻居）。使用DFS或者BFS算法都可以遍历图。

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node newNode = new Node(node.val);
        map.put(node, newNode);
        Stack<Node> stack = new Stack();
        stack.push(node);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            Node newCur = map.get(cur);
            for (Node neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) {
                    map.put(neighbor, new Node(neighbor.val));
                    stack.push(neighbor);
                }
                newCur.neighbors.add(map.get(neighbor));
            }
            
        }
        return newNode;
    }
}

DFS和BFS的递归和迭代的实现

参考上文英文版本

Thoughts? Leave a comment