图（Graph）简单表示

# /*
# 图（Graph）简单表示
# --------------------------------------------------------
# 概念：
# 图由“顶点（Vertex）”和“边（Edge）”组成。
# 分类：
# - 有向图 / 无向图
# - 带权图 / 无权图
#
# 存储方式：
# 1) 邻接矩阵（适合稠密图）
# 2) 邻接表（适合稀疏图）
#
# 以下示例使用邻接表表示无向图。
# */

# 图的邻接表表示
class Graph:
    def __init__(self):
        self.adj_list = {}   # 使用字典存储邻接表

    # 添加顶点
    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []

    # 添加边（无向）
    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.add_vertex(u)
        if v not in self.adj_list:
            self.add_vertex(v)
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # 无向图双向添加

    # 打印图
    def display(self):
        for vertex, neighbors in self.adj_list.items():
            print(f"{vertex} -> {neighbors}")


# --------------------------------------------------------
# 示例操作
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")

print("图的邻接表表示：")
g.display()

# --------------------------------------------------------
# 要点总结：
# 1) 图包含顶点和边，可有向或无向；
# 2) 邻接表存储稀疏图更节省空间；
# 3) 邻接矩阵适合稠密图，访问边O(1)；
# 4) 可以在此基础上实现 BFS、DFS、最短路径等算法；
# 5) 图是树的推广，广泛用于网络、路线、社交关系建模。
# */

#
# 图的邻接表表示：
# A -> ['B', 'C']
# B -> ['A', 'D']
# C -> ['A', 'D']
# D -> ['B', 'C', 'E']
# E -> ['D']