下载掌阅APP，畅读海量书库
立即打开
1.本章从图的基本概念、图的存储表示、图的遍历以及图的相关应用四个方面对图论知识展开了介绍。
2.本章介绍了图的定义以及与图相关的术语。图作为一种数据结构，可以以多种存储方式在计算机内进行表示，因此1.2节从邻接矩阵、邻接表、十字链表和邻接多重表四种方式入手，对图的存储表示进行了介绍。接下来讲解了图的遍历，遍历图的算法通常是实现图的其他操作的基础。
3.本章介绍了广度优先搜索和深度优先搜索两种算法。并在此基础上，从图的实际应用出发，介绍了几种常见的图算法，包括求最小生成树的Prim算法和Kruskal算法、拓扑排序、关键路径以及求单源最短路径的Dijkstra算法和求所有顶点间最短路径的Floyd算法等。