图

约 6617 字大约 22 分钟

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的所有未访问过的邻接顶点，再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。

BFS是一层一层的往外遍历，每一层会有一批结点，不会出现回退现象，不是一个递归算法，实现该算法需要一个辅助队列，用来记忆正在访问结点的下一层结点。

BFS整体思路代码

//访问数组，初始为false，表示所有结点都没有访问
bool visited[100];
//广度优先搜索
void bfs_traverse(graph G){
    for(int i = 0; i < G.v_num; i++){
        visited[i] = false;
    }
    //初始化辅助队列
    queue *Q = init_queue();
    for(int i = 0; i < G.v_num; i++){
        //若没有访问过i结点，则从i结点开始广度搜索
        if(visited[i] == false){
            bfs(G, i);
        }
    }
}

整体思路如上述代码，具体的bfs函数实现，需根据图的实现决定，但思路类似，以邻接矩阵实现的图举例：

邻接矩阵图的bfs实现

void bfs(adj_martix_graph G, int i){
    //访问结点
    printf("%d ", i);
    //表明该结点已经访问过了
    visited[i] = true;
    //将初始结点入队
    en_queue(Q, i);
    //队列中有结点的话，进行不断地遍历
    while(!is_empty(Q)){
        //队列中第一个结点出队
        int v = de_queue(Q);
        //判断出队的结点有没访问过的下一层结点没，有的话，访问后入队
        for(int k = 0; k < G.v_num; k++){
            if(visited[k] == false && G.edg[v][k] == 1){
                printf("%d", k);
                visited[k] = true;
                en_queue(Q, k);
            }
        }
    }
}

因为BFS需要一个辅助队列Q，其包含访问结点的下一层结点，所以最差的情况（除初始结点外，所有结点都是初始结点的下一层结点），空间复杂度为 $O(|V|)$ 。

按照bfs函数具体的实现不同，遍历图的时间复杂度就不同，采用邻接表存储时，时间复杂度为 $O(|V|+|E|)$ ；采用邻接矩阵存储时，时间复杂度为 $O(|V|^2)$ 。

BFS是可以用来求非带权图的单源最短路径问题，其实是默认每条边上的权值为1。

也可以使用BFS得到一颗遍历树，称为广度优先生成树。图的邻接矩阵存储表示是唯一的，所以其广度优先生成树也是唯一的，但邻接表存储并不是唯一的，和结点输入次序有关。

深度优先搜索

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

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

DFS整体思路代码

    bool visited[100];
    void dfs_traverse(graph G){
        for(int i = 0; i < G.v_num; i++){
            visited[i] = false;
        }
        for(int i = 0; i < G.v_num; i++){
            if(visited[i] == false)
                dfs(G, i);    
        }
    }

邻接矩阵图的dfs实现

    void dfs(adj_martix_graph G, int i){
        
    }

DFS显然是一个递归算法，所以其空间复杂度为 $O(|V|)$ ，遍历图的本质都是通过边查找邻接点的过程，所有DFS的时间复杂度和BFS的一样。

同样的，DFS也会产生一颗树，称为深度优先生成树，当然，这个是需要一次遍历完图中所有的结点，否则，就是深度优先生成森林了。

和BFS一样，若图使用邻接表存储，则深度优先生成树不唯一。

图的遍历和图的连通性

通过上面的遍历算法就可以判断图是否连通。

对于无向图，若调用1次DFS或BFS可以将图中所有结点全部遍历一次，则为连通，否则该图非连通。

对于有向图，它的连通性稍微复杂一点，其分为：

弱连通：如果忽略边的方向，将有向图变成无向图后，它能被一次DFS或BFS完全遍历，那么原有的向图就是弱连通的。可以理解为，只看路网结构不看单行道，所有地点都能互相到达。
单向连通：图中任意两点 A 和 B 之间，至少存在一条从 A 到 B 的路径或一条从 B 到 A 的路径。这意味着两点之间至少有一个方向是可达的，但不一定能双向互通。
强连通：图中任意两点 A 和 B 之间，同时存在一条从 A 到 B 的路径和一条从 B 到 A 的路径。这是最严格的连通性，所有节点都必须能相互到达。判断强连通通常需要更复杂的算法，而非简单的一次遍历。

通过上述的性质，可知：对于无向图，遍历的次数就为该图的连通分量数；对于有向图，则不一定，因为在一个非强连通分量中，可能都不止调用一次遍历算法才能遍历完该分量。

图的应用

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

最小生成树

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

那什么是最小呢？答案在权上。仅对无向带权图，不同的生成树，其权值可能不同（所有边上权值相加就为该树的权值），权值最小的那颗生成树称为最小生成树（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算法

Dijkstra算法也是基于贪心算法的，总是选取权值最小的边。

思路比较简单，

需要注意，Dijkstra算法只适用于不含有负权值边的图，时间复杂度为 $O(|V|^2)$ ，当每条边的权值为1时，退化为广度优先算法求单源最短路径。

Floyd算法

该算法会产生一个递推n阶方阵，方阵中包含的信息，就是我们需要的最短路径长度。

设该n阶方阵为 $A$ ，初始化方阵为 $A^{-1}$ ，每递推一次幂就增加一位， $A^k[i][j]$ 表示顶点 $v_i$ 到顶点 $v_j$ 的路径长度， $k$ 表示将结点 $v_k$ 也加入到中间结点中运算。

思路：

初始化方阵：将图对应的邻接矩阵初始化，该n阶方阵为 $A^{-1}$
递推：之后的方阵 $A^k$ ，利用状态转移方程计算，如下：

A^k[i][j]=min\{\,A^{k-1}[i][j],\,A^{k-1}[i][k]+A^{k-1}[k][j]\,\},\,\,k=0,1,2,...,n-1

Floyd算法的时间复杂度为 $O(|V|^3)$ ，因为这个是求出任意两点之间的最短路径长度，肯定会比Dijkstra多出一个次方，利用Dijkstra算法也可以求出任意两点之间的最短路径长度，其时间复杂度和Floyd算法一样。

Floyd算法不适用于带回路的图。

有向无环图描述表达式

拓扑排序

拓扑排序：由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
每个顶点出现且只出现一次
若顶点A在序列中排在顶点B之前，则在图中不存在B到A的路径

这里介绍AOV网和AOE网，AOV网是以顶点作为活动，AOE网是以边作为活动。

AOV网

AOV网：若用有向无环图表示一个工程，其顶点表示活动，用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行的一种关系，将这种有向图称为顶点表示活动的网络，简称AOV网。

在AOV网中，重点讨论的就是拓扑排序，从入度为0的结点开始，然后选取该结点后，将与该结点连接的边全部去掉，又选取入度为0的结点，依次类推，将整个图的结点选取结束得到的结点序列，就为拓扑排序。

当然，也可能不存在拓扑排序，就是在选取结点中没有入度为0的结点，此时图中不存在环。

AOE网

AOE网：

在AOE网中有个重要的组成部分——关键路径，关键路径长度表示工程完成需要的最小时间开销。

而求解关键路径由什么活动构成的重点在于求每个事件的最早发生时间和最迟发生时间，尽管最后，是用活动最早开始时间减去活动最迟时间是否为0，判断关键路径中是否有该活动的。但活动的最早开始和最迟开始时间都是用前者求出来的，下面我就来仔细说说怎样求解关键路径。

关键路径

关键路径：

更新日志

2025/6/30 14:16

查看所有更新日志

c0b79-docs:数据结构-图🚀于 2025/6/30
40c38-docs:数据结构-图🚀于 2025/6/29
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)