我有一个Node
类如下
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 构建图表,我想在其中考虑Node
邻接表中的index=1表示它是它的入口点,即根。
基本上是一个返回图的根的函数:
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: [...]
)
]
)
]
)
任何形式的帮助或指向正确方向的指示都非常感谢。