数据结构第7章图.docx

【数据结构第7章 图】 在数据结构的学习中，图是一种重要的抽象数据类型，它用于表示顶点（或节点）之间的关系。本章主要探讨了图的定义、性质及其相关概念，包括路径、连通性、度数以及图的表示方法。 1. 路径的定义：路径是由顶点和相邻顶点序偶构成的边所形成的序列。例如，从顶点A到顶点D的路径可能是A-B-C-D，其中A、B、C、D是顶点，(A,B)，(B,C)，(C,D)是边。 2. 无向图的边数：一个有n个顶点的无向图最多有n*(n-1)/2条边，这是因为每一条边连接两个不同的顶点，且无向图中的边是无方向的，所以一条边会被计算两次。 3. 连通无向图的边数：一个有n个顶点的连通无向图，其边的个数至少为n-1，因为至少需要n-1条边才能确保所有的顶点都相互连通。 4. 连通有向图的边数：要连通具有n个顶点的有向图，至少需要n-1条边，这与无向图的情况类似。 5. 完全有向图的边数：n个结点的完全有向图含有边的数目为n*(n-1)，每个顶点指向其他所有顶点。 6. 连通分量：一个图最少有1个连通分量（如果图是连通的），最多有n个连通分量（如果图是完全分离的，即每个顶点都是一个独立的连通分量）。 7. 度数和边数的关系：在一个无向图中，所有顶点的度数之和等于所有边数的2倍，因为在无向图中每条边贡献了两个度数。而在有向图中，所有顶点的入度之和等于所有顶点出度之和，体现了边的起点和终点的平衡。 8. 有向无环图(DAG)的表示：表达式(A+B)*(A+B)/A可以用有向无环图表示，至少需要5个顶点，分别代表操作和变量。 9. 深度优先搜索(DFS)与拓扑排序：DFS遍历无环有向图并在退栈时打印顶点，会得到逆拓扑有序的顶点序列。 10. 图的存储结构：稀疏图（边的数量远小于顶点数量的平方）通常用邻接表、逆邻接表或十字链表表示。邻接矩阵适合稠密图，但不适合稀疏图。 11. 邻接矩阵的对称性：无向图的邻接矩阵是对称的，因为无向图的边没有方向，所以邻接矩阵的(i,j)和(j,i)位置的值相同。 12. 邻接矩阵的信息：给定的邻接矩阵表示一个有9个顶点的图，如果是有向图，有3条弧，无向图则有3条边。 13. 顶点的度数：在邻接矩阵表示的图中，顶点Vi的度是矩阵中第i行和第i列之和减去对角线元素（即顶点Vi到自身的边），即第i行和第j列之和的1/2。 14. 判断路径存在：若要检查两个顶点间是否存在长度为m的路径，只需检查矩阵Am-1的第i行第j列元素。 15. 图的遍历特性：图的遍历是从给定的源点出发，每个顶点仅被访问一次，遍历的基本算法有深度优先搜索和广度优先搜索，深度优先搜索是一个递归过程，适用于有向图和无向图。 16. 无向图G的边集：无向图G包含6个顶点和4条边，分别为(a,b)，(a,e)，(a,c)，(b,e)。无向图中的边是双向的，因此(a,b)与(b,a)视为同一边。 这些知识点涵盖了图的基本概念、性质、遍历策略以及图的存储结构，对于理解和操作图至关重要。