4.2 有向图
Robert Sedgewick Kevin Wayne
在有向图中，边是单向的：每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的（表 4.2.1）。许多应用（比如表示网络、任务调度条件或是电话的图）都是天然的有向图。为实现添加这种单向性的限制很容易也很自然，看起来没什么坏处。但实际上这种组合性的结构对算法有深刻的影响，使得有向图和无向图的处理大有不同。本节中，我们会学习搜索和处理有向图的一些经典算法。
表 4.2.1 实际生活中的典型有向图
4.2.1 术语
虽然我们为有向图的定义和无向图几乎相同（将使用的部分算法和代码也是），但仍然需要在这里重复一遍。为了说明边的方向性而产生的细小文字差异所代表的结构特性正是本节的重点。
定义。一幅有方向性的图（或有向图）是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
我们称一条有向边由第一个顶点指出并指向第二个顶点。在一幅有向图中，一个顶点的出度为由该顶点指出的边的总数；一个顶点的入度为指向该顶点的边的总数（请见图 4.2.1）。当上下文的意义明确时，我们在提到有向图中的边时会省略有向二字。一条有向边的第一个顶点称为它的头，第二个顶点则被称为它的尾。将有向边画为由头指向尾的一个箭头。用 v → w 来表示有向图中一条由 v 指向 w 的边。和无向图一样，本节的代码也能处理自环和平行边，但它们不会出现在例子中，在正文中一般也不会提到它们。除了特殊的图，一幅有向图中的两个顶点的关系可能有 4 种：没有边相连；存在从 v 到 w 的边 v → w；存在从 w 到 v 的边 w → v；既存在 v → w 也存在 w → v，即双向的连接。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了有向图的概念、术语和相关算法。有向图中的边是单向的，每条边连接的两个顶点是一个有序对，这种单向性对算法有深刻影响。与无向图相比，有向图的处理更为复杂，因为有向路径的可达性和无向图中的连通性有所不同。文章提到了有向图的术语，如出度、入度、有向路径和有向环等。此外，还介绍了有向图的数据类型和表示方法，使用邻接表来表示有向图，使得每条边只出现一次。文章还介绍了有向图的输入格式和相关API。在算法方面，文章详细介绍了有向图中的可达性问题，包括单点可达性和多点可达性，并给出了相应的算法实现。此外，还讨论了有向图在实际应用中的重要性，如在内存管理系统中的垃圾收集和有向图的寻路等方面。文章内容丰富，对读者理解有向图具有很好的指导意义。文章还提到了有向图中的环和有向无环图的概念，以及有向环检测的问题。有向图中的环特别重要，而有向无环图在实际应用中也具有特殊意义。总的来说，本文内容涵盖了有向图的基本概念、算法实现和实际应用，为读者提供了全面的了解和指导。文章还介绍了Kosaraju算法解决有向图中的强连通性问题，以及传递闭包的概念和实现。文章内容丰富，对读者理解有向图具有很好的指导意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论