当前位置：首页 > news >正文

数据结构进阶第七章图（Graph）

news 2025/6/27 15:18:29

第7章图（Graph）

7.1 图的基本术语

图的定义

图是由顶点集合V和边集合E组成的数据结构，记为G=(V,E)，其中：

顶点集V：有限非空集合
边集E：顶点对的集合

基本概念

无向图：边没有方向，用无序对(vi,vj)表示
有向图：边有方向，用有序对<vi,vj>表示
完全图：任意两个顶点之间都有边
稀疏图：边数相对较少的图，|E| < |V|log|V|
密集图：边数相对较多的图

连通性概念

连通图：无向图中任意两顶点间都有路径
强连通图：有向图中任意两顶点间都有路径
连通分量：无向图的极大连通子图
强连通分量：有向图的极大强连通子图

其他重要概念

度数：与顶点相关联的边数
- 无向图：顶点的度数
- 有向图：入度和出度
路径：顶点序列，相邻顶点间有边
回路（环）：起点和终点相同的路径
生成树：包含图中所有顶点的极小连通子图

7.2 图的存储结构

邻接矩阵表示法

数据结构定义

#define MAX_VERTEX_NUM 20
typedef struct {VertexData vertex[MAX_VERTEX_NUM];  // 顶点数组int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵int vexnum, arcnum;  // 顶点数和边数GraphKind kind;      // 图的类型
} AdjMatrix;

特点

优点：

判断两顶点间是否有边：O(1)
适合稠密图

缺点：

空间复杂度：O(n²)，浪费空间
不适合稀疏图

基本操作

// 判断顶点v1和v2是否邻接
int IsAdj(AdjMatrix G, VertexData v1, VertexData v2) {int i, j;i = LocateVertex(&G, v1);j = LocateVertex(&G, v2);return (G.arcs[i][j].adj == 1);
}// 求顶点v的度
int VexDegree(AdjMatrix G, VertexData v) {int k = LocateVertex(&G, v);int degree = 0;for(int j = 0; j < G.vexnum; j++)degree += G.arcs[k][j];return degree;
}

邻接表表示法

数据结构定义

typedef struct ArcNode {int adjvex;           // 邻接点位置struct ArcNode *nextarc;  // 下一条边OtherInfo info;       // 边的其他信息
} ArcNode;typedef struct VertexNode {VertexData data;      // 顶点数据ArcNode *firstarc;    // 第一条边
} VertexNode;typedef struct {VertexNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;GraphKind kind;
} AdjList;

特点

优点：

空间效率高：O(|V|+|E|)
适合稀疏图
便于遍历顶点的邻接点

缺点：

判断两顶点是否邻接需要遍历：O(度数)

创建无向图

int CreateUDG(AdjList *G) {scanf(&G->vexnum, &G->arcnum);for(i=0; i<G->vexnum; i++) {scanf(&G->vertex[i].data);G->vertex[i].firstarc = NULL;}for(k=0; k<G->arcnum; k++) {scanf("%c%c", &v1, &v2);i = LocateVex(G, v1);j = LocateVex(G, v2);// 申请边结点，连接到相应的链条p = (arcnode*)malloc(sizeof(arcnode));p->adjvex = j;p->nextarc = G->vertex[i].firstarc;G->vertex[i].firstarc = p;p = (arcnode*)malloc(sizeof(arcnode));p->adjvex = i;p->nextarc = G->vertex[j].firstarc;G->vertex[j].firstarc = p;}
}

7.3 图的遍历

深度优先搜索（DFS）

基本思想

从图中某一顶点v0出发，访问此顶点，然后依次从v0的未被访问的邻接点出发深度优先搜索，直至图中所有和v0有路径相通的顶点都被访问到。

递归算法实现

void DFS(Graph g, int v0) {visit(v0); visited[v0] = true;for(w = FirstNeighbor(g, v0); w >= 0; w = NextNeighbor(g, v0, w)) {if(!visited[w]) DFS(g, w);}
}void TraverseGraph(Graph g) {for(vi = 0; vi < g.vexnum; vi++)visited[vi] = false;for(vi = 0; vi < g.vexnum; vi++)if(!visited[vi]) DFS(g, vi);
}

非递归算法实现

void DepthFirstSearch(Graph g, int v0) {InitStack(S);Push(S, v0);while(!Empty(S)) {v = Pop(S);if(!visited[v]) {visit(v); visited[v] = true;w = FirstAdjVertex(g, v);while(w != -1) {if(!visited[w]) Push(S, w);w = NextAdjVertex(g, v, w);}}}
}

邻接矩阵的DFS

void DepthFirstSearch(AdjMatrix g, int v0) {visit(v0); visited[v0] = true;for(vj = 0; vj < g.vexnum; vj++)if(g.arcs[v0][vj].adj == 1)DepthFirstSearch(g, vj);
}

广度优先搜索（BFS）

基本思想

从图中某顶点v出发，访问v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的各个未被访问的邻接点。

算法实现

void BreadthFirstSearch(Graph g, int v0) {visit(v0); visited[v0] = true;InitQueue(&Q);EnterQueue(&Q, v0);while(!IsEmpty(Q)) {DeQueue(&Q, &v);w = FirstNeighbor(g, v);while(w >= 0) {if(!visited[w]) {visit(w); visited[w] = true;EnterQueue(&Q, w);}w = NextNeighbor(g, v, w);}}
}

遍历算法应用

时间复杂度：

邻接表：O(|V|+|E|)
邻接矩阵：O(|V|²)

应用：

判断图的连通性
求连通分量个数
判断是否存在环
求两点间路径

7.4 图的应用

最小生成树

最小生成树（MST）：在连通网的所有生成树中，各边权值之和最小的生成树。

Prim算法

基本思想：
设N=(V,E)是连通网，TE为最小生成树中边的集合。

初始化：U={u0}，TE=∅
在所有u∈U，v∈V-U的边中选择代价最小的边(u,v)
将v加入U，将边(u,v)加入TE
重复(2)，直到所有顶点都被加入MST

算法实现：

void MiniSpanTree_Prim(AdjMatrix *gn, int u) {for(i=0; i<gn->vexnum; i++) {closeedge[i].adjvex = u;closeedge[i].lowcost = gn->arcs[u][i].adj;}closeedge[u].lowcost = 0;for(i=1; i<gn->vexnum; i++) {k = minimum(closeedge);printf("%c %c", gn->vertex[closeedge[k].adjvex].data,gn->vertex[k].data);closeedge[k].lowcost = 0;for(j=0; j<gn->vexnum; j++)if(gn->arcs[k][j].adj < closeedge[j].lowcost) {closeedge[j].adjvex = k;closeedge[j].lowcost = gn->arcs[k][j].adj;}}
}

Kruskal算法

基本思想：
假设N=(V,E)是连通网，将N中的边按权值从小到大的顺序排列。

将n个顶点看成n个集合
按权值由小到大的顺序选择边，保证不形成回路
若该边连接两个不同的连通分量，则选择这条边，否则舍弃
重复(2)，直到所有顶点都在一个连通分量内

时间复杂度：

Prim算法：O(n²)
Kruskal算法：O(elog e)

最短路径问题

单源最短路径——Dijkstra算法

基本思想：
将图G=(V,E)中的顶点分成两组：

第一组S：已求出最短路径的终点集合（初始为{v0}）
第二组V-S：尚未求出最短路径的顶点集合

算法步骤：

初始化：将vi到终点v0的最短路径长度初始化为g.arcs[i][j]
在V-S集合中找dist[]最小的顶点
估算：在第2步中已经找到了顶点，那么对集合V-S中的每个顶点，都有可能通过该顶点走捷径

任意一对顶点间最短路径——Floyd算法

基本思想：
辅助数组D[][]、P[][]，记录vi到vj的路径长度和路径。

算法思想：

-1）初始化：将vi到vj的最短路径长度初始化为g.arcs[i][j]
1）在vi、vj间加入顶点v1，比较（vi,…,v1,…,vj）和（vi,…,vj）的路径长度，取其中较短的路径作为vi到vj的且中间顶点号不大于1的最短路径
2）在vi、vj间加入顶点v2，比较（vi,…,v2,…,vj）和（vi,…,vj）的路径长度，取其中较短的路径作为vi到vj的且中间顶点号不大于2的最短路径

有向无环图的应用

拓扑排序（Topological Sort）

定义：
对有向无环图G的所有顶点进行线性排序，使得对于任意一条边(vi,vj)，在排序中vi都出现在vj之前。

基本思想：

从有向图中选择一个没有前驱的顶点输出
将此顶点和以它为起点的弧删除
重复1、2，直到不存在无前驱的顶点
若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点序列即为一个拓扑排序

算法实现：

int TopoSort(AdjList *G) {Stack S;int indegree[MAX], count, k;ArcNode *p;FindID(G, indegree);  // 求各顶点入度InitStack(&S);for(i=0; i<G->vexnum; i++)if(indegree[i] == 0) Push(&S, i);  // 将入度为0的顶点入栈count = 0;while(!StackEmpty(S)) {Pop(&S, &i);printf("%c", G->vertex[i].data);count++;  // 输出顶点并计数p = G->vertex[i].firstarc;while(p != NULL) {k = p->adjvex;indegree[k]--;  // 每个邻接点的入度减1if(indegree[k] == 0) Push(&S, k);  // 若入度减为0，则入栈p = p->nextarc;}}if(count < G->vexnum) return 0;  // 该有向图含有回路else return 1;
}

关键路径

AOE网（Activity On Edge Network）：
用顶点表示事件，用弧表示活动，弧上权值表示活动的持续时间。

重要定义：

源点：入度为0的顶点，即工程开始
汇点：出度为0的顶点，即工程结束
关键路径：从源点到汇点的最长路径
关键活动：关键路径上的活动

关键路径求取算法思想：

首先调用修改后的拓扑排序算法，求出各个事件的最早发生时间ve(i)
将各顶点的最早发生时间ve[]初始化为0
只要栈S不空，则重复下面处理：
- 将栈顶顶点Vj出栈并加入T（生成拓扑排序）
- 将各顶点Vj的每一个邻接点Vk的入度减1，如果顶点Vk的入度减为0，则将Vk入栈
- 根据顶点Vj的最早发生时间ve[j]和弧<j,k>的权值，更新顶点Vk的最早发生时间ve[k]
找出e(i)=l(i)的活动，即为关键活动

算法步骤：