图

图 $G$ 由顶点集 $V$ 和边集 $E$ 组成，记为 $G=(V,E)$。

基本概念

• 有向图 / 无向图：边是否有方向
• 简单图 / 多重图：是否存在重复边或顶点到自身的边
• 完全图：任意两个顶点之间都存在边
• 子图：顶点集和边集都是原图子集
• 连通、连通图和连通分量：无向图中顶点间是否有路径相连
• 强连通图、强连通分量：有向图中顶点间双向可达
• 生成树 / 生成森林：包含全部顶点的极小连通子图
• 顶点的度、入度和出度：与该顶点相关联的边的数目
• 边的权和网：边上带有权值
• 稠密图 / 稀疏图：按边数与顶点数的相对多少划分
• 路径、路径长度和回路：顶点序列及其经过的边数
• 简单路径 / 简单回路：顶点不重复出现的路径/回路
• 距离：两顶点间最短路径的长度

存储结构

邻接矩阵法

用一个 $n\times n$ 的二维数组存储顶点间的邻接关系，适合稠密图。

邻接表法

为每个顶点建立一个单链表存储其邻接顶点，适合稀疏图。

其他

十字链表（有向图）、邻接多重表（无向图）。

图的基本操作

• Adjacent(G, x, y)：判断边 $(x,y)$ 是否存在
• Neighbors(G, x)：列出顶点 $x$ 的邻接边
• InsertVertex(G, x) / AddEdge(G, x, y) / RemoveEdge(G, x, y)
• FirstNeighbor(G, x) / NextNeighbor(G, x, y)
• Get_edge_value(G, x, y) / Set_edge_value(G, x, y, v)

遍历

广度优先搜索 BFS

• 空间复杂度 $O(|V|)$
• 邻接表时间复杂度 $O(|V|+|E|)$
• 邻接矩阵时间复杂度 $O(|V{|}^2)$
• 可用于求解单源最短路径问题、生成广度优先生成树

深度优先搜索 DFS

• 空间复杂度 $O(|V|)$
• 邻接表时间复杂度 $O(|V|+|E|)$
• 邻接矩阵时间复杂度 $O(|V{|}^2)$
• 可生成深度优先生成树/生成森林

应用

• 最小生成树（MST）：Prim 算法、Kruskal 算法
• 最短路径：Dijkstra 算法（单源）、Floyd 算法（多源）
• 拓扑排序（AOV 网）
• 关键路径（AOE 网）