图的定义与基本术语：顶点度数解析

本资源是一份关于数据结构的课件，主要讲解了图的定义、基本术语、存储结构、遍历方法以及应用。通过学习，旨在理解如何在计算机中表示和处理图，并利用图解决实际问题。 在数据结构中，图是一种非线性的数据结构，与线性表和树结构不同。线性表中的节点间关系一对一，树结构为一对多，而图的顶点之间可以形成多对多的关系，更加复杂。图在许多技术领域有广泛应用，如网络路由、社交网络分析等。 7.1 图的定义与基本术语 图由顶点（vertex）和边（edge）组成，形式化定义为 Graph=(V,R)，其中 V 是顶点集合，R 是边的集合。顶点可以是任何具有相同特性的数据对象，边则表示顶点之间的关系。边分为有向和无向两种。有向边（arc）用有序对 <x,y> 表示，x 为起点（tail），y 为终点（head）。无向边是边的对称形式，用无序对 (x,y) 表示，表示 x 和 y 之间的连接，没有方向之分。 课件提供了两个图的例子：G1 是有向图，包含顶点 1, 2, 3, 4，边的方向从一个顶点指向另一个；G2 是无向图，同样包含顶点 1, 2, 4, 5，边没有方向，如 (1,2), (2,4), (4,5)。 在图中，每个顶点的邻接点（adjacent vertex）是与其直接相连的顶点。图的操作通常包括创建、插入、删除和查找。抽象数据类型 ADTGraph 描述了这些基本操作，例如 CreateGraph(G) 操作用于创建一个图 G。 7.2 图的存储结构 图的存储结构主要有两种：邻接矩阵（adjacency matrix）和邻接表（adjacency list）。邻接矩阵用二维数组表示，矩阵中的每个元素表示对应顶点间是否存在边；邻接表则是为每个顶点维护一个列表，列表包含与其相邻的所有顶点。 7.3 图的遍历 图的遍历方法主要包括深度优先搜索（DFS）和广度优先搜索（BFS）。DFS 从一个顶点出发，尽可能深地搜索图的分支；BFS 则是从起始顶点开始，先访问所有距离起始顶点近的顶点，然后逐步访问更远的顶点。 7.4 图的应用 图的应用广泛，如在路由算法中寻找最短路径（Dijkstra 算法、Floyd-Warshall 算法），在社交网络中分析关系网络，或者在任务调度中找出最优解。 7.5 总结与提高 这部分可能涵盖了对图论概念的总结，以及如何通过学习和实践提升对图的理解和应用能力。 在数据结构的学习中，理解和掌握图的特性及其操作是至关重要的，因为它们能帮助解决很多实际问题，例如在算法设计、网络分析、图形学等领域都有广泛应用。通过本课件，学习者可以深入理解图的概念，为后续的高级数据结构和算法学习打下坚实基础。