清华大学数据结构课件：图的存储与遍历

"数据结构课件，清华大学，包含图的基本概念、存储结构、遍历、生成树、最短路径问题及关键路径等章节" 在数据结构中，"图"是一种非常重要的抽象数据类型，它用于表示对象之间的复杂关系。本课件主要围绕清华大学的数据结构课程，深入讲解了关于图的各种概念和技术。 首先，5.1节介绍了图的基本概念。图是由顶点（也称为节点）集合V和边集合E组成的二元组，用G=(V,E)表示。边可以是有向的（带箭头，表示方向）或无向的（不带箭头，表示双向关系）。例如，G1和G2是两个简单的图示例，分别展示了有向图和无向图的结构。 接着，5.2节讨论了图的存储结构。常用的存储方法包括邻接矩阵、邻接表、边集数组和邻接多重表。邻接矩阵用二维数组存储图中顶点之间的关系，邻接表则通过链表节省空间，尤其对于稀疏图更为适用。边集数组和邻接多重表主要用于有向图，其中边集数组存储所有边，邻接多重表则按顶点组织边。 5.3节讲述了图的遍历技术，包括深度优先遍历（DFS）和广度优先遍历（BFS）。DFS从起点出发，沿着边尽可能深地探索图的分支，而BFS则是从起点开始，逐层探索所有相邻的顶点。 5.4节讨论了图的生成树。在无环图中，生成树是原图的一个子集，包含了所有顶点且边的集合形成了一个树形结构。最小生成树是指边权之和最小的生成树，常用Prim算法或Kruskal算法求解。 5.5节聚焦于最短路径问题。最短路径是指在图中找到从源点到目标点具有最小权值的路径。单源点最短路径问题通常使用Dijkstra算法解决，而求解每对顶点间的最短路径可以采用Floyd-Warshall算法。 最后，5.6节介绍了关键路径。在AOV（Activity On Vertex）网中，关键路径是指项目中最长的路径，决定了项目的最短完成时间。AOE（Activity On Edge）网是关键路径的一种表示形式，通过拓扑排序和计算每个活动的最早和最晚开始时间，可以识别出关键路径。 实际生活中，图广泛应用于如通信网络、交通网络、计算机网络等领域，用来建模对象之间的复杂关系。理解并掌握图的理论与算法，对于解决实际问题具有重要意义。