Question:
How to clone an undirected graph using Java

Summary

Here it implements a solution to clone a graph represented by a set of unconnected nodes. 

In this case, we are implementing the depth-first search (DFS) algorithm to replicate a graph, which is represented by a collection of connected nodes.


Solutions

//User function Template for Java



/*

    class Node{

        int val;

        ArrayList<Node> neighbors;

        public Node(){

            val = 0;

            neighbors = new ArrayList<>();

        }

    

        public Node(int val){

            this.val = val;

            neighbors = new ArrayList<>();

        }

    

        public Node(int val, ArrayList<Node> neighbors){

            this.val = val;

            this.neighbors = neighbors;

        }

    }

*/

class Solution{

    Node cloneGraph(Node node){

        

        Node start = node;

        HashSet<Node> visited = new HashSet<>();

        HashMap<Node,Node> map = new HashMap<>();

        dfs(start,visited,map);

        

        addEdges(map);

        

        return map.get(start);

        

    }

    public static void addEdges(HashMap<Node,Node> map){

        for(Map.Entry m : map.entrySet()){

            Node ori = (Node) m.getKey();

            map.get(m.getKey()).neighbors.add(ori);

        }

    }

    

    public static void dfs(Node start,HashSet<Node> visited,HashMap<Node,Node> map){

        

        visited.add(start);

        Node copyNode = new Node(start.val);

        map.put(start,copyNode);

        for(Node p : start.neighbors){

            if(!visited.contains(p)){

                dfs(p,visited,map);

            }

        }

        

    }

}


Explanation

  • This class represents a node in the graph.

  • It has an integer val representing the value of the node, and an ArrayList<Node> called neighbors, representing the neighboring nodes.


Solution class

  • This class contains the cloneGraph method, which clones the input graph.

  • It takes a Node object representing the starting node of the original graph.


dfs method

  • This method performs a depth-first search traversal of the original graph.


addEdges method

  • This method adds edges to the cloned nodes based on the mappings stored in the map HashMap.


Answered by:> >mogilimanikanta5555

Credit:> >GeekforGeeks


Suggested blogs:

>How to detect whether the linked list has a loop using Java

>How to determine the number of valid groupings for a string using Java

>How to mock a constant value in Python?

>Creating a pivot table by 6 month interval rather than year

>How to Install mariaDB client efficiently inside docker?

>Can I call an API to find out the random seed in Python `hash()` function?

>How remove residual lines after merge two regions using Geopandas in python?


Submit
0 Answers
Top Questions
21-02-2024

Calculating the Nth Fibonacci Number

06-03-2024

How to remove duplicates from an array in place using Java?

14-02-2024

How to check whether all leaves are at the same level using Java

12-03-2024

How to split Array into the largest sum using Java

05-02-2024

How to check whether a string is Panagram or not using Java

Related Questions

How to find Missing And Repeating numbers in an array?
img
How to check whether all leaves are at the same level using Java
img
How to solve array pair sum divisibility problem using Java
img
Check if strings are rotations of each other or not with Java
img
Finding all possible permutations of a given string using Java
img

What Our Clients Say About Us

Client satisfaction is our ultimate goal. Here are some kind words of our precious clients they have used to express their satisfaction with our service.

Why Choose Us ?

We endow businesses with flexible engagement models based on their unique needs. Our strength lies in state-of-the-art technology and affordable consulting services. Try us for fast POCs, full-fledged applications, or technology consulting. Always available for your service.