c# - 在 C# 中克隆图形的算法

问题描述

给定连接无向图中节点的引用，返回图的深层副本（克隆）。图中的每个节点都包含一个 val (int) 和一个其邻居的列表 (List[Node])。

此代码中的错误是什么 - 克隆图形。它说

对象引用未设置为 LeetCode 中此行的对象实例 - target.Add(C);。

有人可以在这里分享一些建议。

public class Node {
    public int val;
    public IList<Node> neighbors;

    public Node(){}
    public Node(int _val,IList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;}

public class Solution {
      public Node CloneGraph(Node node) {
        if (node == null)
        {return null;}
    var map = new Dictionary<int, Node>();
       Queue<Node>  q = new Queue<Node>();
        q.Enqueue(node);
        Node newNode = new Node();
        newNode.val = node.val;
        CopyList(node.neighbors,newNode.neighbors);   

        map.Add(newNode.val, newNode);

        while(q.Count!=0)
        {
            Node head = q.Dequeue();
            Node cloneU = map[head.val];
            foreach (Node neighborNode in head.neighbors)
            {
                if(map.ContainsKey(neighborNode.val))
                {
                    CopyList(head.neighbors,cloneU.neighbors);            
                }
                else
                {
                    q.Enqueue(neighborNode);
                    Node neighborNodeCopy = new Node(neighborNode.val,neighborNode.neighbors);
                    map.Add(neighborNodeCopy.val, neighborNodeCopy);
                    CopyList(neighborNodeCopy.neighbors,cloneU.neighbors);                  
                }
            }
        }            
        return newNode;    
    }

    public void CopyList(IList<Node> source, IList<Node> target)
    {
        foreach( Node C in source)
        {
            target.Add(C);
        }
    }
}

标签： c#algorithmgraphclone

您看到的具体错误是由于target是null，并且您试图在其上调用方法 ( Add)。

要解决此问题，您可以target在尝试对其调用.Add方法之前设置一个新列表（如果它为空）：

public void CopyList(IList<Node> source, IList<Node> target)
{
    if (target == null) target = new List<Node>();

    foreach( Node C in source)
    {
        target.Add(C);
    }
}

System.Linq但是，这与使用扩展方法的单行代码版本相同， ToList“

public void CopyList(IList<Node> source, IList<Node> target)
{
    target = source?.ToList();
}

话虽如此，您似乎正在尝试制作的深层副本Node，但是当您这样做时target.Add(C);，您正在添加对源节点的引用而不是该节点的克隆。

对于深复制，我们需要对所有引用类型进行完整的复制，在的情况下Node，它唯一的引用类型是IList<Node>集合。创建深层副本的一种可能更简单的方法是在自身上实现一个Clone方法，该方法创建一个新的，然后创建一个包含列表中每个节点的克隆的新的：NodeNodeList<Node>

public class Node
{
    public int Value { get; set; }
    public IList<Node> Neighbors { get; set; }

    public Node() { }

    public Node(int val, IList<Node> neighbors)
    {
        Value = val;
        Neighbors = neighbors;
    }

    public Node Clone()
    {
        // Start with a new node with the same value
        var newNode = new Node { Value = Value };

        // Deep copy the list of neighbors by returning their clones in a new list
        newNode.Neighbors = Neighbors?.Select(node => node.Clone()).ToList();

        // Return our deep copy
        return newNode;
    }
}

c# - 在 C# 中克隆图形的算法

问题描述

解决方案

推荐阅读