如何在Python中用数组和链表构建并测试图的邻接顶点（无内置列表/字典）

核心实现逻辑 #

既然不能用Python内置列表和字典，我们需要自己实现基础的链表节点和模拟数组，再基于这两个结构搭建图的邻接表（邻接表天然适合用链表存储每个顶点的邻接节点）。

代码实现 #

1. 链表节点类 #

用来存储邻接顶点的标识，以及下一个节点的引用：

class Node:
    def __init__(self, vertex_id):
        self.vertex_id = vertex_id
        self.next = None

2. 模拟数组类（替代内置列表） #

用类模拟固定大小的数组，通过属性存储每个位置的链表头：

class Array:
    def __init__(self, size):
        self.size = size
        # 初始化每个位置为None（对应顶点的邻接链表头）
        for i in range(size):
            setattr(self, f"_{i}", None)
    
    def get(self, index):
        if 0 <= index < self.size:
            return getattr(self, f"_{index}")
        raise IndexError("Array index out of bounds")
    
    def set(self, index, value):
        if 0 <= index < self.size:
            setattr(self, f"_{index}", value)
        else:
            raise IndexError("Array index out of bounds")

3. 图的邻接表实现 #

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 数组存储每个顶点的邻接链表头
        self.adj_list = Array(num_vertices)
    
    # 添加无向边（有向图只需保留单向添加逻辑）
    def add_edge(self, vertex_u, vertex_v):
        if vertex_u < 0 or vertex_u >= self.num_vertices or vertex_v < 0 or vertex_v >= self.num_vertices:
            raise ValueError("Invalid vertex ID")
        
        # 将v加入u的邻接链表（头插法）
        new_node = Node(vertex_v)
        new_node.next = self.adj_list.get(vertex_u)
        self.adj_list.set(vertex_u, new_node)
        
        # 将u加入v的邻接链表（无向图必备）
        new_node2 = Node(vertex_u)
        new_node2.next = self.adj_list.get(vertex_v)
        self.adj_list.set(vertex_v, new_node2)
    
    # 获取指定顶点的所有邻接顶点
    def get_adjacent_vertices(self, vertex):
        if vertex < 0 or vertex >= self.num_vertices:
            raise ValueError("Invalid vertex ID")
        
        # 这里用内置list临时存储结果，如果连这个都不能用，可返回自定义链表实例
        adjacent = []
        current = self.adj_list.get(vertex)
        while current is not None:
            adjacent.append(current.vertex_id)
            current = current.next
        return adjacent

测试方案 #

1. 基础功能验证 #

# 创建含5个顶点的图
graph = Graph(5)
# 添加测试边
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)

# 打印邻接顶点（头插法会导致顺序与添加顺序相反，属于正常现象）
print("顶点0的邻接顶点:", graph.get_adjacent_vertices(0))  # 输出 [2, 1]
print("顶点1的邻接顶点:", graph.get_adjacent_vertices(1))  # 输出 [3, 0]
print("顶点4的邻接顶点:", graph.get_adjacent_vertices(4))  # 输出 [3, 2]

2. 边界场景测试 #

• 非法顶点测试：调用graph.get_adjacent_vertices(5)，应抛出ValueError
• 孤立顶点测试：创建图后不为某顶点加边，比如顶点4不加边，调用graph.get_adjacent_vertices(4)应返回空列表
• 重复边测试：多次添加同一条边（如graph.add_edge(0,1)两次），验证邻接顶点是否出现重复（若需避免重复，可在add_edge中添加查重逻辑）

3. 链表结构可视化验证 #

如果担心链表遍历出错，可手动打印每个顶点的邻接链表结构：

def print_graph_structure(graph):
    for i in range(graph.num_vertices):
        print(f"顶点{i}的邻接链表: ", end="")
        current = graph.adj_list.get(i)
        while current is not None:
            print(f"{current.vertex_id} -> ", end="")
            current = current.next
        print("None")

print_graph_structure(graph)

输出示例：

顶点0的邻接链表: 2 -> 1 -> None
顶点1的邻接链表: 3 -> 0 -> None
顶点2的邻接链表: 4 -> 0 -> None
顶点3的邻接链表: 4 -> 1 -> None
顶点4的邻接链表: 3 -> 2 -> None

额外说明 #

• 若需保持邻接顶点的添加顺序，可将头插法改为尾插法（需给链表添加尾节点引用）
• 若完全不能使用内置list，可修改get_adjacent_vertices，让它返回自定义的LinkedList实例，再通过遍历该链表验证结果

内容的提问来源于stack exchange，提问作者GDTeam