图论基础：定义、术语与存储结构详解

本文档是对数据结构中的图进行深入总结的教程。首先，我们明确了图的基本概念： 1. **定义与术语**： - 图是一种无序的数据结构，由两个主要部分组成：边集和顶点集。 - **边集**包括两类：有向图和无向图。在有向图中，边具有方向性，如边<v,w>表示从v指向w，而无向图则无方向性。还区分了弧头、弧尾和权值的概念。对于无向图，度（TD(v)）指顶点的相邻边数量；有向图则区分出度（ID(v)）（指向其他顶点的边数量）和入度（OD(v)）（从其他顶点指向该顶点的边数量）。 - **无向完全图**和**有向完全图**分别是当n个顶点间每对顶点之间都有一条边时，它们的特殊形式。无向完全图有[n*(n-1)]/2条边，有向完全图有n*(n-1)条边。 - **连通分量**和**强连通分量**分别是指在无向图和有向图中最大的连通子图。无向图的连通分量可以是单个，而在有向图中，强连通分量意味着可以从任何顶点到任何其他顶点都有路径。 - **生成树**是图的最小连通子图，包含所有顶点，仅有的边数为n-1，确保每个顶点都可达但不存在环。 2. **存储结构**： - 顶点通常使用链表或数组存储，链表更常用，便于添加和删除操作。 - 边的存储方式有邻接矩阵和邻接表两种： - 邻接矩阵（对无向图用对称矩阵，有向图用不对称矩阵）可以直观表示顶点间的连接关系，通过矩阵元素判断顶点是否相连及其权重。 - 邻接表（链表）更为节省空间，适合大规模图，每个顶点关联一个链表，链表中包含边的信息如权值。 - 十字链表（OthogonalList）则针对有向图，维护弧的双向链接。 3. **图的遍历**： - 深度优先遍历（DFS）是图遍历的一种重要方法，类似于树的先根遍历，从起点v出发，尽可能深地探索分支，直到遍历完所有可达顶点。对于无连通图，可能需要从不同起点重复这个过程。 本文档全面概述了图的定义、关键术语、存储结构以及常用的深度优先遍历算法，为理解和应用图数据结构提供了清晰的指导。学习者可以通过本文深入了解如何在实际编程中有效地操作和处理图数据。