有向图与拓扑排序

"该资源是关于数据结构导论中第5章‘图’的课程内容，主要探讨了图的基本概念、存储结构、遍历、最小生成树以及拓扑排序等核心知识点。" 在数据结构中，图是一种重要的抽象数据类型，它由顶点集V和弧集E组成，表示了顶点之间的关系。图的形式定义为Graph=(V,E)，其中V是非空的顶点集合，E是边或弧的集合。如果边具有方向，那么图被称为有向图，例如，<v,w>表示从顶点v到顶点w的一条弧，v是弧尾，w是弧头。无向图则没有方向，边以(v,w)的形式表示，表示v和w之间存在一条边，且(v,w)和<w,v>是等价的。 在有向图中，引入了度的概念，分为出度和入度。出度是顶点作为弧尾的弧的数量，入度则是顶点作为弧头的弧的数量。顶点的度是出度与入度之和。例如，在图示例子中，顶点B的出度是1，入度是2，因此度是3。 图的存储结构通常有两种主要方式：邻接矩阵和邻接表。邻接矩阵用二维数组表示，每个元素表示对应顶点间是否存在边或弧；邻接表则是为每个顶点维护一个链表，链表中的元素表示与其相邻的顶点。 图的遍历方法主要包括深度优先搜索(DFS)和广度优先搜索(BFS)。在有向图中，拓扑排序是另一种重要的遍历方法，用于得到一个无环有向图的所有顶点的线性顺序，使得对每条有向边(u, v)，顶点u都在顶点v之前。在给定的描述中，提到的有向图无法进行拓扑排序，原因在于图中存在回路，如回路{B, C, D}。 最小生成树算法，如Prim算法或Kruskal算法，用于寻找无向图中连接所有顶点的边集，使得这些边的权重之和最小。 总结来说，本章内容覆盖了图的定义、术语、存储结构、遍历方法，以及与图相关的特定问题如最小生成树和拓扑排序。这些知识在计算机科学中有着广泛的应用，如网络路由、任务调度、社交网络分析等。