Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

codingpineapple
codingpineapple

Posted on

     

LeetCode 133. Clone Graph(javascript solution)

Description:

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// DFS approachvarcloneGraph=function(node){// Nodes we have already copiedconstvisited={};// DFS function to copy graphconstdfs=(node)=>{if(!node)returnnode;// If we have seen this node before, return itif(visited[node.val]!=null)returnvisited[node.val];// Create base for copied nodeconstroot=newNode(node.val);// Add this copied node to group of nodes we hav copiedvisited[node.val]=root;// Add copied neighbors to the current copied nodenode.neighbors.forEach(n=>root.neighbors.push(dfs(n)))returnroot;}// Return new copied graphreturndfs(node);};
Enter fullscreen modeExit fullscreen mode

Top comments(1)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss
CollapseExpand
 
qurashieman profile image
Tuba Inam
  • Joined

I found that solution is very popular and helpful:youtu.be/t9pj1Ail2z4

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

  • Joined

More fromcodingpineapple

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp