抽象数据类型图的定义

1、第七章第七章 图图7.1 抽象数据类型图的定义抽象数据类型图的定义adt graph 数据对象数据对象v：v是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系r：rvrvr| v,wv且p(v,w)，表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息 名词和术语名词和术语有向图、 无向图、 网、 子图 弧头、 弧尾、 边完全图、 稀疏图、 稠密图 邻接点、 度、 入度、 出度路径、 路径长度、 回路简单路径、 简单回路连通图、 连通分量、强连通图、 强连通分量生成树、 生成森林、 最小生成树基本操作基本操作p：结构的建立和销毁:creategraph(&g,v,vr);

2、/ 按v和vr的定义构造图g。destroygraph(&g); / 销毁图g。对顶点的访问操作:locatevex(g, u); / 若g中存在顶点u，则返回该顶点/ 在图中位置位置；否则返回其它信息。getvex(g, v); / 返回v的值。putvex(&g, v, value); / 对v赋值value。对邻接点的操作:firstadjvex(g, v); / 返回v的第一个邻接点。若该顶点/在g中没有邻接点，则返回“空”。nextadjvex(g, v, w); /返回v的（相对于w的）下一个/ 邻接点。若w是v的最后一个邻/ 接点，则返回“空”。插入或删除顶点in

3、sertvex(&g, v); / 在图g中增添新顶点v。deletevex(&g, v); / 删除g中顶点v及其相关的弧。插入和删除弧insertarc(&g, v, w); / 在g中增添弧，若g是无/ 向的，则还增添对称弧。deletearc(&g, v, w); /在g中删除弧，若g是无/ 向的，则还删除对称弧。遍历dfstraverse(g, v, visit(); / 从顶点v起深度优先遍历图/ g，并对每个顶点调用函数/ visit一次且仅一次。bfstraverse(g, v, visit(); / 从顶点v起广度优先遍历图/ g，并对每个顶点

4、调用函数/ visit一次且仅一次。7.2 图的存储表示图的存储表示图的数组(邻接矩阵)存储表示#define infinity int_max / 最大值#define max_vertex_num 20 / 最大顶点个数typedef enum dg, dn, ag, an graphkind;/有向图,有向网,无向图,无向网typedef struct arccell vrtype adj; / vrtype是顶点关系类型。/ 对无权图，用1或0表示相邻否；/ 对带权图，则为权值类型。infotype *info; / 该弧相关信息的指针 arccell, adjmatrixmax_ve

5、rtex_nummax_vertex_num;typedef struct vertextype vexsmax_vertex_num; / 顶点向量adjmatrix arcs; / 邻接矩阵int vexnum, arcnum; / 图的当前顶点数和弧(边)数graphkind kind; / 图的种类标志 mgraph;1.图的邻接表存储表示#define max_vertex_num 20typedef struct arcnode int adjvex; / 该弧所指向的顶点的位置struct arcnode *nextarc; / 指向下一条弧的指针infotype *info;

6、/ 该弧相关信息的指针 arcnode;typedef struct vnode vertextype data; / 顶点信息arcnode *firstarc; / 指向第一条依附该顶点的弧 vnode, adjlistmax_vertex_num;typedef struct adjlist vertices;int vexnum, arcnum; / 图的当前顶点数和弧数int kind; / 图的种类标志 algraph;1.有向图的十字链表存储表示有向图的十字链表存储表示 #define max_vertex_num 20typedef struct arcbox int tail

7、vex, headvex; / 该弧的尾和头顶点的位置struct arcbox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域infotype *info; / 该弧相关信息的指针 arcbox;typedef struct vexnode vertextype data;arcbox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 vexnode;typedef struct vexnode xlistmax_vertex_num; / 表头向量int vexnum, arcnum; / 有向图的当前顶点数和弧数 olgrap

8、h;1.无向图的邻接多重表存储表示无向图的邻接多重表存储表示 #define max_vertex_num 20typedef emnu unvisited, visited visitif;typedef struct ebox visitif mark; / 访问标记int ivex, jvex; / 该边依附的两个顶点的位置struct ebox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边infotype *info; / 该边信息指针 ebox;typedef struct vexbox vertextype data;ebox *firstedge; / 指

9、向第一条依附该顶点的边 vexbox;typedef struct vexbox adjmulistmax_vertex_num;int vexnum, edgenum; / 无向图的当前顶点数和边数 amlgraph; 7.3 图的遍历图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。一、深度优先搜索一、深度优先搜索从图中某个顶点v0 出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有

10、顶点都被访问到为止。/- 下列算法使用的全局变量 -boolean visitedmax; / 访问标志数组status (* visitfunc)(int v); / 函数变量void dfstraverse(graph g, status (*visit)(int v) / 对图g作深度优先遍历。visitfunc = visit; for (v=0; vg.vexnum; +v) visitedv = false; / 访问标志数组初始化for (v=0; vg.vexnum; +v) if (!visitedv) dfs(g, v); / 对尚未访问的顶点调用dfsvoid dfs(g

11、raph g, int v) / 从第v个顶点出发递归地深度优先遍历图g。visitedv = true; visitfunc(v); / 访问第v个顶点for ( w=firstadjvex(g, v); w!=0; w=nextadjvex(g, v, w) )if (!visitedw) dfs(g, w); / 对v的尚未访问的邻接顶点w递归调用dfs二、广度优先搜索二、广度优先搜索从图中的某个顶点v0出发，并在访问此顶点之后依次访问v0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和v0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问

12、,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。void bfstraverse(graph g, status (*visit)(int v) / 按广度优先非递归遍历图g。使用辅助队列q和访问标志数组visited。for (v=0; vg.vexnum; +v) visitedv = false;initqueue(q); / 置空的辅助队列qfor ( v=0; vg.vexnum; +v )if ( !visitedv) / v尚未访问enqueue(q, v); / v入队列while (!queueempty(q) dequeue(q, u

13、); / 队头元素出队并置为uvisitedu = true; visit(u); / 访问ufor ( w=firstadjvex(g, u); w!=0; w=nextadjvex(g, u, w) )if ( ! visitedw) enqueue(q, w); / u的尚未访问的邻接顶点w入队列q7.4 最小生成树最小生成树问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。算法一：（普里姆算法）算法一：（普里姆

14、算法）可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：u（包含已落在生成树上的结点）和v-u（尚未落在生成树上的顶点），则在所有连通u中顶点和v-u中顶点的边中选取权值最小的边。记录从顶点集u到vu的代价最小的边的辅助数组：struct vertextype adjvex;vrtype lowcost; closedgemax_vertex_num;k = locatevex ( g, u ); / 顶点u为构造生成树的起始点for ( j=0;

15、 jg.vexnum; +j ) / 辅助数组初始化if (j!=k) closedgej = u, g.arcskj.adj ; closedgek.lowcost = 0; / 初始，uufor (i=0; ig.vexnum; +i) /在其余顶点中选择k = minimum(closedge); / 求出t的下一个结点(k)printf(closedgek.adjvex, g.vexsk); / 输出生成树的边closedgek.lowcost = 0; / 第k顶点并入u集for (j=0; jg.vexnum; +j)if (g.arcskj.adj closedgej.lowco

16、st)closedgej = g.vexsk, g.arcskj.adj ;/ 新顶点并入u后重新选择最小边算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图sg，然后从权值最小的边开始，若它的添加不使sg中产生回路，则在sg上加上这条边，如此重复，直至加上n-1条边为止。算法算法:构造非连通图 st=( v, );k = i = 0;while (kadjvex;dfsarticul(g, v); / 从第v顶点出发深度优先搜索if (count nextarc) w

17、 = p-adjvex; / w为v0的邻接顶点if (visitedw = 0) / w未曾被访问dfsarticul(g, w); / 返回前求得lowwif (loww =visitedv0) printf(v0, g.verticesv0.data); / 输出关节点elseif (visitedw min) min = visitedw; / w是回边上的顶点lowv0 = min; 7.6 两点之间的最短路径问题两点之间的最短路径问题1.求从某个源点到其余各点的最短路径迪杰斯特拉推出了一个按路径长度递增的次序按路径长度递增的次序求从源点到其余各点最短路径的算法。假设图中所示为从源点

18、到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者 在这条路径上，必定只含一条(权值最小)弧，由此，只要在所有从源点出发的弧中查找权值最小者; 长度次短的路径可能有两种情况: 它可能是从源点直接到该点的路径;也可能是，从源点到a, 再从a到该点其余依次类推。 假设 distk 表示 当前所求得的从源点到k的最 短路径显然，distk = 或者 = + 二、每一对顶点之间的最短路径从vi到vj的最短路径是以下各种可能路径中的长度最小者:若存在，则存在路径vi,vj/ 路径中不含其它顶点若,存在，则存在路径vi,v1,vj/ 路径中所含顶点序号不大于1若vi,v2, v2,vj存在，

19、则存在一条路径vi, , v2, vj/ 路径中所含顶点序号不大于2依次类推，则vi至vj的最短路径应是上述这些路径中，路径长度最小者。7.7 拓扑排序拓扑排序 问题问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。 何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作:按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之;二、从有向图中删去此顶点以及所有

20、以它为尾的弧;重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 - 入度为零删除顶点及以它为尾的弧- 弧头顶点的入度减1 算法算法:取入度为零的顶点v;while (v0) printf(v); +m;w:=firstadj(v);while (w0) indegreew-;w:=nextadj(v,w);取下一个入度为零的顶点v;if mn printf(“图中有回路); 7.8 关键路径关键路径 问题问题:假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间，问:哪些子工程项是“关键工程”？即:将影响整个工程完成期限的子工程项。整个工程完成的时间为:从有向图的源点到汇点的最长路径