图论 (2).pdf

【图论基础】 图论是计算机科学中的一个重要分支，尤其在算法设计和复杂问题建模中扮演着核心角色。在信息学竞赛和实际编程中，图论知识是必不可少的。本章将深入探讨图的基本概念及其存储方式。 1.1 图的基本概念 图是由顶点（或结点）和边组成的结构。在图论中，顶点表示问题中的基本元素，边则表示顶点之间的关系。根据边的方向，图可以分为有向图和无向图。在有向图中，边是有方向的，通常表示从一个顶点到另一个顶点的流动或关系，记为<vi, vj>。无向图中，边没有方向，记作(vi, vj)，意味着存在双向的关系。顶点的出度是与之相连的有向边的数量，入度则是指向它的边的数量。无向图中，边的数量是顶点度的一半，因为每条边在邻接矩阵中被计算两次。 1.2 图的存储方式 存储图的方法主要有邻接矩阵和邻接表两种。 - 邻接矩阵：对于有向图，邻接矩阵是一个n*n的二维数组，M[I, j] = 1表示存在从顶点vi到vj的边，否则为0。对于无向图，M[i, j] = M[j, i] = 1表示顶点vi和vj之间有边，其余为0。邻接矩阵适合表示稠密图，即边的数量接近于顶点数量的平方。 - 邻接表：对于有向图和无向图，邻接表通常更节省空间，特别是对于稀疏图（边的数量远小于顶点数量的平方）。邻接表可以用链表或数组模拟链表的形式，记录每个顶点的所有邻接顶点。前向星是邻接表的一种变体，使用三个数组a, b, c分别存储起点、终点和边的权重，链式前向星适用于动态更新和复杂查询。 1.3 广度优先搜索（BFS） 广度优先搜索是图遍历的一种策略，用于寻找最短路径、检测连通性等问题。从一个源顶点开始，BFS按照层次顺序访问顶点，先访问距离源顶点近的顶点，再访问远的。使用队列数据结构可以有效地实现BFS。 通过理解图的基本概念和存储方式，我们可以解决各种图论问题，如最短路径、最小生成树、拓扑排序等。在信息学竞赛中，掌握图论技巧能够帮助我们解决复杂问题，甚至使用网络流等高级技术来处理流量分配和资源调度问题。 【习题】 1. 线段和射线不是图，因为它们不包含顶点的集合。一些孤立的点可以构成图，但它们是无边的图，即没有边连接的顶点集合。 2. 在信息学中，图通常用邻接矩阵或邻接表存储。邻接矩阵适用于表示边关系清晰且边数量较多的情况，而邻接表更适合边数量较少的稀疏图，以节省空间。此外，还可以使用邻接多重表（邻接表的变种）或其他数据结构如二叉堆、堆等进行优化。