广度优先搜索实现克隆图

Question

力扣133题，克隆图

import collections
class Node:
    def __init__(self,val,alist):
        self.val = val     #存储这个节点的值
        self.neighbors = alist    #这个节点的邻接点
class Solution:
    def cloneGraph(self,node):   #node为第一个节点的引用
        if not node:
            return node
        visited = dict()     #visited为哈希表，用来存储原图中被访问过的节点和克隆图中对应节点，键值对为 原图中被访问过的节点：克隆图中对应节点
        queue = collections.deque()
        visited[node] = Node(node.val,[])   #克隆第一个节点并存储到哈希表中
        queue.append(node)   #将起始节点放入队列中
        while queue:
            node_u = queue.popleft()    #从队列中取出左边第一个节点
            for node_v in node_u.neighbors:
                if node_v not in visited:   #遍历该节点的所有未访问节点
                    visited[node_v] = Node(node_v.val,[])
                    queue.append(node_v)
                visited[node_u].neighbors.append(visited[node_v])
        return visited[node]   #返回起始节点的克隆节点

我觉得官方解释没有给Node类，所以我自己补了一个
Solution里面的node为第一个节点的引用，每个节点既有值，又有邻接节点列表，具体是什么形式呢，
还有要怎么调用这个函数啊？
快b溃了

Answer 1

【以下回答由 GPT 生成】

首先，让我们解释一下Node类的具体形式。Node类表示图中的一个节点，具有以下属性：

• val：节点的值，可以是任意类型的数据。
• neighbors：节点的邻接节点列表，是一个包含其他节点的列表。注意，这里的邻接节点是指与当前节点有直接连接的节点。

接下来，我们来优化代码实现克隆图的函数。我们可以使用广度优先搜索来克隆整个图。以下是优化后的代码：

import collections

class Node:
    def __init__(self, val=None, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

class Solution:
    def cloneGraph(self, node):
        if not node:
            return node

        visited = {}     # visited为哈希表，用来存储原图中被访问过的节点和克隆图中对应节点
        queue = collections.deque()
        visited[node] = Node(node.val)   # 克隆第一个节点并存储到哈希表中
        queue.append(node)   # 将起始节点放入队列中

        while queue:
            node_u = queue.popleft()    # 从队列中取出左边第一个节点
            cloned_node_u = visited[node_u]

            for node_v in node_u.neighbors:
                if node_v not in visited:   # 遍历该节点的所有未访问节点
                    visited[node_v] = Node(node_v.val)
                    queue.append(node_v)
                cloned_node_u.neighbors.append(visited[node_v])

        return visited[node]   # 返回起始节点的克隆节点

这里我们对代码进行了一些改进：

1. 将Node类的构造函数更改为可选的val和neighbors参数，使得在创建节点对象时更加灵活。
2. 将visited的默认类型更改为普通字典，而不是collections.defaultdict。
3. 在克隆节点时，只克隆节点的值，而不是整个节点对象。

现在，让我们来看看如何调用这个函数来实现克隆图。假设我们有一个如下所示的图：

1 -- 2
|    |
4 -- 3

我们可以使用以下代码创建并克隆这个图：

# 创建节点对象
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

# 建立邻接关系
node1.neighbors = [node2, node4]
node2.neighbors = [node1, node3]
node3.neighbors = [node2, node4]
node4.neighbors = [node1, node3]

# 创建Solution对象并调用cloneGraph函数
solution = Solution()
cloned_graph = solution.cloneGraph(node1)

现在，cloned_graph将是原始图的克隆。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7775869

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^