数据结构学习(七)
数据结构——用C语言描述(七)
非线性结构
图
图的定义与基本术语
图的定义
图(Graph)是一种网状数据结构,其形式化定义如下:
Graph=(V,R)
V={x|x∈DataObject}
R={VR}
VR={<x,y>|P(x,y)∧(x,y∈V)}
其中,
- DataObject:具有相同特性的元素的集合
- V:顶点(vertex)集合
- VR:顶点间关系的集合
- P(x,y):表示 x 和 y 之间有特定的关联属性 P
图的抽象类型定义
数据对象 V:具有相同特性的元素的集合
结构关系:多对多
R={VR}
VR={<x,y>|P(x,y) (xy∈V)}
操作集合:
- 创建
GreateGraph(G)
- 销毁
DestoryGraph(G)
- 确定顶点位置
LocateVertex (G, v)
- 取第 i 个顶点
GetVertex(G, i)
- 找顶点 v 的第一个邻接点
FirstAdjVertex(G, v)
- 找顶点 v 的下一个邻接点
NextAdjVertex(G, v, w)
- 插入顶点
InsertVertex(G, u)
- 删除顶点及弧
DeleteVertex(G, v)
- 插入弧
lnsertArc (G, v, w)
- 删除弧
DeleteArc (G, v, w)
- 遍历
TraverseGraph(G)
基本术语
-
图
- 无向图:图中边无方向
- 有向图:图中边有方向
- 有向完全图:图中每个顶点和其余 n-1 个顶点都有弧相连(总共$n×(n-1)$条边)
- 无向完全图:图中每个顶点和其余 n-1 个顶点都有边相连(总共$\frac{n×(n-1)}{2}$条边)
- 子图:若 G' 的顶点包含于 G 的顶点,则称图 G' 为 G 的子图
- 连通图:对于图中任意两个顶点都是连通的
- 连通分量:无向图中的极大连通子图
- 强连通图:任意两个顶点之间互相可达
- 强连通分量:有向图的极大强连通子图
-
邻接点:两顶点之间存在边,则称其互为邻接点
-
路径和回路
- 路径:顶点序列
- 路径长度:顶点序列上经过的边的个数
- 回路或环:起点和终点相同
- 简单路径:顶点序列中的顶点各不相同的路径
- 简单回路:除了第一个和最后一个顶点外,其余各顶点均不重复出现的回路
-
度
-
无向图的度:顶点 V 的度 TD(V)——和 V 相连的边的个数
-
有向图的度:入度+出度
入度 ID(V):进来的弧
出度 OD(V):出去的弧
-
度的计算公式:n 个顶点,e 条边或弧,则有 $$ 2e=\sum_{i=1}TD(V_i) $$
-
-
权和网
- 权:图的边或弧上与它相关的数(可以表示从一个顶点到另一个顶点的距离或耗费等信息)
- 赋权图(网):带权的图
-
生成树:极小连通子图,含有连通图全部顶点 n 并有 n-1 条边
-
顶点在图中的位置:人为排列中的位置序号,可将任一顶点看作图的第一个顶点,对任一顶点其邻接点间不存在顺序关系
图的存储结构
显然,我们需要存储顶点和顶点间关系两部分信息,对此我们有如下四种办法
邻接矩阵表示法(数组表示法)
定义
用两个数组来表示图:存储顶点信息的一维数组、存储顶点关联关系的二维数组(邻接矩阵)
表示
G 是一具有 n 个顶点的无权图,G 的邻接矩阵是如下性质的 n×n 矩阵 A: $$ A[i,j]= \begin{cases} 1 &若<v_i,v_j>或(v_i,v_j)∈VR\\ 0 &反之 \end{cases} $$ 若图 G 是一个有 n 个顶点的网,则它的邻接矩阵是具有如下性质的 n×n 矩阵 A: $$ A[i,j]= \begin{cases} W_{ij} &若<v_i,v_j>或(v_i,v_j)∈VR\\ 0或∞ &反之 \end{cases} $$ 例如:
$$
A=\left(
\begin{array}{cccc}
0 & 1 & 1 & 1\\
1 & 0 & 0 & 0\\
1 & 0 & 0 & 1\\
1 & 0 & 1 & 0\\
\end{array}
\right)
$$
C语言类型描述
|
|
特点
- 存储空间:
-
无向图
邻接矩阵是对称矩阵,可采用下三角压缩存储只需$\frac{n×(n-1)}{2}$空间
-
有向图
邻接矩阵不一定是对称矩阵,所以需要$n^2$个存储空间。
- 便于运算:
-
根据$A[i,j]=0或1$来判定图中任意两个顶点之间是否有边相连
-
便于求各个顶点的度
-
无向图:其邻接矩阵第 i 行元素之和就是图中第i 个顶点的度 $$ TD(v_i)=\sum_{j=1}^nA[i,j] $$
-
有向图:第 i 行元素之和就是图中第 i 个顶点的出度;第 i 列元素之和就是图中第 i 个顶点的入度。
$$ OD(v_i)=\sum_{j=1}^nA[i,j]\\ ID(v_i)=\sum_{j=1}^nA[j,i] $$
-
- 便于实现一些基本操作
创建有向网的算法
|
|
邻接表表示法
基本思想
采用链式结构存储图,只存储图中有关联的边的信息:
- 对图中 n 个顶点均建有关联的边链表
- 每个顶点信息与其边链表的头指针构成表头结点表
结构构成
-
表头结点表:
由所有表头结点以顺序结构的形式存储,以便可以随机访问任一顶点的邻接点单链表。 $$ \begin{array}{|c|c|} \hline vexdata(数据域) & firstarc(链域)\\\hline \end{array} $$
-
边表:
由表示图中顶点间邻接关系的 n 个边链表组成。 $$ \begin{array}{|c|c|c|} \hline adjvex(邻接点域) & info(数据域) & nextarc(链域)\\\hline \end{array} $$
图例
结构类型定义
|
|
存储空间
n 个顶点,e 条边的无向图:
采取邻接表作为存储结构,需要 n 个表头结点和 2e 个表结点。
无向图的度
在无向图的邻接表中,顶点$V_i$的度恰好就是第 i 个边链表上结点的个数
有向图的度
有向图中,第 i 个边链表上顶点的个数是顶点$V_i$的出度。
求该顶点的入度,须遍历整个邻接表。在所有单链表中,查找邻接点域的值为 i 的结点并计数求和。
逆邻接表法:
对每一顶点$V_i$再建立一个所有以顶点$V_i$为弧头的弧的表(逆邻接表)。求顶点$V_i$的入度即是计算逆邻接表中第 i 个顶点的边链表中节点个数
正向邻接表求出度,逆向邻接表求入度。
十字链表
定义
十字链表是有向图的另一种链式存储结构。它是有向图的邻接表和逆邻接表结合的一种链表。
有向图中的每一条弧对应十字链表中的一个弧结点,有向图中的每个顶点对应有一个结点,叫做顶点结点。
结构
用于存储顶点的首元结点结构: $$ \begin{array}{|c|c|c|} \hline data & firstin & firstout\\\hline \end{array} $$
data
数据域firstin
以当前顶点为弧头的其他顶点构成的链表fitstout
以当前顶点为弧尾的其他顶点构成的链表
普通结点的结构: $$ \begin{array}{|c|c|c|c|c|} \hline tailvex & headvex & hlink & tlink & info\\\hline \end{array} $$
tailvex
弧尾顶点的位置下标headvex
弧头顶点的位置下标hlink
下一个以首元节点为弧头的顶点tlink
下一个以首元节点为弧尾的顶点info
数据域
结构类型定义
|
|
图例
建立算法
|
|
优点
在十字链表中能容易地找到以$V_i$为尾的弧,也能容易地找到以$V_i$为头的弧,有向图若采用十字链表作为存储结构,容易求出顶点$V_i$的度。
邻接多重表
定义
邻接多重表是无向图的另外一种存储结构,它将图中关于一条边的信息用一个结点来表示,能够提供更为方便的边处理信息。
结构
顶点结构: $$ \begin{array}{|c|c|} \hline data & firstedge\\\hline \end{array} $$ 边结点结构: $$ \begin{array}{|c|c|c|c|c|c|} \hline mark & ivex & ilink & jvex & jlink & info\\\hline \end{array} $$
结构类型定义
|
|
图例
图的遍历
定义
从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次。
显然我们需要设置访问标志数组visited[]
:
- 保证图中的各顶点均被访问
- 避免重复访问
方法
|
|
此处的search(g, vi)
函数分为深度优先搜索(DFS)和广度优先搜索(BFS)两种。
DFS
深度优先搜索 DFS(Depth_First Search)是指按照深度方向搜索,类似于树的先根遍历:
- 从图中某个顶点$v_0$出发,首先访问$v_0$
- 找出刚访问过的顶点$v_i$的第一个未被访问的邻接点,然后访问该顶点。重复此步骤,直到当前的顶点没有未被访问的邻接点为止
- 返回前一个访问过的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点。转2
与树的先根遍历一样,DFS 算法是递归技术实现:
|
|
邻接矩阵实现DFS
|
|
邻接表实现DFS
|
|
深度优先生成树
显然,DFS 算法将生成一个覆盖 n 个点,有 n-1 条边的访问序列,也就是树,我们可以进一步修改 DFS 算法使其输出深度优先生成树:
|
|
BFS
广度优先搜索 BFS(Breadth_First Search)是指按照广度方向搜索,类似于树的层次遍历:
- 从图中某个顶点$v_0$出发,首先访问$v_0$
- 依次访问$v_0$的各个未被访问的邻接点
- 分别从这些邻接点(端结点)出发,依次访问它们的各个未被访问的邻接点(新的端结点)
与树的层次遍历一样,BFS 算法是队列技术实现:
|
|
广度优先生成树
类似于深度优先生成树,我们也可以进一步修改 BFS 算法使其输出广度优先生成树:
|
|
图的应用
图的连通性问题
无向图的连通分量
调用搜索过程的次数就是该图连通分量的个数。
- 连通图仅调用一次搜索过程——连通分量为 1
- 非连通图需多次调用搜索过程——连通分量为此处次数
修改图的遍历算法即可实现统计无向图的连通分量:
|
|
两顶点之间的简单路径
生成树
最小生成树
各边的代价之和最小的生成树称为最小(代价)生成树。
性质:设$N=(V,{E})$是一连通网,U 是顶点集 V 的一个非空子集。若$(u,v)$是一条具有最小权值的边,存在一棵包含边$(u,v)$的最小生成树。
由此性质,我们有两种算法实现:
-
普里姆算法(加点法)
思想:加点不构成回路
-
假设 N=(V,{E}) 是连通网,TE 为最小生成树中边的集合
-
初始 U={$u_0$}($u_0$∈V),TE=∅
-
在所有$u∈U, v∈V-U$的边中选一条代价最小的边$(u_0, v_0)$并入集合 TE,同时将$v_0$并入 U
-
重复第 2 步,n-1 直到 U=V 为止。
此时,TE 中必含有 n-1 条边,则 T=(V,{TE}) 为N的最小生成树
注意普里姆算法时间复杂度为$O(n^2)$ -
-
克鲁斯卡尔算法(加边法)
思想:加边不构成回路
-
假设 N=(V,{E}) 是连通网,将 N 中的边按权值从小到大的顺序排列
-
将 n 个顶点看成 n 个集合
-
按权值由小到大的顺序选择边,选边应满足两个顶点不在同一个集合内,将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并
-
重复第 3 步,直到所有的顶点都在同一个顶点集合内
-
有向无环图的应用1—拓扑排序
AOV-网
顶点表示活动的网:
- 顶点表示活动
- 弧表示活动间的优先关系
拓扑序列
有向图 G=(v,{E}) 中顶点的线性序列
图中任意两个顶点$v_i$、$v_j$,有一条从$v_i$到$v_j$的路径,则在拓扑序列中$v_i$必排在$v_j$之前。
拓扑网的特性
- 先行关系具有可传递性
- 拓扑序列不唯一
拓扑排序的基本思想
- 选一个无前驱顶点输出
- 删除此点及以它为起点的弧
- 重复1、2,直到不存在无前驱顶点
- 输出顶点数小于图中顶点数,则有向图中存在回路,否则输出顶点顺序即为拓扑序列
拓扑排序算法
-
基于邻接矩阵:
A 为有向图 G 的邻接矩阵,则有
- 找 G 中无前驱的顶点——在 A 中找到值全为 0 的列
- 删除以 i 为起点的所有弧——将矩阵中i对应的行置为全 0
即选全 0 列,置全 0 行。
-
基于邻接表:
附设一个存放各顶点入度的数组
indegree[]
- 找 G 中无前驱的顶点——查找
indegree[i]
为零的顶点$v_i$ - 删除以 i 为起点的所有弧——对链在顶点 i 后面的所有邻接顶点 k,将对应的
indegree[k]
减 1
为避免重复检测入度为零的顶点,设置一个入度为 0 点的栈,若某一顶点的入度减为0,则将它入栈。每当输出某一顶点,便将它从栈中删除。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
bool TopoSort(AdjList G) { int i, k, count, indegree[MAX_VERTEX_NUM]; Stack S; ArcNode *p; FindID(G, indegree); //求各顶点入度 InitStack(&S); for (i = 0; i < G.vexnum; i++) if (!indegree[i]) push(&S, i); //将入度0的顶点入栈 count = 0; while (!IsEmpty(S)) { pop(&S, &i); printf("%c", G.vertex[i].data); count++; p = G.vertex[i].firstarc; while (p) { k = p->adjvex; indegree[k]--; if (!indegree[k]) push(&S, k); p = p->nextarc; } } if (count < G.vexnum) //有回路 return false; else return true; }
- 找 G 中无前驱的顶点——查找
有向无环图的应用2—关键路径
AOE-网
边表示活动的网:
- 顶点表示事件
- 弧表示活动
- 弧的权值表示活动所需时间
在AOE-网中的基本概念
- 源点:唯一入度为零的顶点
- 汇点:唯一出度为零的顶点
- 关键路径:从源点到汇点的最长路径
- 关键活动:关键路径上的活动
几个重要的定义
-
$ve(i)$:事件$v_i$的最早发生时间——从源点到顶点$v_i$的最长路径长度
-
$vl(i)$:事件$v_i$的最晚发生时间(在保证汇点按其最早发生时间发生的前提下)
在求出$ve(i)$的基础上,可从汇点开始,按逆拓扑顺序向源点递推:
$vl(n-1)=ve(n-1)$;
$vl(i)=min${$vl(k)-dut(<i,k>)$}
-
$e(i)$:活动$a_i$的最早开始时间
活动$a_i$对应的弧为$<j,k>$,$e(i)$等于从源点到顶点 j 的最长路径的长度,即$e(i)=ve(j)$
-
$l(i)$:活动$a_i$的最晚开始时间
活动$a_i$对应的弧为$<j, k>$,其持续时间为$dut(<j, k>)$则$l(i)=vl(k)-dut(<j, k>)$
-
$a_i$的松弛时间(时间余量):$a_i$的最晚开始时间与$a_i$的最早开始时间之差——$l(i)-e(i)$
松弛时间(时间余量)为 0 的活动为关键活动
求关键路径的基本步骤
- 在对图中顶点进行拓扑排序过程中按拓扑序列求出每个事件的最早发生时间$ve(i)$
- 按逆拓扑序列求每个事件的最晚发生时间$vl(i)$
- 求出每个活动$a_i$的最早开始时间$e(i)$和最晚发生时间$l(i)$
- 找出$e(i)=l(i)$的活动$a_i$,即为关键活动
修改后的拓扑排序算法
通过拓扑顺序求出事件的最早发生时间
|
|
求关键路径的实现算法
|
|
最短路径
求某一顶点到其它各顶点的最短路径
迪杰斯特拉(Dijkstra)算法
-
基本思想:
下一条最短路径是弧$(v_0,v_x)$或是中间经过 S 的某些顶点到达$v_x$的路径——按路径长度递增顺序产生最短路径
-
算法步骤:
-
g 为邻接矩阵表示的带权图,将$v_0$到其余顶点的路径长度初始化为权值
-
选择$v_k$,使得$v_k$为目前求得的下一条从$v_0$出发最短路径的终点
-
修改从$v_0$出发到集合 V-S 上任一顶点$v_i$的最短路径的长度
如果$dist [k]+g.arcs[k][i]<dist[i]$则修改$dist[i]=dist[k]+g.arcs[k][i]$
-
重复2、3 n-1 次,即按最短路径长度的递增顺序,逐个求出$v_0$到图中其它每个顶点的最短路径
-
-
算法描述:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
ShortestPath_DJS(AdjMatrix g, int vo, VRType dist[MAX_VERTEX_NUM], VertexType path[MAX_VERTEX_NUM]) //存放i的当前最短路径长度,存放i的当前最短路径 { VertexType s; //已找到最短路径的终点集合 int i, k, t, min; for (i = 0; i < g.vexnum; i++) //初始化dist[i]、path[i] { InitList(&path[i]); dist[i] = g.arcs[v0][i]; if (dist[i] < MAX) { AddTail(&path[i], g.vexs[v0]); AddTail(&path[i], g.vexs[i]); InitList(&s); AddTail(&s, g.vexs[v0]); } } for (t = 1; t < g.vexnum - 1; t++) { min = MAX; for (i = 0; i < g.vexnum; i++) if (!Member(g.vexs[i], s) && dist[i] < min) { k = i; min = dist[i]; } if (min = INFINITY) return; AddTail(&s, g.vexs[k]); //选择最小距离vk for (i = 0; i < g.vexnum; i++) if (!Member(g.vexs[i], s) && (dist[k] + g.arcs[k][i] < dist[i])) //基于vk修正距离和路径 { dist[i] = dist[k] + g.arcs[k][i]; path[i] = path[k]; AddTail(&path[i], g.vexs[i]); // path[i]=path[k]∪{vi} } } }
注意此算法时间复杂度为$O(n^2)$
求任意一对顶点间的最短路径
佛罗依德算法(Floyd)
-
基本思想
生成中间顶点序号不大于 0 … 不大于 n一1 的路径矩阵
图 g 用邻接矩阵法表示,求图 g 中任意一对顶点$v_i$、$v_j$间的最短路径
将$v_i$到$v_j$的最短的路径长度初始化为$g.arcs[i][j]$,然后进行如下 n 次比较和修正
-
在$v_i$、$v_j$间加入顶点$v_0$,比较$(v_i,v_0,v_j)$和$(v_i,v_j)$路径的长度,取其中较短路径作为$v_i$到$v_j$的且中间顶点号不大于 0 的最短路径
-
在$v_i$,$v_j$间加入顶点$v_1$,得$(v_i,…,v_1)$和$(v_1,…,v_j)$,其中$(v_i,…,v_1)$是$v_i$到$v_1$的且中间顶点号不大于 0 的最短路径,$(v_1,…,v_j)$是$v_1$到$v_j$且中间顶点号不大于 0 的最短路径,这两条路径在上一步中已求出。将$(v_i,…,v_1,v_j)$与$v_i$到$v_j$中间顶点号不大于 0 的最短路径比较,取较短的路径作为$v_i$到$v_j$的且中间顶点号不大于 1 的最短路径
-
依次类推,经过 n 次比较和修正,在第 n-1 步,将求得$v_i$到$v_j$且中间顶点号不大于 n-1 的最短路径,这必是从$v_i$到$v_j$的最短路径
-
-
算法描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
ShortestPath_Floyd(AdjMatrix g, VRType dist[MAX][MAX], VertexType path[MAX][MAX]) { int i, j, k; for (i = 0; i < g.vexnum; i++) for (j = 0; j < g.vexnum; j++) { InitList(&path[i][j]); dist[i][j] = g.arcs[i][j]; //初始化dist[i][j]和path[i][j] if (dist[i][j] < MAX) { AddTail(&path[i][j], g.vexs[i]); AddTail(&path[i][j], g.vexs[j]); } } for (k = 0; k < g.vexnum; k++) for (i = 0; i < g.vexnum; i++) for (j = 0; j < g.vexnum; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = JoinList(path[i][k], path[k][j]); } }
例题
求距离顶点$v_0$的最短路径长度为k的所有顶点
已知无向图 g,设计算法求距离顶点$v_0$的最短路径长度为 k 的所有顶点,要求尽可能节省时间。
显然,本题应使用广度优先搜索算法(BFS),从顶点$v_0$开始,将一步可达的、两步可达的 … 直至 k 步可达的所有顶点记录下来,同时用一个队列记录每个结点的层号,输出第 k+1 层的所有结点即为所求。
|
|