无向图的概念与定义 - 数据结构中的图

"本资源为数据结构导论中关于图的章节内容，主要讲解了图的基本概念、存储结构、遍历、最小生成树以及拓扑排序。特别关注了无向图的定义，即若顶点的偶序对是无方向的，称此图为无向图。文中给出了无向图G2的实例，并介绍了顶点的度、有向图的入度和出度等概念。" 在数据结构中，图是一种非常重要的抽象数据类型，它由顶点集V和边集E组成，通常表示为Graph=(V,E)。图可以是有向或无向的。无向图是当边没有明确的方向时，即对于任意一对顶点v和w，如果存在边<(v,w)>，那么也一定存在边<(w,v)>。例如，给出的无向图G2包含顶点集V2={A, B, C, D, E, F}和边集E2={(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F)}。 图的边可以带权，这样的图被称为有向网或无向网，权重可以代表距离、成本等实际意义。图中的子图是包含原图部分顶点和边的图，即V'⊆V且E'⊆E。 图中的顶点之间通过边相互连接，如果顶点v和w之间存在边，它们被称为邻接点。顶点v的度(Degree)是指与v相连的边的数量。对于无向图，顶点的度等于其相邻边的数量。而在有向图中，引入了出度(Outdegree)和入度(InDegree)的概念，出度是作为起点的边的数量，入度是作为终点的边的数量，顶点的总度等于出度加上入度。 完全图是指所有顶点两两之间都存在边的图，在无向图中，完全图有n(n-1)/2条边；在有向图中，每对顶点间有两条方向相反的弧，因此有n(n-1)条边。 此外，图的遍历是图论中的重要操作，包括深度优先搜索(DFS)和广度优先搜索(BFS)等方法，这些方法用于访问图中的所有顶点。最小生成树算法如Prim算法或Kruskal算法则是寻找连接所有顶点且总权重最小的边集。拓扑排序是针对有向无环图(DAG)的操作，它将顶点排出一个线性的顺序，使得对于每条有向边<u, v>，u总是在v之前。 这些基本概念和操作是理解和处理复杂关系网络的基础，广泛应用于网络分析、路由算法、社交网络、计算机科学的多个领域，以及各种实际问题的建模。