python 邻接表

邻接表是一种表示图的数据结构，它使用链表来表示每个顶点连接到的其他顶点。在Python中，可以使用字典来实现邻接表。具体实现方法如下：

1. 创建一个空字典来存储图中的所有顶点及其连接的其他顶点和权重。

2. 创建一个顶点类，其中包含顶点的名称和连接到的其他顶点及其权重。

3. 在顶点类中，使用字典来存储连接到的其他顶点及其权重。

4. 在图类中，使用字典来存储所有顶点及其对应的顶点对象。

5. 在图类中，使用add_vertex方法向图中添加新的顶点。

6. 在图类中，使用add_edge方法向图中添加新的边，即连接两个顶点。

7. 在图类中，使用get_vertex方法获取指定名称的顶点对象。

以下是一个简单的Python实现示例：

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connected_to = {}

    def add_neighbor(self, neighbor, weight=0):
        self.connected_to[neighbor] = weight

    def get_connections(self):
        return self.connected_to.keys()

    def get_weight(self, neighbor):
        return self.connected_to[neighbor]

    def __str__(self):
        return str(self.id) + ' connected to: ' + str([x.id for x in self.connected_to])

class Graph:
    def __init__(self):
        self.vert_list = {}
        self.num_vertices = 0

    def add_vertex(self, key):
        self.num_vertices += 1
        new_vertex = Vertex(key)
        self.vert_list[key] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.vert_list:
            return self.vert_list[n]
        else:
            return None

    def add_edge(self, f, t, weight=0):
        if f not in self.vert_list:
            self.add_vertex(f)
        if t not in self.vert_list:
            self.add_vertex(t)
        self.vert_list[f].add_neighbor(self.vert_list[t], weight)

    def get_vertices(self):
        return self.vert_list.keys()

    def __iter__(self):
        return iter(self.vert_list.values())

    def __str__(self):
        s = ''
        for v in self:
            for w in v.get_connections():
                s += f'{v.id} -> {w.id}\n'
        return s