基本图算法的介绍与历史

图论的发展历史

图是一种成对对象的集合——可以是整数对、人对、城市对、恒星对、国家对、科学论文对、网页对、游戏状态对、递归子问题对，甚至图对。最常用的可视化方法是镜像表示；被配对的实体通常称为顶点或节点，而这些配对本身则称为边或弧。但实际上，这些对象和配对可以是任何事物。

图的最早实例之一是道路网络及其地图。在罗马帝国鼎盛时期，罗马工程师在欧洲、西亚和北非修建了超过40万公里的公共道路网络。旅行者依靠路线图行进，这些路线图要么是简单的列表，要么是带有地标和距离信息的图像化表示。《普特林格地图》（Tabula Peutingeriana）是一幅13世纪的手卷，描绘了整个“罗马公共驿道”系统，普遍认为它是5世纪版本的中世纪复制品，而该版本又源自公元1世纪由奥古斯都皇帝下令制作的《图画式行程录》。普特林格地图并非地理精确的地图——历史学家甚至争论它是否算得上真正的“地图”——但它是一种抽象的道路网络表示，类似于现代地铁线路图。每条道路上的城市通过曲线的折点来标识，城市名称以及各段道路之间的长度也标注在图上。因此，这张地图包含了足够信息，可用来找出5世纪罗马帝国任意两座城市之间的最短路径。见下图：

图论最早的古典应用之一是用以表示家谱的树状结构。复杂的家族树已使用数百年，用于解决婚姻、继承和王位继承等法律问题。罗马帝国的民法后来被早期天主教会采纳为教规，禁止一级堂表亲或更近亲属通婚。到了9世纪初，教会改变了计算标准的距离要求和方式：罗马的“法律计算法”要求最近共同祖先的路径总和至少为四代，而新的“教规计算法”则要求两条路径的最大值至少为七代。1215年，考虑到实际操作的需要（以及现实中的做法），教会将结婚所需的最低距离放宽至四代。下图左侧展示了一个极为复杂的案例：提里乌斯与特伯加结婚并生下儿子盖乌斯，之后提里乌斯去世；特伯加随后嫁给洛塔尔，生下一子后去世；最后，洛塔尔与贝莎结婚，生下女儿吉姆娜。那么，盖乌斯的儿子能否合法地与吉姆娜的女儿结婚？

图形静力学的发展

17世纪末，法国数学家皮埃尔·瓦里尼翁发展出一种图形方法，用于求解受张力作用的树状绳索网络的平衡位置，其基础建立在前人西蒙·斯蒂文一个世纪前的工作之上。瓦里尼翁观察到，当绳索处于平衡状态时，可以绘制一张图，其中每条边与相应绳索平行，长度等于绳索上的张力，且网络中任一点交汇的绳索在图中形成闭合回路。瓦里尼翁的“图形静力学”方法直到1725年才完整发表，即他去世两年后。这类图现在被称为互易力图或麦克斯韦-克雷莫纳图，以詹姆斯·克拉克·麦克斯韦和路易吉·克雷莫纳命名，他们在19世纪后期（与卡尔·库尔曼等人一起）发展了互易图的丰富理论。

当然，还有许多其他常见的图的例子：棋盘类游戏（可追溯至古代）；凸多面体的顶点与边（由古希腊哲学家正式研究，但远早于他们）；星象图案的可视化（早在公元7世纪东亚已有发展）；骑士巡游问题（由阿勒-阿德利、鲁德拉塔、阿勒-苏里等人在9至10世纪描述）；迷宫（以现代形式由乔瓦尼·丰塔纳约在1420年引入）；大地测量三角测量（由杰马·弗里斯尤斯于1533年提出，后由威勒布罗德·斯内尔于1615年用于计算地球周长，并于1799年用于定义“米”的单位）；莱昂哈德·欧拉对柯尼斯堡七桥问题的经典部分解答（1735年）；电报及其他通信网络（最早于1753年提出，由罗纳兹、施林、高斯、韦伯等人在19世纪初发展，于19世纪末实现全球部署）；电路系统（由欧姆、麦克斯韦、基尔霍夫等人在19世纪初正式建立）；分子结构式（由奥古斯特·凯库勒于1857年独立提出，阿奇博尔德·库珀于1858年独立提出）；社交网络（由社会学家雅各布·莫诺在20世纪30年代中期首次研究）；数字电子电路（由查尔斯·桑德斯·皮尔士于1886年提出构想，由克劳德·香农于1937年确立为现代形式）；当然，我们也可以把现代互联网包含在这一系列之中。

图论关键发展的历史

“图”这一术语用于指代抽象数学对象，是由詹姆斯·西尔维斯特于1878年提出的，他根据同事威廉·克利福德的建议，借用凯库勒的“化学图”概念来描述某些代数不变量。“树”这一术语首次用于表示连通无环图，是由阿瑟·凯莱于1857年提出的，尽管在此之前，古斯塔夫·基尔霍夫和卡尔·冯·施陶特已在十年前就已使用过这一抽象概念。第一本图论专著由安德烈·圣特-拉居于1926年出版；十年后，德奈斯·柯尼希出版了第一本系统的图论书籍。