- 文集信息
- 目录大纲
- 最新文档
- 知识宇宙
文集详情
文集导读
图论基础：概念、算法与应用
普雷格尔河从哥尼斯堡城中穿过，河心的克奈普霍夫岛与两岸之间架着木桥。市民们茶余饭后争论不休：能否把每座桥恰好经过一遍，最后回到出发的地方？欧拉把这个散步难题抽象成"陆地"与"桥"的连接关系，一笔证明了这样的路线不存在——图论就此诞生，远征也由此启程。
本册把整个图论学科组织成一支远征队的推进史：顶点与边是远征地图上的要素，遍历算法是侦察兵的行军路线，最短路径、最小生成树、网络流是一场场目的明确的战役，着色与匹配是收尾攻坚，特殊图类是沿途归档的地图档案，工程应用则是凯旋之后的实战检阅。读完全册，你会拥有的不是一堆孤立名词，而是一张"遇到连接问题该调哪支部队"的作战地图。
这支远征队会走过哪些疆土
各章在主线上的位置
前两章是出发准备：弄清图论从哪里来、地图语言怎么写、情报如何存储。第 3、4 章进入行军阶段——深度优先与广度优先是所有图算法的行军底牌，连通性勘定则回答"哪些地方连成一片、哪里有回路"。第 5 到 7 章是三场硬仗：最短路径解决"怎么走得最快"，最小生成树解决"怎么用最省的代价把据点连起来"，网络流解决"这条补给线最多能运多少物资"。第 8、9 章收尾：着色与匹配处理冲突与配对，特殊图类把沿途见过的图归档立卷。第 10 章凯旋检阅，把前面所有兵法放到社交网络、导航路由、编译器、数据库与推荐系统里验收。
怎样使用这本册子
本册的每节都按同一种节奏推进：先给一个具体的场景或悬案，再展开思路推演，然后给出可运行的代码与手推的图例，最后算清复杂度账单、交代应用与变体。阅读时强烈建议同步敲代码——所有实现基于 Python 与 networkx，任何一台装了这两样的机器都能复现书里的每个数字。遇到证明先抓直觉版论证，形式化的部分可以第二遍再补；每个算法节末尾的"复杂度与证明"段落就是为这种两遍读法设计的。
三条路线供不同起点的读者选用。零基础起步：按章节顺序通读，每章做完节末演练再前进，全册约需数周。有算法基础：可以直奔第 4 到 8 章的算法战役，需要回查词汇时再翻前两章，第 9、10 章按兴趣选读。工程导向：先读第 2 章的选型决策、第 10 章的实战检阅建立全局感，再回头补齐对应算法的原理章节。无论走哪条路线，建议把每章支柱页的"知识点清单"当作自测卷——那些条目都写到了可考核的颗粒度，能逐条对答如流，才算真正通关。
与站内其他册子的分工也交代清楚：本册讲的是数学与算法层面的经典图论；想学图上的深度学习，请移步图神经网络专题册；想了解大规模网络的经验规律与统计模型，网络科学专题册在那里等候。这两册都以本册的地基为起点，学完这里再过去，事半功倍。
读这本册子之前
你只需要会一点 Python 基础语法和初中代数，不需要预先学过离散数学。每一节都从具体问题出发，配可运行的代码与手推的图例；涉及证明的地方，先给直觉再给论证，读不懂论证可以先记结论，回头再补。如果你关心的是"图上的深度学习"，本册只在数学与算法层面铺路，神经网络部分请移步站内的图神经网络专题册；反过来，想把 GNN 学扎实的人，也建议先在这里把图的语言与经典算法过关。
一句话总纲：图论研究的不是"图"这个字，而是"连接"这件事——凡有关系处，皆可成图。
目录大纲
最新文档
知识宇宙
正在加载知识图谱...