数据结构与算法第六章图

noruta

675人浏览 · 2025-07-08 00:44:18

noruta · 2025-07-08 00:44:18 发布

6.1 图的基本概念

图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。

若V={v₁,v₂,…,v_n}，则用|V|表示图G中顶点的个数，也称图G的阶。

E={(u,v)|u∈V，v∈V}，用|E|表示图G中边的条数

注意： 图不能是空，即V一定是非空集

在这里插入图片描述

无向图、有向图

若E是无向边的有限集合，则图G为无向图，且(v,w)=(w,v)

在这里插入图片描述

若E是有向边(弧)的有限集合，则图G为有向图。弧是顶点的有序对，记为<v,w>，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧。<v,w>≠<w,v>

在这里插入图片描述

简单图、多重图

简单图：不存在重复边，不存在顶点到自身的边

多重图：存在重复的边，或结点自身连向自身的边

在这里插入图片描述

顶点的度、入度、出度

$对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。\\在具有n个顶点、e条边的无向图中，\sum_{i=1}^{n} TD(v_i) = 2e\\即无向图的全部顶点的度的和等于边数的2倍$

$对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v)；\\出度是以顶点v为起点的有向边的数目，记为OD(v)。\\顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。\\在具有n个顶点、e条边的有向图中，\sum_{i=1}^{n} ID(v_i) = \sum_{i=1}^{n} OD(v_i) = e$

顶点-顶点的关系描述

路径——顶点v_p到顶点v_q之间的一条路径是指顶点序列，v_p, v_i1, v_i2, …, v_q
回路——第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度——路径上边的数目
点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。

常见考点：
$对于n个顶点的无向图G，若G是连通图，则最少有n-1条边；若G是非连通图，则最多可能有C_{n-1}^{2}条边$
在这里插入图片描述

若图中任意一对顶点都是强连通的，则称此图为强连通图

常见考点：
$对于 n 个顶点的有向图 G ，若是强连通图，则最少有 n 条边（形成回路）。$
在这里插入图片描述

图的局部——子图

设有两个图G = (V, E)和G’ = (V’, E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。

若有满足V(G’) = V(G)的子图G’，则称其为G的生成子图。

在这里插入图片描述

连通分量

在这里插入图片描述

强连通分量

在这里插入图片描述

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少，但保持连通）

若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边就会形成一个回路。

在这里插入图片描述

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林

在这里插入图片描述

边的权、带权图/网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

6.2 邻接矩阵法

#define MaxVertexNum 100;	// 顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];		// 顶点表
    int Edge[MaxVertexNum];		// 邻接矩阵
    int vexnum,arcnum;		// 图的当前顶点数和边数/弧数
}MGragp;

在这里插入图片描述

$E)的邻接矩阵A是n\times n的。将G的顶点编号为v_1, v_2, \ldots, v_n，则\\A[i][j] = \begin{cases} 1, & \text{若 } (v_i, v_j) \text{ 或 } \langle v_i, v_j \rangle \text{ 是 } E(G) \text{ 中的边} \\0, & \text{若 } (v_i, v_j) \text{ 或 } \langle v_i, v_j \rangle \text{ 不是 } E(G) \text{ 中的边}\end{cases}$
无向图中：第i个结点的度=第i行（或第i列）的非零元素个数

有向图中：第i个结点的出度=第i行的非零元素个数

第i个结点的入度=第i列的非零元素个数

第i个结点的度=第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

存储带权图（网）

#define MaxVertexNum 100;	// 顶点数目的最大值
#define INFINITY 最大的int值	// 宏定义常量“无穷”
typedef char VertexType;	// 顶点的数据类型
typedef int EdgeType;	// 带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];		// 顶点
    EdgeType Edge[MaxVertexNum];		// 边的权
    int vexnum,arcnum;		// 图的当前顶点数和弧数
}MGragp;

在这里插入图片描述

邻接矩阵法的性能分析

空间复杂度：O(|V|²)——只和顶点数相关，和实际的边数无关

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

邻接矩阵法的性质

设图G的邻接矩阵为A，则Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目

在这里插入图片描述

6.3 邻接表法

//顶点
typedef struct VNode{
    VertexType data;	// 顶点信息
    ArcNode *first;		// 第一条边/弧
}VNode,AdjList[MaxVertexNum];

// 边
typedef struct ArcNode{
    int adjvex;		// 边/弧指向哪个结点
    struct ArcNode *next;	// 指向下一条弧的指针
    // InfoType info;	// 边权值
}ArcNode;

// 用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vernum,arcnum;
}ALGraph;

在这里插入图片描述

邻接表法适合存储稀疏图，表示方式不唯一，计算有向图的入度、入边不方便。

6.4 十字链表、邻接多重表

十字链表存储有向图

在这里插入图片描述

性能分析

空间复杂度：O(|V|+|E|)

如何找到指定顶点的所有出边？顺着绿色线路找

如何找到指定顶点的所有入边？顺着橙色线路找

邻接多重表存储无向图

在这里插入图片描述

空间复杂度：O(|V|+|E|)

在这里插入图片描述

6.5 图的基本操作

Ajacent(G,x,y)：判断图G是否存在边<x,y>或(x,y)

在无向图中，邻接矩阵只需要检查x与y对于的元素是否为1即可，时间复杂度为O(1)；在邻接表中，最好的情况是边节点的第一个元素就是想要查找的那个元素，最坏的情况是这个顶点连接了v-1个其他的顶点，且遍历到最后一个边节点才找到目标元素，因此时间复杂度为O(1)~O(|V|)。同理，有向图的邻接矩阵和邻接表也是如此。

Neighbors(G,x)：列出图G中与结点x邻接的边

在无向图中，邻接矩阵只要查看x对应的那一行元素哪个为1即可，时间复杂度为O(|V|)；在邻接表中，若x的边节点只连接了一个，时间复杂度为O(1)，若连接了v-1个，时间复杂度为O(|V|)

在有向图中，在邻接矩阵中查找的时间复杂度和无向图一样；在邻接表中，查找出边的时间复杂度和无向图一样，而查找入边，最坏情况是要遍历所有顶点的边节点，时间复杂度为O(|V|)

InsertVertex(G,x)：在图G中插入顶点x

无向图中，在邻接矩阵中插入结点只需要增添最后面的一行一列即可，邻接表只需要在后面增添节点与指向的边结点，时间复杂度都为O(1)，同理有向图也是如此。

DeleteVertex(G,x)：从图G中删除顶点x

在无向图中，将邻接矩阵中要删除结点的一行一列置为空，时间复杂度为O(|V|)；邻接表中将删除结点的指向指针置为空，并且要遍历每个边将其他结点指向被删除元素的指针置为空，时间复杂度为O(1)~O(|V|)

同理的，对于有向图的邻接表，删出边所需要的时间复杂度也是O(1)~O(|V|)，删入边就是遍历每条边，时间复杂度为O(|E|)。

AddEdge(G,x,y)：若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边

无论是有向图还是无向图，在邻接矩阵中对于的位置改成1即可，在邻接表中使用头插法插入结点即可，时间复杂度都为O(1)。

RemoveEdge(G,x,y)：若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边

无向图中，将邻接矩阵对应的元素值改为0，时间复杂度为O(1)；在邻接表需要先找到该边再删除，时间复杂度为O(1)~O(|V|)。同理有向图也是如此。

FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1

在邻接矩阵中时间复杂度为O(1)~O(|V|)，在邻接表中时间复杂度为O(1)

NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。

Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。

Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。

6.6 图的广度优先遍历

若树非空，则根节点入队
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
重复2直到队列为空

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一

同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一

bool visited[MAX_VERTEX_NUM];	// 访问标记数组
void BSFTraverse(Graph G){
    for(i=0;i<G.vexnum;i++)
        visited[i]=FALSE;	// 访问标记数组初始化
    InitQueue(Q);	// 初始化辅助队列
    for(i=0;i<G.vexnum;i++)		// 从0号顶点开始遍历
        if(!visited[i])		// 对每个联通分量调用一次BFS
            BFS(G,i);	// vi未访问过，从vi开始BFS
}
// 广度优先遍历
void BFS(Graph G,int v){	// 从顶点v出发，广度优先遍历图G
    visit(v);	// 访问初始顶点v
    visited[v]=TRUE;	// 对v做已访问标记
    Enqueue(Q,v);	// 顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);	// 顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            // 检测所有结点
            if(!visited[w]){	// w为v的尚存未访问的邻接结点
                visited(w);
                visited[w]=TRUE;	// 对w做已访问标记
                Enqueue(Q,w);	// 顶点w入队列
            }
    }
}

结论：对于无向图，调用BFS函数的次数=连通分量数

最坏情况下，辅助队列大小为O(|V|)

复杂度分析

在这里插入图片描述

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点，时间复杂度为O(|V|²)

邻接表存储的图：

访问|V|个顶点需要O(|V|)的时间

查找各个顶点的邻接点共需要O(|E|)的时间，时间复杂度为=O(|V|+|E|)

广度优先生成树

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

在这里插入图片描述

6.7 图的深度优先遍历

bool visited[MAX_VERTEX_NUM];	// 访问标记数组
void DSFTraverse(Graph G){
    for(v=0;v<G.vexnum;++v)
        visited[i]=FALSE;	
    for(v=0;v<G.vexnum;++v)		
        if(!visited[i])		
            DFS(G,i);	
}
// 广度优先遍历
void DFS(Graph G,int v){	// 从顶点v出发，广度优先遍历图G
    visit(v);	// 访问初始顶点v
    visited[v]=TRUE;	// 对v做已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){	// w为v的尚存未访问的邻接结
            DFS(G,w);
        }
    }
}

复杂度分析

在这里插入图片描述

时间复杂度和广度优先遍历的一样

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一

同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一

深度优先生成森林

与广度优先生成森林一样，由遍历过程决定

图的遍历与连通性

在这里插入图片描述

6.8 最小生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

Prim算法

从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

时间复杂度为O(|V|²)，适合用于边稠密图

Kruskal算法

每次选择一条权值最小的边，使这条边的两头联通（原本已经连通的就不选），直到所有结点都连通

时间复杂度为O(|E|log₂|E|)，适合用于边稀疏图

Prim算法的实现思想

在这里插入图片描述

从V₀开始，总共需要n-1轮处理，每一轮处理循环遍历所有结点，找到lowCost最低的，且还没加入树的顶点。再次循环遍历，更新还没加入的各个顶点的lowCost值（每一轮时间复杂度为O(2n)）。总的时间复杂度为O(n²)，即O(|V|²)。

Kruscal算法的实现思想

在这里插入图片描述

共执行e轮，每轮判断两个顶点是否属于同一集合，需要O(log₂e)，总时间复杂度O(elog₂e)

6.9 最短路径问题——BFS算法

单源最短路径问题研究的是一个点到其余每个点的最短距离

在这里插入图片描述

BFS求无权图的单源最短路径

void BFS_MIN_Distance(Graph G,int u){
    // d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;i++){
        d[i]=∞;		// 初始化路径长度
        path[i]=-1;	// 最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=True;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,u);
        for(w=FirstNeighbor(G,u);w=NextNeighbor(G,u,w))
            if(!visited[w]){
                d[w]=d[u]+1;	// 路径长度加1
                path[w]=u;		// 哪一个结点过来的
                visited][w]=TRUE;
                EnQueue(Q,w);
            }
    }
}

所得的生成树一定是以起点为根，高度最小的生成树

6.10 最短路径问题——Dijkstra算法

BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图，于是衍生出了Dijkstra算法

在这里插入图片描述

V₀到V₂的最短路径长度为：dist[2]=9

通过path[]可知，V₀到V₂的最短路径：V₂<–V₁<–V₄<–V₀

初始：若从V₀开始，令 final[0]=true; dist[0]=0; path[0]=-1。其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]=(arcs[0][k]==∞) ? -1 : 0

n-1轮处理：循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i]=true。并检查所有邻接自Vi的顶点，对于邻接自Vi的顶点Vj，若final[j]==false 且 dist[i]+arcs[i][j] < dist[j]，则令 dist[j]=dist[i]+arcs[i][j]; path[j]=i。（注：arcs[i][j]表示V_i到V_j的弧的权值）

时间复杂度：O(n²)即O(|V|²)

此算法不适用于有负权值的带权图

6.11 最短路径问题——Floyd算法

在这里插入图片描述

for(int k=0;k<n;k++){	// 考虑以Vk作为中转点
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(A[i][j]>A[i][k]+A[k][j]){	// 以Vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];	// 更新最短路径长度
                path[i][j]=k;	// 中转点
            }
        }
    }
}

时间复杂度为O(n³)，空间复杂度为O(n²)

该算法不能解决带有“负权回路”的题

	BFS算法	Dijkstra算法	Floyd算法
无权图	√	√	√
带权图	×	√	√
带负权值的图	×	×	√
带负权回路的图	×	×	×
时间复杂度	O(\|V\|²)或O(\|V\|+\|E\|)	O(\|V\|²)	O(\|V\|³)
通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

6.12 有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）

Step 1：把各个操作数不重复地排成一排

Step 2：标出各个运算符的生效顺序（先后顺序有点出入无所谓）

Step 3：按顺序加入运算符，注意“分层”

Step 4：从底向上逐层检查同层的运算符是否可以合体

在这里插入图片描述

合体后：

在这里插入图片描述

6.13 拓扑排序

AOV网（Activity On Vertex NetWork，用顶点表示活动的网）

拓扑排序的实现：

从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
从网中删除该顶点和所有以它为起点的有向边。
重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

在这里插入图片描述

#define MaxVertexNum 100  // 图中顶点数目的最大值

typedef struct ArcNode{   // 边表结点
    int adjvex;           // 该弧所指向的顶点的位置
    struct ArcNode *nextarc;  // 指向下一条弧的指针
    InfoType info;       // 网的边权值
}ArcNode;

typedef struct VNode{    // 顶点表结点
    VertexType data;     // 顶点信息
    ArcNode *firstarc;   // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{        // Graph是以邻接表存储的图类型
    AdjList vertices;
    int vexnum,arcnum;
} Graph;

bool TopologicalSort(Graph G){  // 拓扑排序函数
    InitStack(S);  // 初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);  // 将所有入度为0的顶点进栈
    int count=0;  // 计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){  // 栈不空，则存在入度为0的顶点
        Pop(S,i);  // 栈顶元素出栈
        printf("%d ",i);  // 输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){  // 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);  // 入度为0，则入栈
        }
    } // while
    if(count<G.vexnum)  // 排序失败，有向图中有回路
        return false;
    else
        return true;  // 拓扑排序成功
}

逆拓扑排序的实现——DFS算法

void DFSTraverse(Graph G){  // 对图G进行深度优先遍历
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;  // 初始化已访问标记数据
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}

void DFS(Graph G,int v){  // 从顶点v出发，深度优先遍历图G
    visit(v);  // 访问顶点v
    visited[v]=TRUE;  // 设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){  // w为v的尚未访问的邻接顶点
            DFS(G,w);
        }  // if
}

6.14 关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网 (Activity On Edge Network)。

具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。若关键活动不能按时完成，整个工程的完成时间会延长。

事件 v_k 的最早发生时间 ve(k) —— 决定了所有从 v_k 开始的活动能够开工的最早时间

事件 v_k 的最迟发生时间 vl(k) —— 它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动 a_i 的最早开始时间 e(i) —— 指该活动弧的起点所表示的事件的最早发生时间

活动 a_i 的最迟开始时间 l(i) —— 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

活动 a_i 的时间余量 d(i)=l(i)−e(i)，表示在不增加完成整个工程所需总时间的情况下，活动 a_i 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0 即 l(i)=e(i) 的活动 ai 是关键活动。

在这里插入图片描述

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能