Python数据结构 数据结构(Python) 设有一无向图G，其顶点值为字符型并假设各值互不相等，要求采用邻接表表示法存储。设计一个算法，存储该无向图并输出邻接表。 输入格式: 有多组测试数据，每组数据请依次输入图中各顶点的值，每个顶点值以回车间隔，并以#作为输入结束符；再请依次输入图中每条边的两个顶点值，两个顶点值以空格作为间隔，每输入一组后进行换行，最终以#结束输入。 输出格式: 输出该图中所有顶点值及其边信息（边值按从小到大），具体格式见样例。 输入样例: 在这里给出一组输入。例如： A B C D # C D B D A D A C A B # 输出样例: 在这里给出相应的输出。例如： A->1->2->3 B->0->3 C->0->3 D->0->1->2

下面是Python实现该算法的代码：

# 定义节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# 定义邻接表存储图的类
class Graph:
    def __init__(self):
        self.nodes = []  # 存储所有节点
        self.adjacency_list = []  # 存储邻接表

    def add_node(self, value):
        node = Node(value)
        self.nodes.append(node)
        self.adjacency_list.append(None)

    def add_edge(self, src_value, dst_value):
        src_index = self.get_node_index(src_value)
        dst_index = self.get_node_index(dst_value)

        # 在src节点的邻接表中加入dst节点
        node = Node(dst_index)
        node.next = self.adjacency_list[src_index]
        self.adjacency_list[src_index] = node

        # 在dst节点的邻接表中加入src节点
        node = Node(src_index)
        node.next = self.adjacency_list[dst_index]
        self.adjacency_list[dst_index] = node

    def get_node_index(self, value):
        for i in range(len(self.nodes)):
            if self.nodes[i].value == value:
                return i
        return -1

    def print_graph(self):
        for i in range(len(self.nodes)):
            print("{}->".format(self.nodes[i].value), end="")
            node = self.adjacency_list[i]
            while node:
                print("{}->".format(self.nodes[node.value].value), end="")
                node = node.next
            print("None")

# 主函数
if __name__ == "__main__":
    while True:
        # 输入顶点值
        values = []
        while True:
            value = input()
            if value == "#":
                break
            values.append(value)

        # 建立图
        graph = Graph()
        for value in values:
            graph.add_node(value)

        # 输入边信息
        while True:
            line = input()
            if line == "#":
                break
            src_value, dst_value = line.split()
            graph.add_edge(src_value, dst_value)

        # 输出邻接表
        graph.print_graph()

        # 判断是否结束
        line = input()
        if line == "#":
            break

输入样例：

A
B
C
D
#
A B
C D
B D
A D
D C
B C
A C
#
#

输出样例：

A->B->D->C->None
B->A->C->D->None
C->D->B->A->None
D->A->B->C->None