数据结构的图研究和定义

图Graph是离散数学与计算机科学中的核心数据结构之一广泛用于建模实体之间的二元关系。本报告从数学定义出发系统阐述图的基本概念、分类体系、存储表示、经典算法及实际应用旨在为读者提供一份全面且专业的图论入门参考。一、引言在现实世界中许多问题本质上都可以抽象为对象及其关系的研究——社交网络中的人际关联、交通网络中的路线规划、互联网中网页的链接结构、生物信息学中蛋白质的交互网络等。图论Graph Theory 正是研究这类关系的数学分支而图Graph 则是其最基本的研究对象。图论起源于 1736 年瑞士数学家莱昂哈德·欧拉Leonhard Euler 对柯尼斯堡七桥问题的解答这篇论文被公认为图论的奠基之作。经过近三个世纪的发展图论已渗透到数学、计算机科学、物理学、社会学、生物学等众多学科领域。二、图的数学定义2.1 基本定义定义 2.1图一个图 G 是一个有序二元组G (V, E)其中V 是一个非空有限集合称为顶点集Vertex Set其元素 v in V 称为顶点Vertex或节点Node。E 是 V 中元素构成的无序对或有序对的集合称为边集Edge Set其元素 e in E 称为边Edge。记号约定通常用 V(G) 和 E(G) 分别表示图 G 的顶点集和边集用 |V| 和 |E| 分别表示顶点的数量和边的数量。2.2 无向图与有向图根据边的性质图可分为两大类定义 2.2无向图Undirected Graph若图 G (V, E) 中的每条边 e {u, v} 都是顶点的无序对即 {u, v} {v, u}则称 G 为无向图。此时称 u 和 v 是该边的端点Endpoints并称 u 与 v 相邻Adjacent。定义 2.3有向图Directed Graph / Digraph若图 G (V, E) 中的每条边 e (u, v) 都是顶点的有序对即 (u, v) neq (v, u)则称 G 为有向图。此时称 u 为该边的起点Tailv 为该边的终点Head并称该边从 u 指向 v。2.3 形式化示例示例 1无向图G_1 (V_1, E_1), quad V_1 {v_1, v_2, v_3, v_4}, quad E_1 {{v_1,v_2}, {v_2,v_3}, {v_3,v_4}, {v_4,v_1}}该图表示一个由 4 个顶点和 4 条边构成的四边形结构。示例 2有向图G_2 (V_2, E_2), quad V_2 {A, B, C}, quad E_2 {(A,B), (B,C), (C,A), (A,C)}该图中边 (A,C) 和 (C,A) 是两条不同的边体现了有向图的方向性。三、图的基本概念与术语3.1 关联与度术语 定义关联Incidence 若边 e {u, v}则称 e 与顶点 u、v 关联也称 e 关联于 u 和 v。度Degree 无向图中顶点 v 的度 deg(v) 是与 v 关联的边的数目。入度In-degree 有向图中顶点 v 的入度 deg^-(v) 是以 v 为终点的边的数目。出度Out-degree 有向图中顶点 v 的出度 deg^(v) 是以 v 为起点的边的数目。定理 3.1握手定理Handshaking Lemma对于任意无向图 G (V, E)所有顶点的度数之和等于边数的两倍sum_{v in V} deg(v) 2|E|推论无向图中度数为奇数的顶点个数一定是偶数。3.2 路径、回路与连通性术语 定义路径Path 顶点序列 v_0, v_1, dots, v_k使得对每个 i{v_i, v_{i1}} in E或 (v_i, v_{i1}) in E且序列中顶点不重复。通路Walk 类似路径但允许顶点和边重复。回路/环Cycle 起点和终点相同的路径即 v_0 v_k且 k geq 3无向图。连通Connected 无向图中若顶点 u 和 v 之间存在路径则称 u 和 v 连通。连通图 若图中任意两个顶点都连通则称该图为连通图。连通分量 无向图的极大连通子图。强连通Strongly Connected 有向图中若对任意 u, v in V既存在 u to v 的路径也存在 v to u 的路径则称该有向图为强连通图。3.3 子图与补图子图Subgraph若 V subseteq V 且 E subseteq E则 G (V, E) 是 G 的子图。生成子图/支撑子图Spanning SubgraphV V 的子图。补图Complement Graphbar{G} (V, bar{E})其中 {u, v} in bar{E} 当且仅当 {u, v} notin E。四、图的分类体系4.1 按边的性质分类类别 特征 说明简单图Simple Graph 无自环、无重边 最基本的图类型多重图Multigraph 允许重边平行边 两个顶点间可有多条边伪图Pseudograph 允许自环和重边 最一般化的图有权图Weighted Graph 每条边附有权值 w(e) 用于建模距离、成本等4.2 按结构特征分类类别 特征完全图Complete Graph K_n 任意两个不同顶点之间都有边相连 E frac{n(n-1)}{2}二部图Bipartite Graph 顶点集可划分为两个不相交子集 V X cup Y每条边的两个端点分别属于 X 和 Y树Tree 连通且无回路的无向图 E V - 1有向无环图DAG 不含任何回路的有向图平面图Planar Graph 可以画在平面上且边不相交的图正则图Regular Graph 所有顶点的度数相同五、图的存储表示在计算机中实现图算法首先需要选择合适的数据结构来存储图。常用的有以下几种5.1 邻接矩阵Adjacency Matrix用一个 n times n 的矩阵 A 表示图其中 n |V|A[i][j] begin{cases}1 text{或权值 } w_{ij}text{}, text{若 } (v_i, v_j) in E \0 text{或 } inftytext{}, text{否则}end{cases}空间复杂度O(|V|^2)优点查询边是否存在的时间为 O(1)适合稠密图。缺点空间浪费大稀疏图时遍历邻居的时间为 O(|V|)。5.2 邻接表Adjacency List为每个顶点维护一个链表存储与该顶点相邻的所有顶点V0 → V1 → V3V1 → V2V2 → V0V3 → V2空间复杂度O(|V| |E|)优点空间高效遍历邻居的时间与该顶点的度成正比适合稀疏图。缺点查询特定边需要遍历链表时间为 O(deg(v))。5.3 边集数组Edge List直接存储所有边的列表每条边用 (u, v, w) 三元组表示。空间复杂度O(|E|)适用场景Kruskal 等以边为操作对象的算法。5.4 对比总结表示方式 空间复杂度 查询边 遍历邻居 适用场景邻接矩阵 O(V^2) O(1) O(V) 稠密图邻接表 O(VE) O(deg v) O(deg v) 稀疏图边集数组 O(E) O(E) O(E) 边操作算法六、图的经典算法6.1 图的遍历6.1.1 深度优先搜索DFS, Depth-First Search思想从起始顶点出发沿一条路径尽可能深地探索直到无法继续时回溯再探索下一条路径。类似于走迷宫时的一条路走到黑策略。时间复杂度O(|V| |E|)邻接表应用连通分量检测、拓扑排序、强连通分量Tarjan 算法、环检测等。6.1.2 广度优先搜索BFS, Breadth-First Search思想从起始顶点出发先访问所有直接相邻的顶点再依次访问距离为 2、3、... 的顶点。类似于水波纹向外扩散。时间复杂度O(|V| |E|)邻接表应用无权图最短路径、层序遍历、连通分量等。6.2 最短路径算法算法 适用条件 时间复杂度 核心思想Dijkstra 算法 非负权边 O((VE)log V) 贪心策略逐步扩展最近顶点Bellman-Ford 算法 允许负权边 O(VE) 动态规划松弛所有边Floyd-Warshall 算法 全源最短路径 O(V^3) 动态规划枚举中间顶点**A* 算法** 有启发函数 取决于启发函数 启发式搜索6.3 最小生成树MST算法 策略 时间复杂度Kruskal 算法 按边权排序贪心选边 O(E log E)Prim 算法 从顶点出发贪心扩展 O((VE)log V)6.4 拓扑排序Topological Sort适用对象有向无环图DAG定义将图中所有顶点排成一个线性序列使得对每条有向边 (u, v)u 都出现在 v 之前。方法基于 BFSKahn 算法利用入度或基于 DFS。应用任务调度、课程安排、编译依赖分析等。七、图的实际应用7.1 社交网络分析顶点用户边好友关系 / 关注关系应用好友推荐共同邻居、PageRank、社区发现模块度优化、影响力传播模型SIR/IC 模型7.2 交通与物流网络顶点城市 / 交叉路口边道路 / 航线权值为距离或时间应用导航最短路径Dijkstra / A*、物流配送优化TSP / VRP7.3 互联网与万维网顶点网页边超链接有向应用Google PageRank 算法基于有向图的链接分析、网页爬虫策略7.4 生物信息学顶点蛋白质 / 基因边相互作用关系应用蛋白质交互网络分析、基因调控网络建模、药物靶点发现7.5 编译原理顶点代码中的变量 / 基本块边数据依赖 / 控制流应用控制流图CFG分析、寄存器分配图着色、死代码消除7.6 推荐系统顶点用户 物品构成二部图边购买 / 评分 / 点击行为应用协同过滤、图嵌入GraphSAGE、GAT、知识图谱推理八、图论的前沿研究方向方向 说明图神经网络GNN 将深度学习应用于图结构数据如 GCN、GAT、GraphSAGE 等大规模图计算 分布式图处理框架如 Pregel、GraphX、Neo4j动态图 / 时序图 研究边随时间变化的图结构图生成模型 利用生成对抗网络GAN或扩散模型生成图结构知识图谱 大规模异构信息网络的构建、推理与查询九、结论图作为一种强大而灵活的数学模型其核心价值在于能够将复杂的实体关系抽象为简洁的顶点与边的结构。从欧拉的七桥问题到当代的图神经网络图论经历了从纯数学理论到跨学科应用工具的深刻演变。在计算机科学中图不仅是算法设计与分析的重要载体更是大数据时代处理关系型数据的核心基础设施。深入理解图的定义、性质与算法对于从事计算机科学及相关领域研究的人员而言具有不可替代的基础性意义。