图论里的“图”不一定是一张地图也不是图片。它是一种描述关系的方法把对象当成“点”把对象之间的关系当成“边”。对象可以是地点、玩家、课程、任务关系可以是道路、好友、先后顺序。我们从几个实际案例来看为什么要用图以及图能帮我们解决什么问题。一、游戏寻路NPC 怎样走到玩家身边假设地图有几个区域出生点 A ── 走廊 B ── 据点 D │ │ └──── 仓库 C ────────┘在这张图里点可以到达的区域边区域之间的通路。问题一能不能到达如果据点的两个入口都被封死出生点 A ── 走廊 B 据点 D │ └──── 仓库 C那么 A 和 D 不再连通。用图的遍历算法就能判断从 A 出发是否存在一条到 D 的路线这可以用于检查地图设计出生点是不是被意外困住了目标区域是否可达。问题二哪条路更快给通路加上预计耗时A → B3 秒 B → D8 秒 A → C5 秒 C → D2 秒那么经过 B3 8 11 秒 经过 C5 2 7 秒虽然路线都经过两条边但走仓库更快。这就是带权图中的最短路径问题。这里的“最短”可以指距离最短也可以指耗时或消耗最小。**实际用途**NPC 寻路、导航、物流配送。二、社交系统推荐谁成为你的好友假设玩家之间的好友关系是你 ── 小明 ── 小李 │ │ └── 小红 ─────┘在这里点玩家边好友关系。你与小李还不是好友但你们有两个共同好友小明和小红。系统就可以把小李列为“你可能认识的人”。图能解决哪些问题1. 查找共同好友你的好友小明、小红 小李的好友小明、小红、小王 共同好友小明、小红本质上是比较两个点的邻居集合。2. 查找关系距离你 → 小明 → 小李你到小李需要经过两条关系边也就是“两跳关系”。3. 发现社群如果一群玩家之间连接非常密集而与外部玩家连接较少那么他们可能形成一个社群例如固定开黑圈。**实际用途**好友推荐、社区分析、组队推荐。不过真实推荐不能只看共同好友数量还要考虑隐私、兴趣和用户设置。三、任务与科技树哪些事情必须先做假设游戏中的解锁规则是采集木材 → 建造工作台 → 制作弓箭 │ └──→ 制作工具这里点任务或解锁项目边前置依赖。箭头A → B表示必须先完成 A才能完成或解锁 B。这种关系有方向所以需要使用有向图。图能帮助确定执行顺序一种合法顺序是采集木材 → 建造工作台 → 制作弓箭 → 制作工具弓箭和工具之间没有前后依赖因此也可以交换顺序。寻找满足所有前置关系的排列叫作拓扑排序。图还能发现设计错误假设策划不小心配置成任务 A 需要先完成任务 C 任务 B 需要先完成任务 A 任务 C 需要先完成任务 B形成A → B → C → A这就是一个环。如果这些都是必须满足的前置条件而且没有任务预先完成那么玩家谁也解锁不了。**实际用途**任务系统、科技树、软件编译依赖、项目排期。四、网络通信一条线路断了数据还能到吗假设服务器之间的连接是服务器 A ── 路由器 B ── 服务器 D │ │ └──── 路由器 C ─────────┘这里点服务器或路由设备边通信链路权重可以是链路成本或估计延迟。如果 B 到 D 的线路断了仍然可以走A → C → D这叫备用路径。图还能发现“关键连接”例如区域网络 1 ───── 区域网络 2 ↑ 唯一连接如果两个区域只有这一条连接断开它就会使网络分裂。在无向图里这种删除后会增加连通分量数量的边叫作桥。同样如果某个节点一旦失效就让原本连通的网络分开它就是割点。**实际用途**网络容灾、关键设备识别、通信线路规划。五、资源分配让谁去做哪件事假设有三名玩家准备分配三个团队角色玩家 A可以玩突击、侦察 玩家 B可以玩突击 玩家 C可以玩侦察、支援可以把点分成两组玩家一组 角色一组 玩家 A ─────────── 突击 └────────── 侦察 玩家 B ─────────── 突击 玩家 C ─────────── 侦察 └────────── 支援连接表示“这个玩家可以担任这个角色”。这种两组点之间连边、组内不连边的图叫作二分图。为什么不能随便分配如果先让 A 选突击A → 突击 B → 没有可选角色但其实存在完整分配B → 突击 A → 侦察 C → 支援寻找尽可能多的不冲突分配就是二分图匹配问题。**实际用途**人员排班、任务分配、学生选课、资源调度。真实游戏中的整队匹配还会加入段位、延迟和组队约束通常比这个例子更复杂。六、地图与网络建设怎样用最低成本连接所有地点假设游戏里要在几个据点之间修建电缆A ── B │ ╲ │ C ── D每条候选线路都有建造成本。目标不是“让 A 到 D 的路最短”而是让所有据点都连通同时总建造成本尽量低。在候选连接构成连通无向图的情况下这对应最小生成树问题。它与最短路径有什么不同问题目标最短路径找到两点间代价最低的路线最小生成树用最低总成本连接所有点最小生成树节省总体建设成本但不保证每两个据点之间的路线都最短而且没有备用回路。**实际用途**管线铺设、通信布线也可用于生成游戏地图的基础连通结构再额外加边形成回路。七、遇到实际问题怎么判断能不能用图可以依次问三个问题。1. 哪些东西可以当成点例如地点、玩家、任务、服务器、课程2. 它们之间有什么关系例如可以通行 互为好友 必须先完成 能够通信 能够承担任务3. 我想问关系中的什么问题你想问的问题常见图问题能不能从这里到那里可达性、连通性怎么走代价最低最短路径哪些事情要先做拓扑排序依赖是否互相卡住环检测哪条连接断了影响最大桥、割点等分析怎样进行不冲突的分配匹配怎样最低成本连接全部地点最小生成树最后再选择用邻接表、邻接矩阵或其他方式保存它。图是关系模型邻接表和邻接矩阵是存储方式图算法则是解决问题的方法。最重要的不是先背算法而是先看出来眼前这个问题究竟有哪些对象它们如何连接我想从这些连接中得到什么答案。