图的定义和基本术语
图的定义和基本术语
复习定位
图是一种非线性的数据结构——任意两个数据元素之间都可能存在关系(边)。树是一对多的层次关系——图是多对多的网状关系。社交网络中用户是顶点，好友关系是边——这种结构无法用树或线性表表达。理解图的术语后——图的存储、遍历和算法的学习就开始了。
图的定义
图(graph)由顶点集V(vertex)和边集E(edge)组成——记作G=(V,E)。|V|表示顶点数——|E|表示边数。
无向图——边没有方向——(u,v)与(v,u)含义相同。一条边连接两个顶点。
有向图——边有方向——<u,v>表示从u到v的有向边——u为弧尾(起点)v为弧头(终点)。<u,v>和<v,u>含义完全不同。
完全图——任意两个顶点之间都有边：无向完全图有n(n-1)/2条边(每对顶点一条边)；有向完全图有n(n-1)条边(每对顶点之间有两个方向相反的边)。
子图——图G'=(V',E')满足V'⊆V且E'⊆E——则G'是G的子图。
度——在无向图中——顶点v的度是与v关联的边的数数。握手定理：所有顶点度数之和 = 2|E|。在有向图中——入度(指向v的边数)和出度(从v出发的边数)分别为独立的概念。
路径和回路
路径是顶点序列v=v0,v1,...,vk=u满足相邻之间在E中有边。路径的长度=路径上边的数目（或权重之和）。简单路径——路径中没有重复的顶点。回路(cycle)——起点和终点为同一个顶点的路径，且路径长度至少为1，且除首尾外没有重复顶点(简单回路)。
连通性
连通——无向图中顶点u到v存在路径——称u和v连通。如果图中任意两个顶点都连通——该图是连通图。
连通分量——无向图中的极大连通子图。
强连通——有向图中——对于任意两个顶点u和v——存在从u到v的路径且存在从v到u的路径——该图是强连通图。强连通分量——有向图中的极大强连通子图。
图的表示方式
邻接矩阵——用二维数组A[n][n]存储顶点间的关系——A[i][j]=1表示i和j之间有边(对于无向图在矩阵对称位置也是1)。判断两顶点是否相邻为O(1)。但存储空间O(n²)——对于稀疏图(边数远小于n²时候)浪费大量空间。
邻接表——为每个顶点v维护一个链表——存储所有与v相邻的顶点。空间O(n+|E|)——适合稀疏图。在无向图中一条边在邻接表中出现两次(两端各一次)。有向图可以只存出边(出度邻接表)或者也存逆邻接表(入度情况)。
复习检查
无向完全图n=10——有多少条边？如果是有向完全图——总边数是多少？
无向图中所有顶点的度数之和一定等于边数的2倍——用握手定理证明。
连通分量和连通图的区别是什么——如果一个图不是连通的——它有几个连通分量？
邻接矩阵和邻接表分别适用于稠密图还是稀疏图？给出选择的原因(存储空间和遍历所需时间两者考虑的差异)。
一个有向图中入度为0的顶点可以有多少个——入度和不为0的结点的存在可能使这个图成为弱连通图吗(将有向边当作无向边后整体的连通性)？
图的基本概念详解
图(Graph)是比树和线性表更复杂的数据结构——任意两个顶点之间都可以建立联系——这是图的核心特征。
图的数学定义：G=(V,E)——V是顶点的非空有限集合——E是顶点之间边的有限集合。|V|=n是顶点数——|E|=e是边数。
无向图中的边是无序对(u,v)——(u,v)与(v,u)代表同一条边。无向完全图Kn中每对顶点之间都有一条边——边数e=n(n-1)/2。
有向图中的边是有序对<u,v>——<u,v>与<v,u>不同。有向完全图中每对顶点之间都有两条方向相反的边——边数e=n(n-1)。
图的度与握手定理
在无向图中——顶点v的度deg(v)是v关联的边的数量——自回路(循环边)使度增加2(因为连接自身两次)。握手定理——所有顶点的度数之和 = 2|E|——因为每条边关联两个顶点(两个端点)——为每个端点贡献了1度。
在有向图中——入度indeg(v)是终点为v的边的数量——出度outdeg(v)是起点为v的边的数量——度deg(v)=indeg(v)+outdeg(v)所有顶点的入度之和=所有顶点的出度之和=|E|。
握手定理的推论——在任何图中——度数为奇数的顶点个数为偶数——因为奇度顶点的总和为偶数才能满足总度数为偶(2|E|)。
特殊图结构的分类与实际背景
稀疏图: |E|远小于|V|²——社交网络(用户关系、媒体影响)具有典型稀疏性
稠密图: |E|≈|V|²——可以用于描述整个核心网络的情况(如像RTA们需要全互联拓扑时)
有权图: 边上有权重——表示距离/成本/带宽——地图导航的最短路径、网络中的传输时延都是有权图的典型应用
无权图: 边上没有权重——仅表示连通关系——如社交网络的好友关系
二部图: 顶点集可分为两个不相交的集合X和Y——所有边的两个端点分别属于X和Y——如学生选课关系——学生和课程是两个集合。路径与回路的详细分类
路径——顶点序列u=v0,v1,...,vk=v——满足(v_i,v_{i+1})∈E(对无向图)或<v_i,v_{i+1}>∈E(对有向图)所有相邻顶点对都存在的有向或无向关系序列。
简单路径——路径中所有顶点都不重复。基本路径——路径中除首尾外其他顶点都不重复。
回路(环): 起点=终点的路径(长度≥1)
简单回路: 起点=终点——且中间顶点不重复的回路
有向图中如果有>1的回路——可能意味着无穷遍历循环
无向图中回路的存在意味着图不是树(树是无环连通图)回路的存在与否是区分树(无环连通图)和非树图结构的重要特征。
图的连通性——无向图与有向图对比
| 连通性概念 | 无向图 | 有向图 |
|---|---|---|
| 连通 | 任意两顶点间有路径 | 忽略方向后任意两顶点间有路径(弱连通) |
| 强连通 | — | 任意两顶点间双向都有路径 |
| 连通分量 | 极大连通的子图 | 极大强连通的子图(强连通分量) |
| 弱连通分量 | — | 将有向边视为无向边后的连通分量 |
连通分量是判断图整体结构的核心概念——一个非连通图由多个连通分量组成——每个连通分量内部连通——分量之间不连通。在社交网络分析中——连通分量代表了"互相可达的人群"——孤立顶点是一个连通分量——大型连通分量可能代表了在网络上高度互相关注的作者之间组成的大社区。
图的存储——邻接矩阵的详细设计
邻接矩阵A[n][n]中：
A[i][j] = 1 (如果顶点i和j之间有边)
A[i][j] = 0 (如果顶点i和j之间没有边)
对于有权图: A[i][j] = w(i,j) (如果顶点i和j之间有边) — INF(如果无直接边)
对于无向图: 矩阵对称——A[i][j]=A[j][i]
对于有向图: 矩阵不一定对称——A[i][j]表示i→j的边邻接矩阵的主要优势：判断两个顶点是否相邻O(1)时间。主要劣势：存储空间O(n²)——对稀疏图浪费严重。1亿个顶点(108)形成1016规模的矩阵——无法存储在现有最大存储中——所以大图(如数十亿条边的社交网络图)不可能用邻接矩阵存储。
邻接表的实现与优化
邻接表的存储结构由顶点数组+顶点内维护的链表组成——每个顶点v的链表存储所有与v相邻的顶点。对于稀疏图——总空间O(|V|+|E|)远小于邻接矩阵的O(|V|²)。
无向图的邻接表: 每条边在邻接表中出现2次(两端各一次)
有向图的邻接表(出边表): 每个顶点只存储从该顶点出发的有向边——用于正向遍历
有向图的逆邻接表(入边表): 每个顶点只存储指向该顶点的有向边——用于反向遍历优化版本的邻接表(邻接数组)中——使用动态数组(vector/ArrayList)替代链表——通过连续内存存储所有邻接点——减少指针的开销并提高顺序访问的Cache友好性——在大多数图算法中比链表实现更快。
图的四种存储结构对比总表
| 存储结构 | 空间 | 判断边是否存在 | 遍历邻接边 | 适用场景 |
|---|---|---|---|---|
| 邻接矩阵 | O(n²) | O(1) | O(n) | 稠密图、需要快速判断边存在 |
| 邻接表 | O(n+e) | O(度) | O(度) | 稀疏图、以遍历为主 |
| 逆邻接表 | O(n+e) | O(入度) | O(入度) | 需要频繁查找"入边"的有向图 |
| 十字链表 | O(n+e) | O(度) | O(出度+入度) | 有向图的双向高效遍历 |
在实际工程中——对于节点数<1000且边密度>50%的图——选择邻接矩阵更加简便；对于大多数边的节点数大但边稀疏的应用(社交网络、推荐算法、神经网络构图等)——邻接表(尤其是邻接数组版本)是最优的默认选择。
复习检查（续）
无向完全图n=10的边数——10×9/2=45——有向完全图n=10的边数——10×9=90。
握手定理——所有顶点的度数之和=2|E|——因为每条边关联两个顶点——每个顶点计算度数时被计入一次。
非连通图的连通分量数=顶点数时——说明图中没有任何边——每个顶点自成连通分量。
邻接矩阵适用于稠密图——O(1)判断边存在——但O(n²)空间在稀疏图中浪费极大——邻接表适用于稀疏图——空间O(n+e)——遍历邻接点效率高。
有向图中入度为0的顶点可以任意多个——将边看作无向边后的弱连通性需根据具体图的结构判断。
图术语的应用场景与实际背景
图的各类术语不仅仅是抽象概念——它们在现实世界中有具体映射：
连通分量: 社交网络中互相可达的用户群体——一个大型连通分量可能包含几百万用户
强连通分量: 网页之间的链接关系——网页A到B有链接——B到A也有链接
完全图: 小型全连接网络中所有节点两两互联的情况——如一个办公室内的本地路由器之间用OSPF协议有时全互连
森林: 若干棵树的集合——在并查集(union-find)数据结构中初始状态为n个节点组成的森林
生成树: 连通图的一个极小连通子图——包含所有顶点——但只有n-1条边——如以太网中的STP(生成树协议)用来消除环形网络中的帧的循环理解图术语的实际背景有助于在遇到实际建模问题时选择合适的图结构来描述变量/实体之间的关系。
有向图和无向图的学习路线图
图论的基础学习路线:
基本概念(无向/有向/度)
→ 图的存储(邻接矩阵/邻接表)
→ 图的遍历(DFS/BFS)
→ 最小生成树(Prim/Kruskal)
→ 最短路径(Dijkstra/Floyd/Bellman-Ford)
→ 拓扑排序与关键路径(有向无环图应用)
→ 强连通分量(Tarjan/Kosaraju)
→ 网络流(最大流/最小割)从基本术语开始逐步深入到图的各类经典算法——每步建立在前一步的基础上——形成完整的图论知识体系。考试中——图的基本术语(连通性/度/路径)是选择题高频考点——图的遍历和最短路径是综合题常规考点。
图的几种存储实现方式的代码对比
邻接矩阵的C语言表示：
#define MAXV 1000
int graph[MAXV][MAXV]; // 0表示无边——1表示有边(有权图可改int表示权重)
// 初始化——全部设为0
memset(graph, 0, sizeof(graph));
// 添加边
graph[u][v] = 1; // 无向图还需要 graph[v][u] = 1邻接表的C语言表示：
typedef struct EdgeNode {
int adjvex; // 邻接点下标
int weight; // 权值(有权图使用)
struct EdgeNode *next; // 下一个邻接点
} EdgeNode;
typedef struct {
EdgeNode *first; // 边的链表头
} AdjList[MAXV];在C++中——常用vector<vector<int>> adj(n)代替纯C的链表实现——因为vector连续存储、迭代器访问直接且更快——在CP(竞赛编程)和一般的企业笔试编程题中是邻接表的默认首选。