图

约 4662 字大约 16 分钟

2025-05-16

什么是图

图的定义和常见场景

图在我们日常生活十分常见，如：qq联系人、地图、交通网络、计算机网络等等，是一种多对多的数据结构。

图的定义：图G由顶点集V和边集E组成，记为 G = (V, E) ，其中 V(G) 表示图G中顶点的有限非空集； E(G) 表示图G种边的集合。若V={v1,v2,...v1,v2,...}则|V|表示G中顶点的个数，E={(u, w)|u∈V,v∈V}，则|E|代表G中边的条数。

通俗来讲，图就是一个点集加上一个边集构成的数据结构，边集中的边由点集中的点构成。

图可以看做链表、树的超集，其中包含着这些数据结构的影子。需要注意的是，线性表和树可以是空的，但图不能，点集中至少也得有一个顶点，边集可以为空。

图的基本概念

有向图：G中的E为有向边（带箭头），该有向边称为弧，箭头指的结点w为弧头，另一端结点v为弧尾，记为<v, w>，称 v邻接到w
无向图：G中的E为无向边（不带箭头），该无向边称为边，记为(v, w)或(w, v)，没有顺序可言，称 v和w相互邻接
简单图：G中不存在重复边，不存在顶点到自身的边
顶点的度、出度和入度：出度和入度是对于有向图而言，见名知义，顶点的入度就是箭头指向该结点的个数，出度反之；度是有向图和无向图都存在的概念，对于有向图，度为出度、入度之和；对于无向图，度为顶点上所有边的条数
路径、路径长度和回路：两个不同顶点v、w及之间经历的一些顶点构成一条路径，相关联的边也可以视为路径的构成元素。无权图中，路径上的边的条数为路径长度；带权图则是路径上边对应的权值之和。第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径、简单回路：顶点不重复出现的路径称为简单路径，除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
距离：距离是在最短路径上讨论的，对于无权图，距离就是路径长度；对于带权图，距离是路径上边的权值之和
子图：图G=(V, E)和图G'=(V', E')，其中V'是V的子集，且E'是E的子集，则称G'是G的子图，但若E的子集E'中的某些边关联的顶点不在V的子集V'中，则不能构成子图G'
连通、连通子图和连通分量：在无向图中，顶点v到顶点w之间存在路径，则称v和w是连通的。若无向图中的任意两个顶点都是连通的，则该图为一个连通图，否则为非连通图。其中的极大连通子图称为极大连通分量
强连通图和强连通分量：这个和上面的类似，只不过针对的是有向图。还要保证两个顶点间相互有路径才行。
生成树、生成森林：连通图的生成树是包含途中全部顶点的一个极小连通图（边数最少），因为是连通图，所以只会有一颗生成树，直接遍历完所有结点，但若是非连通图，则就会形成多颗生成树，它们共同组成生成森林
边的权、网和带权路径长度：边上的数值称为该边的权值。若一个图中的所有边带有权值，则该图为带权图（网）。路径上所有边的权值之和，称为该路径的带权路径长度
完全图：边数拉满，其中有向图的边数为 $|V|(|V|-1)$ ，无向图的边数为 $\frac{|V|(|V|-1)}{2}$
稠密图、稀疏图：边多的图称为稠密图，反之为稀疏图，判断依据是边的条数。一般来说，若一个图满足 $|E|<|V|log_2|V|$ ，则该图称为稀疏图
有向树：一个顶点入度为0，且其余顶点的入度都为1的有向图

图的存储结构和基本操作

图的存储结构和树类似，但又更加复杂，因为其要表示顶点与顶点之间多对多的平级关系，而不像树那样严格的层级关系。

除了存储结构外，能对图进行的操作也很重要，先来介绍一下图的存储结构吧！常见的有4种，详细说明在下方：

邻接矩阵法

这是图最简单的存储方式，使用一个二维数组 $A_{n×n}$ 表示，n为图中的顶点数。

A[i][j] = \begin{cases} 1 & \text{如果顶点 } i \text{ 和 } j \text{ 之间有边（在无权图中）} \\ w_{ij} & \text{如果顶点 } i \text{ 到 } j \text{ 之间有权重为 } w_{ij} \text{ 的边（在带权图中）} \\ 0 & \text{如果顶点 } i \text{ 和 } j \text{ 之间没有边（在无权图中）} \\ 0 \text{或} \infty & \text{如果顶点 } i \text{ 到 } j \text{ 之间没有边（在带权图中）} \end{cases}

邻接矩阵结构体

typedef struct adj_matrix{
    //顶点数据
    char vex[100];
    //边表
    int edge[100][100];
    //顶点数和边数
    int vex_num, edge_num;
}adj_matrix;

有关图的邻接矩阵表示的特点：

对于无向图，用不到这么多的空间来存储数据，因为其是相互邻接的，所以其是对称矩阵，可以进行矩阵压缩（只存储上（下）三角矩阵元素）。
对于无向图，邻接矩阵的第i行（或第i列）非零元素个数为顶点i的度TD(vi)。
对于有向图，邻接矩阵的第i行非零元素（或非正无穷元素）为顶点i的出度OD(vi)，第i列非零元素（或非正无穷元素）为顶点i的入度ID(vi)
稠密图适用于邻接矩阵存储表示，这样可以将邻接矩阵的每个空间几乎都利用起来，而且便于判断两个顶点之间是否存在边
设图G的邻接矩阵为 $A$ ，则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点i到顶点j的长度为n的路径的条数

邻接表法

这个方法也较为简单，思路是顺序存储所有顶点，然后将每个顶点邻接的结点，加入到对应顶点的链表中。存在顶点结点和边结点。

邻接表结构体

//边表
typedef struct adj_list_e{
    //弧指向的顶点号
    int v_index;
    //下一跳边
    struct adj_list_e *next_e;
}e_node;

//顶点表
typedef struct adj_list_v{
    //顶点值
    char value;
    //顶点对应的第一条边
    e_node *first_edge;
}v_list[100];

//邻接表
typedef struct adj_list{
    //顶点
    v_list vertices;
    //顶点数和边数
    int vex_num, edge_num;
}adj_list;

有关图的邻接表表示的特点：

邻接表法重心是存储边，所以适用于稀疏图，可以大大减少存储空间
邻接表法需要存储每个顶点和边，所有对于无向图，需要存储空间为 $O(|V|+2|E|)$ ；对于有向图，需要存储空间为 $O(|V|+|E|)$
邻接表法可以很容易得到一个顶点的所有相邻边，只用遍历一条链表则可，时间复杂度为 $O(n)$ ，但是若要确定两个顶点之间是否存在边，则效率很低，需要把整个存储空间都遍历一遍
图的邻接表表示并不是唯一的，它的建立取决于建立邻接表的算法和边的输入次序
邻接表法，对于无向图，某个结点的度为对应边表中的结点个数；对于有向图，某个结点的出度为边表中结点的个数，但是结点的入度需要遍历全部的邻接表，统计该结点在边表中的个数，时间效率低

十字链表法

十字链表法是针对有向图的，提供一种更先进，更方便的存储方式，其包含弧结点和顶点结点。

十字链表法结构体

//弧结点
typedef struct h_node{
    //弧的弧头和弧尾顶点号
    int tail_vex, head_vex;
    //指向弧头相同的下一条弧
    struct h_node *h_link;
    //指向弧尾相同的下一条弧
    struct h_node *t_link;
    //弧结点需要包含的信息
    char info;
}h_node;

//顶点结点
typedef struct d_node{
    //顶点结点包含的数据
    char data;
    //以该顶点为弧头和以该顶点为弧尾的第一条弧
    h_node *first_in, *first_out;
}d_node[100];

//十字链表结构体
typedef struct cross_linked_list{
    d_node vertices;
    int v_num, e_num;
}cross_linked_list;

十字链表法，既容易找到以顶点vi为头的弧，又容易找到以vi为尾的弧，因此容易求得顶点的出度和入度。图的十字链表表示不是唯一的，但一个十字链表只能表示一个图。

邻接多重表法

邻接多重表是针对无向图的，其和上面的十字链表法类似，存在边结点和顶点结点。

邻接多重表结构体

//边结点
typedef struct e_node{
    //存放该边依附的两个顶点的顶点号
    int i_vex, j_vex;
    //指向依附于i_vex和j_vex的下一条边
    struct e_node *i_link, *j_link;
    //存放边上的信息
    char info;
}e_node;

//顶点结点
typedef struct v_node{
    //顶点上的数据
    char data;
    //指向第一条依附于该顶点的边
    e_node *first_side;
}v_node[100];

//邻接多重表结构体
typedef struct adj_multi_table{
    v_node vertices;
    int v_num, e_num;
}adj_multi_table;

在邻接多重表中，某个结点邻接的所有边都会在同一条链表中，因为每条边依附于两个顶点，所以每个边结点同时链接在两条链表中。每个顶点和边都只用存储一次了，不像邻接表，需要存储两倍的边。

四种存储方式总结

特性 / 存储方式	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(V^2)$	无向图： $O(V +2E)$ 有向图： $O(V+E)$	$O(V+E)$	$O(V+E)$
找相邻边	遍历对应行或列的时间复杂度为 $O(V)$	找有向图的入度必须遍历整个邻接表	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一

图的基本操作

常见的关于图的基本操作有（名称可以随意取，但其表含的操作需要理解）：

adjacent(G, x, y)：判断图G是否存在<x, y>或(x, y)
neighbors(G, x)：列出图G中顶点x邻接的边
insert_vertex(G, x)：在图G中插入顶点x
delete_vertex(G, x)：在图G中删除顶点x
add_edge(G, x, y)：若图G中不存在边(x, y)或弧<x, y>，则向图G中添加
remove_edge(G, x, y)：若图G中存在边(x, y)或弧<x, y>，则从图G中移除
first_neighbor(G, x, y)：求图G中顶点x的第一个邻接点，若有则返回顶点号，否则返回-1
next_neighbor(G, x, y)：y和x是邻接的，返回y的除x的下一个邻接结点的顶点号，若y只有x这一个邻接结点，则返回-1
get_edge_value(G, x, y)：获取图G中边(x, y)或弧<x, y>的权值
set_edge_value(G, x, y)：设置图G中边(x, y)或弧<x, y>的权值

对于图的不同实现方式，虽然代码不同，但是思路完全一致，采用不同的实现方式，造成的操作效率也会天差地别，所以在实现时，要考虑好什么样的图实现效率更快。

图的遍历

遍历图中的所有元素可比遍历树复杂，但在树那章已经用到了这里的思维，广度和深度。

广度优先搜索

在树那里广度优先搜索的展示是层序遍历，从根结点开始一层遍历完，再遍历下一层。对于图，也可以采取这样的思路，从开始结点一圈一圈地向外遍历。

BFS基本思想（专业版）：首先访问起始顶点 v，接着由 v 出发，依次访问v的各个未访问过的邻接顶点 w1，w2，...，wi，然后依次访问w1，w2，...，wi的所有未访问过的邻接顶点，再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。

深度优先搜索

“一条道走到黑”是形容深度优先搜索的最好的一句话，在树那是以先序遍历体现的，在图中的某个从某个结点开始，按一个方向搜索到没有下一个节点为止，然后倒退一个结点，再按照这样的搜索方法进行，直到搜索完所有的结点。

DFS基本思想（专业版）：首先访问图中某一起始顶点 v，然后由 v 出发，访问与 v 邻接且未被访问的任意一个顶点 w1，再访问与 w1 邻接且未被访问的任意一个顶点 w2...重复上述过程。当不能再继续往下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述过程，直至图中所有顶点均被访问过为止。

图的遍历和图的连通性

图的应用

图的应用在日常生活中不仅常见，而且是很重要的。常见的是地图上两个地理位置的最短距离，可以用最短路径的算法得出、工作的执行流程可以用有向无环图描述等等。

最小生成树

一个连通图的生成树包含图中所有顶点，并且只含有最少的边，不过这颗生成树若去掉其中一条边，则生成树会变成非连通图；若加上一条边，则会在图中形成一条回路

那什么是最小呢？答案在权上。仅对无向带权图，不同的生成树，其权值可能不同（所有边上权值相加就为该树的权值），权值最小的那颗生成树称为最小生成树（MST）。

由以上的定义可知：

若图G中存在相同权值的边，则有多个MST，因为在选择边时有多种选择
虽然MST不唯一，但是最小的权值是唯一的，且是最小的
MST的边数为顶点数减1

注意

对于MST而言，是保证整体权值相加最小，而不能保证两点之间的路径是最短路径。

怎样构造MST呢？在这里有多种方式，但都是基于贪心算法形成的，这里只介绍Prim算法、Kruskal算法。它们的基本思想都是不断地加入权值最小的边，看是否不产生回路，不产生就加入，否则判断下一边，只是它们两者加入边的方式不同。

Prim算法

该算法需要维护一个顶点集U。

加入的边只能从加入了U的顶点所连接的边中选取，通过图形来看，像一个蛛网的形成过程，是呈扩散状的。

因为加入边时得遍历U中所有的顶点，并从所有顶点连接的边中选取最小权值的边，所以时间复杂度为 $O(|V|^2)$ ，不依赖与边，故Prim算法适用于求边稠密图的MST。

Kruskal算法

这个“狂野”得多，不需要维护边集了，所有边都在它的边集中，每次从全局选取一个权值最小的边，加入到它维护的边集中，只不过要注意不能形成回路了。

Kruskal 算法在每次选择最小权值边时，是通过预先对所有边进行一次排序（时间复杂度为）来实现的。排序完成后，后续只需顺序遍历这些已排序的边。虽然理论上也可以用最小堆来动态获取最小权值边（每次取出并维护的复杂度为 $O(log_2∣E∣)$ ，总共 $∣E∣$ 次），但通常更倾向于一次性排序

在遍历边时，判断是否形成回路是借助并查集完成的。并查集执行 find 和 union 操作的时间复杂度接近常数级 $O(α(∣V∣))$ ，可以忽略不计。所以Kruskal算法的时间复杂度为 $O(|E|log_2|E|)$ ，不依赖顶点，故Kruskal算法适用于求点稠密图的MST。

最短路径

带权路径长度：当图是带权图时，把一个顶点 $v_0$ 到图中任意个顶点 $v_i$ 的一条路径所经过边上的权值之和
最短路径：带权路径最短的那条路径

当图是带权图时，求最短路径介绍两种方法，分别为Dijkstra算法和Floyd算法。当然，如果求解最短路径是在无权图中（每条边的权值默认为1），则广度优先搜索也是可以用来求最短路径。

要介绍的这两种算法也有不同的适用场景。前者是求 单源最短路径（从某一顶点到其他各顶点的最短路径），后者是求 每对顶点间的最短路径。

Dijkstra算法

Floyd算法

87b71-docs:数据结构-图🚀于 2025/6/25
19cb2-fix:the project add于 2025/6/21
7b20b-fix:git-balabala🚀于 2025/6/21
f47c5-docs:数据结构-所有章节目录🚀于 2025/6/8
162ad-docs:408-sidebar于 2025/5/16

版权所有

版权归属：代码・生活・THINKING

许可证：署名 4.0 国际 (CC-BY-4.0)

图