在 Python 中使用邻接表构建节点图

Question

我有一个 Node class 如下

class Node:

    def __init__(self, val = 0, neighbors = None):

        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
    
    def __eq__(self, other) -> bool:
        
        if isinstance(other, self.__class__):
            return all([other.val == self.val, self.neighbors == other.neighbors])
        
        return False
    
    def __repr__(self):
        return f"Node(val: {self.val}, neighbors: {self.neighbors})"
    
    def __str__(self):
        return self.__repr__()

我正在尝试使用如下邻接表构建图：

[
 [2,4],
 [1,3],
 [2,4],
 [1,3]
]

在上述从 1 索引的邻接列表中，索引是 Node 值，即 Node.val，该索引处的列表是邻居，即 Node.neighbors

例如，对于索引 1：

Node.val = 1
Node.neighbors = [Node(2), Node(4)]

对于索引 2：

Node.val = 2
Node.neighbors = [Node(1), Node(3)]

等等...

我如何使用 python 构建图，我想在其中将邻接列表中由 index=1 表示的 Node 视为它的入口点，即根。

基本上是一个函数 returns 图的根：

def make_graph(adj_list: List) -> Node:
    ...

我试过迭代方法，导致无限循环或错误输出。

我的一次尝试导致输出错误：

def make_graph(adj_list: List) -> Node:
        
        if not adj_list:
            return []
        
        root = Node(1)
        node_dict = {}
        
        for i in adj_list[0]:
            neighbor = Node(i)
            root.neighbors.append(neighbor)
            node_dict[i] = neighbor
        
        node_dict[1] = root
        
        for i in range(1, len(adj_list)):
            
            node = Node(i) if i not in node_dict else node_dict[i]
            
            for neighbor in adj_list[i]:
                
                if neighbor not in node_dict:
                    neighbor_node = Node(neighbor)
                    node_dict[neighbor] = neighbor_node
                else:
                    neighbor_node = node_dict[neighbor]
                
                node.neighbors.append(neighbor_node)
                
            if i not in node_dict:
                node_dict[i] = node
                
        return root

给出输出：

Node(
    val: 1, 
    neighbors: [
        Node(
            val: 2,
            neighbors: [
                Node(
                    val: 2,
                    neighbors: [...]
                ),
                Node(
                    val: 4,
                    neighbors: []
                )
            ]
        ),
        Node(
            val: 4,
            neighbors: []
        ),
        Node(
            val: 1,
            neighbors: [...]
        ),
        Node(
            val: 3,
            neighbors: [
                Node(
                    val: 1,
                    neighbors: [...]
                ), 
                Node(val: 3,
                     neighbors: [...]
                )
            ]
        )
    ]
)

非常感谢任何形式的帮助或指出正确的方向。

Answer 1

如果您首先创建所有节点实例，然后通过将这些邻居编号映射到您随后可以使用的节点来填充邻居，将会更容易。

这是您可以使用的函数：

def make_graph(adj_list: List) -> Node:
    nodes = [Node(i + 1) for i in range(len(adj_list))]
    for i, neighbors in enumerate(adj_list):
        nodes[i].neighbors = [nodes[j-1] for j in neighbors]
    return nodes[0]

使用示例输入进行测试的代码：

from typing import List

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

    def __repr__(self):
        return f"Node(val: {self.val}, neighbors: {self.neighbors})"

def make_graph(adj_list: List) -> Node:
    nodes = [Node(i + 1) for i in range(len(adj_list))]
    for i, neighbors in enumerate(adj_list):
        nodes[i].neighbors = [nodes[j-1] for j in neighbors]
    return nodes[0]

adj_list = [[2,4],[1,3],[2,4],[1,3]]
node = make_graph(adj_list)

print(node)

在 Python 中使用邻接表构建节点图

Construct a graph of nodes using adjacency list in Python

python

graph

nodes

adjacency-list