1986 · 理论与算法

揭示图中的结构

高效图算法让人不必反复探索全部关系。

约翰·霍普克罗夫特 · 罗伯特·塔扬

1986图灵奖

视觉指南

奖项，化为图解

阅读图解文字

图算法用于编译器、网络和优化等任务，在这些问题中，关系与对象本身同样重要。

图是一种抽象；算法的保证取决于具体问题和表示方式。

01 · 核心想法

约翰·霍普克罗夫特和罗伯特·塔扬推进了算法与数据结构的设计和分析。他们展示了遍历图时发现的结构如何支持强大算法，例如判断一个图能否在平面上无交叉地绘制。计算的组织方式，与单个操作同样重要。

图算法用于编译器、网络和优化等任务，在这些问题中，关系与对象本身同样重要。

02 · 人物

约翰·霍普克罗夫特推动算法设计与分析成为系统性学科。他在自动机、图算法与数据结构方面的研究，展示了数学洞察如何显著提高效率。他与罗伯特·塔扬共同发展图问题的重要方法，也合著了广泛使用的教材。他在康奈尔的研究和教学使算法成为计算机科学教育中连贯的核心内容。

罗伯特·塔扬发展了高效图算法、数据结构以及严格分析其效率的方法。他的研究包括深度优先搜索技术、并查集分析与自调整数据结构。他与约翰·霍普克罗夫特的合作使高效图处理成为算法的重要基础领域。1986 年获奖时，他任职于普林斯顿大学和 AT&T 贝尔实验室。

03 · 延伸阅读

本站原创讲解依据官方获奖记录。领域标签用于编辑导航。