图是什么？——用点和线认识世界

想象一下你和你的好朋友之间的关系。每个人是一个“点”，好朋友之间用一条“线”连起来。这种由“点”和“线”组成的结构，在计算机里就叫图。

顶点：就是图中的每个“点”，比如你、你的朋友。
边：就是连接两个顶点的“线”，表示他们有关系。
有向图：如果关系是单向的，比如你关注了小明，但小明没关注你，箭头就只指向小明。
无向图：如果关系是双向的，比如你们是朋友，那么连线就没有箭头。
权重：有的边还有数字，比如从家到学校的距离是500米，这个数字就是权重。

图能干很多事：帮你找到从家到学校的最短路线、推荐你可能认识的朋友、规划地铁线路……掌握图，就能用计算机模拟这些真实世界的关系。

生活中的图——处处都是点和线

先看几个例子：

朋友圈：每个人是一个点，互相认识就是一条边（无向）。如果你单向关注了某网红，那就是有向边。
地图与道路：十字路口是点，路是边，路的长短就是权重。比如从你家到学校有一条500米的直达路，还有一条800米但经过小卖部的路。
游戏传送点：游戏里有几个传送门（点），每个传送门可以传送到另外几个地方（有向边），花费的金币数就是权重。

关键概念详解

1. 顶点和边——图的基本零件

每个图中都有顶点（也叫节点）和边。边连接两个顶点。生活中：“你”是一个顶点，“小明”是另一个顶点，“你们是好朋友”就是一条边。

# 定义顶点（用字符串代表名字）
a = "你"          # 顶点：你
b = "小明"        # 顶点：小明
c = "小刚"        # 顶点：小刚

# 边：表示你和小明是朋友（无向）
# 这里我们只是先理解概念，后面会用字典真正表示

2. 有向图 vs 无向图

无向图：边没有方向，就像“朋友”——你认识我，我必然认识你。在代码里，如果A连到B，也要把B连到A。

有向图：边有方向，就像“关注”——A关注B，B不一定关注A。在代码里，只记录从A到B的单向关系。

生活中的例子：

班级里谁给谁写了小纸条（有向，A传给B，B不一定传回A）
地铁线路（无向，车可以双向开）

# 无向图：朋友关系
friends_graph = {
    "小红": ["小明", "小刚"],   # 小红的邻居：小明和小刚
    "小明": ["小红", "小丽"],   # 注意：小明也包含了小红（双向）
    "小刚": ["小红"],           # 小刚只有小红
    "小丽": ["小明"]
}
# 有向图：关注关系（假设小红关注小明，小明没关注小红）
follow_graph = {
    "小红": ["小明"],           # 小红关注了小明
    "小明": [],                 # 小明没关注任何人（空列表）
    "小刚": ["小红", "小丽"]   # 小刚关注了小红和小丽
}

3. 权重（边上的数字）

有些图除了表示“有关系”，还表示“关系的强度”或“代价”。比如：

从家到学校距离500米，到小卖部200米
坐地铁从A站到B站需要3分钟
游戏里从新手村到主城需要5个金币

带权重的图就是每条边都附上一个数字。

# 带权重的无向图：家到各处的距离（单位：米）
weighted_graph = {
    "家": [("学校", 500), ("小卖部", 200), ("公园", 800)],  # 家到学校500米，到小卖部200米
    "学校": [("家", 500), ("小卖部", 300)],                 # 学校到家500米，到小卖部300米
    "小卖部": [("家", 200), ("学校", 300)],                 # 小卖部到家200米，到学校300米
    "公园": [("家", 800)]
}

每个邻居用一个元组表示：(顶点名, 权重)。注意无向图要对称添加。

如何用Python表示图（最常用的三种方式）

除了字典加邻接表（上面已经演示），还有两种方式：

方式1：字典+列表（邻接表）——最直观

适合顶点不多、边稀疏的情况。每个顶点对应一个列表，列表里放它的邻居（有向图只放出去的邻居，无向图相互放）。

# 无向图：朋友关系（用字典+列表）
graph = {
    "小红": ["小明", "小刚"],   # 小红的朋友
    "小明": ["小红", "小丽"],   # 小明的朋友
    "小刚": ["小红"],           # 小刚的朋友
    "小丽": ["小明"]            # 小丽的朋友
}

方式2：字典+集合（邻接集合）——防重复

如果担心同一对邻居出现多次（比如重复添加），可以用集合代替列表。集合里元素不会重复。

# 无向图，用集合存储邻居（自动去重）
graph_set = {
    "小红": {"小明", "小刚"},   # 注意用花括号{}表示集合
    "小明": {"小红", "小丽"},
    "小刚": {"小红"},
    "小丽": {"小明"}
}

方式3：列表+列表（邻接矩阵）——适合顶点少、边多

用二维列表，行和列都代表顶点，相交的位置填1（有边）或0（无边），有向图不对称。权重图填权重数字。

# 一个3个顶点的无向图，顶点编号0,1,2
# 0--1, 0--2, 1--2（完全三角形）
num_nodes = 3                    # 顶点数
adj_matrix = [
    [0, 1, 1],   # 0号顶点连1和2
    [1, 0, 1],   # 1号顶点连0和2
    [1, 1, 0]    # 2号顶点连0和1
]

新手容易犯的错误

❌ 错误1：无向图忘记加双向边

# 错误示例：只加了一边
bad_graph = {
    "小红": ["小明"],    # 小红认识小明
    "小明": []           # 小明不认识小红？不对，朋友是双向的
}
# 正确做法：小明也必须加上小红
good_graph = {
    "小红": ["小明"],    
    "小明": ["小红"]     
}

❌ 错误2：有向图的边方向搞反

比如题目说“小明给小刚一块糖”，应该从小明指向小刚，而不是反过来。

❌ 错误3：权重图里忘记把邻居和权重打包成元组

# 错误：直接把数字当邻居名
bad_weight = {
    "学校": [500]   # 错误！“500”不是顶点名，是距离
}
# 正确：用元组(顶点名, 权重)
good_weight = {
    "学校": [("家", 500)]  # 学校到家500米
}

❌ 错误4：用字符串写数字作为顶点名

比如顶点名写“1”而不是1。如果用数字作为顶点名，要注意类型统一。后续遍历时容易出错。

# 不推荐：混用类型
mix = {1: [2, 3], "2": [1]}   # 1是整数，"2"是字符串，容易混乱
# 推荐：统一用字符串或整数

完整可运行示例：朋友关系检测

下面代码包含：

用字典表示一个无向图（朋友关系）
打印所有顶点的朋友列表
判断两个人是否是朋友

# 完整示例：朋友关系检测
def main():
    # 用字典+列表表示无向图
    friends = {
        "小红": ["小明", "小刚"],   # 小红的朋友
        "小明": ["小红", "小丽"],   # 小明的朋友
        "小刚": ["小红"],           # 小刚的朋友
        "小丽": ["小明"]            # 小丽的朋友
    }
    
    # 1. 打印每个人的朋友
    print("=== 每个人的朋友列表 ===")
    for person, friend_list in friends.items():
        # person是当前人的名字，friend_list是他的朋友列表
        print(f"{person}的朋友有：{friend_list}")
    
    # 2. 判断两个人是否是朋友
    def are_friends(name1, name2):
        # 检查name2是否在name1的朋友列表中
        if name2 in friends.get(name1, []):
            return True
        return False
    
    print("\n=== 朋友关系检测 ===")
    test_pairs = [("小红", "小明"), ("小红", "小丽"), ("小刚", "小丽")]
    for a, b in test_pairs:
        if are_friends(a, b):
            print(f"{a}和{b}是朋友")
        else:
            print(f"{a}和{b}不是朋友")

# 运行主函数
if __name__ == "__main__":
    main()

输出：

=== 每个人的朋友列表 ===
小红的朋友有：['小明', '小刚']
小明的朋友有：['小红', '小丽']
小刚的朋友有：['小红']
小丽的朋友有：['小明']

=== 朋友关系检测 ===
小红和小明是朋友
小红和小丽不是朋友
小刚和小丽不是朋友

图的定义与相关概念