数据结构8图.ppt

1、第八章 图,图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径方法,图的基本概念,图定义 图是由顶点集合(vertex)及顶点间的关系边（或者弧)集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷 非空集合； E = 或(v,w)| v, w V 是顶点之间关系的有穷集合，谓词P(v,w)定义了弧的意义或信息,谓词是用来刻划个体词的性质或事物之间关系的词.,有向图与无向图 若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向(x, y)的，则称G为无向图. (x, y)称为边。,无向图G1 有

2、向图G2,G2=(V2,E2) V2=v1,v2,v3,v4 E2=, G1=( V, E ) 集合Vv1,v2,v3,v4,v5 集合E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。,2020/8/6,4,权 某些图的边具有与它相关的数, 称之为权。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。 带权图叫做网。有向网、无向

3、网。,1,2,3,5,6,8,7,4,A,B,D,C,E,10,7,9,6,6,7,12,3,15,16,60,30,45,35,80,40,75,60,80,40,2020/8/6,6,完全图 对有n个顶点的图，若为有向图且边数为n(n-1) ，则称其为有向完全图。若为无向图且边数为n(n-1)/2，则称其为无向完全图；边或弧数 ,称vi邻接到vj， 弧关联于顶点vi和vj.,顶点的度 一个顶点v的度是与它相关联的边的条数。 记作TD(v)。,顶点 v 的入度 是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,子图 设

4、有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,5,路径 在图 G(V, E) 中, 若存在一个顶点序列 vp1, vp2, , vpm，使得(vi, vp1)、(vp1, vp2)、 .、(vpm, vj)均属于E，则称顶点vi到vj存在一 条路径。若一条路径上除了vi 和vj 可以相同外， 其余顶点均不相同，则称此路径为一条简单路径 。起点和终点相同的路径称为回路或环,其余顶点均不相同，称为简单回路,6,图的连通 在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi 和vj 是连通的。若G中任意两个顶点都是连通的，则称G为连通图。

5、非连通图的极大连通子图叫做连通分量。,2020/8/6,10,强连通图与强连通分量 在有向图中, 若对于每一 对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,生成树 一个连通图的生成树是它的极小 连通子图，含图中n个顶点，有n-1条 边。,含图中n个顶点，有n-1条边的图一定生成树吗？,2020/8/6,12,生成森林 在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。,2020/8/6,13,基本操作P： /结构的建立和销毁: CreateG

6、raph( / 对v赋值value。,2020/8/6,14,对邻接点的操作: FirstAdjVex(G, v); / 返回v的第一个邻接点。若该顶点 /在G中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); /返回v的（相对于w的）下一个 邻接点。若w是v的最后一个邻接点，则返回“空”。 插入或删除顶点 InsertVex( / 删除G中顶点v及其相关的弧。,2020/8/6,15,插入和删除弧 InsertArc( / 从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个

7、表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A .Edgenn，定义： 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,1.邻接矩阵 (Adjacency Matrix),16,在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。,网的邻接矩阵,邻接矩阵表示法中图的描述 #define n 6 /*图的顶点数*/ #define e 8 /*图的边数*/ typedef char vex

8、type; /*顶点的数据类型*/ typedef float adjtype; /*权值类型*/ typedef struct vextype vexsn; adjtype arcsnn; graph;,2,1,5,3,4,6,20,30,50,40,70,80,邻接矩阵表示法中无向网的建立算法 CREATEGRAPH(graph *ga) int i,j,k; float w; for (i=0;ivexsigetchar(); /*读入顶点信息，建立顶点表*/ for (i=0;iarcsij0; /*邻接矩阵初始化*/ for (k=0;karcsijw; ga-arcsjiw; ,邻

9、接表存储结构 (Adjacency List),无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标 dest 和指向同一链表中下一个边结点的指针 link。,有向图的邻接表和逆邻接表 在有向图的邻接表中，第 i 个邻接表链接的边都是顶点 i 发出的边。也叫做出边表。 在有向图的逆邻接表中，第 i 个邻接表链接的边都是进入顶点 i 的边。也叫做入边表。,带权图的边结点中保存该边上的权值 cost。 顶点 i 的边链表的表头指针 adj 在顶点表的下标为 i 的顶点记录中，该记录还保存了该顶点的其它信息。

10、在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。,邻接表的形式说明和建立算法 typedef struct node /*边表结点定义*/ int adjvex; struct node *next; edgenode; typedef struct /*顶点表结点定义*/ vextype vertex; edgenode *link; vexnode; vexnode gan;,网络 (带权图) 的邻接

11、表,图的遍历性,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,DFS 在访问图中某一起始顶点 v 后，由 v 出发， 访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但

12、还没有访问过的顶点 w2；然后再从 w2 出 发，进行类似的访问， 如此进行下去，直至到达 所有的邻接顶点都被访问过的顶点 u 为止。接着， 退回一步，退到前一次刚访问过的顶点，看是否还 有其它没有被访问的邻接顶点。如果有，则访问此 顶点，之后再从此顶点出发，进行与前述类似的访 问；如果没有，就再退回一步进行搜索。重复上述 过程，直到连通图中所有顶点都被访问过为止。,深度优先搜索DFS ( Depth First Search ),深度优先搜索的示例,深度优先搜索算法 int visitedn; graph g; DFS(int i) /*图用邻接矩阵表示*/ int j; printf(“n

13、ode:%cn”,g.vexsi); visitedi=TRUE; for (j=0;jn;j+) if (g.arcsij=1) ,vexnode g1n; DFSL(int i) /*图用邻接表表示*/ int j; edgenode *p; printf(“node:%cn”,g1i.vertex); visitedi=TRUE; p=g1i.link; while (p!=NULL) if (!visitedp-adjvex) DFSL(p-adjvex); p=p-next; ,邻接表的形式说明 /*边表结点定义*/ typedef struct node int adjvex; s

14、truct node *next; edgenode; /*顶点表结点定义*/ typedef struct vextype vertex; edgenode *link; vexnode;,例子,遍历结果：A、C、B、D,深度优先,广度优先搜索BFS ( Breadth First Search ),广度优先搜索的示例,广度优先搜索过程 广度优先生成树,使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, , wt，然后再顺序访问 w1, w2, , wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有

15、还未被访问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。 与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组 visited ，给被访问过的顶点加标记。,广度优先搜索算法 BSF(int k) /*图用邻接矩阵表示*/ int i,j; /1 SETNULL(Q); printf(“%cn”,g.vexsk); vis

16、itedk=TRUE; ENQUEUE(Q,K); while (!EMPTY(Q),while (!EMPTY(Q) i=DEQUEUE(Q); /2 for (j=0;jn;j+) if (g.arcsij=1) /3 /2 /1,BFSL(int k) /*图用邻接表表示*/ int i; edgenode *p; SETNULL(Q); printf(“%cn”,g1k.vertex); visitedk=TRUE; ENQUEUE(Q,k);,while (!EMPTY(Q) i=DEQUEUE(Q); p=g1i.link; while (p!=NULL) if (!visited

17、p-adjvex) printf(“%cn”,g1p-adjvex.vertex); visitedp-adjvex=TRUE; ENQUEUE(Q,p-adjvex); p=p-next; ,例子,遍历结果：A、 C 、 B 、D,无向图的连通性,当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。 若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。 算法实现：需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还

18、未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。,对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,非连通图的遍历,非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法，以DFS为例：,TRAVER() /* 遍历用邻接矩阵表示的非连通图*/ int i; for ( i = 0; i n; i+) visitedi = FALSE; /* 标志数组初始化 */ for ( i = 0; i n; i+) if ( !visitedi) DFS(i); /* 从顶点出发遍历一个连 通分量 */ printf( “comp endn”); ,四、最小生成树 ( m

19、inimum cost spanning tree ),按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。 生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。,用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。,2020/8/6,46,对于无向网，生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。 构造最小生成树的准则：必须只使用该网中的边来构造最小生成树；必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；不能使用产生回路的边,权值总和最

20、小。,2020/8/6,47,问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。,最小生成树的重要性质： 设 G =（V，E）是一个连通网，U 是顶点集 V 的一个非空子集。若（u，v）具有最小权值的一条边，u是在U中，v不在U 中，则一定存在 G 的一棵最小生成树包含（u，v）边。,u,v,U,VU,证明（反证法）： 假设 G 中任何一棵最小生成树中都不包含(u，v)。设T是一棵最小生成树但不包含(u，v)。由于T

21、是最小生成树，所以 T 是连通的，因此有一条从u到v的路径，且该路径上必有一条连接两个顶点集 U、V 的边(u，v)，其中uU，vV-U。当把边(u，v)加入到 T 中后，得到一个含有边(u，v)的回路。删除边(u，v)，上述回路即被消除。由此得到另一棵生成树 T， T 和 T 的区别仅在于用边(u，v)代替了(u，v)。由于(u，v)的权=(u，v)的权，所以， T的权=T的权，与假设矛盾。,u,v,U,VU,u,v,普里姆(Prim)算法,普里姆算法的基本思想： 从连通网络 N = V, E 中的某一顶点 u0 出 发，选择与它关联的具有最小权值的边(u0, v)， 将其顶点加入到生成树的

22、顶点集合U中。以后每 一步从一个顶点在U中，而另一个顶点不在U中 的各条边中选择权值最小的边(u, v),把它的顶点 加入到集合U中。如此继续下去，直到网络中的 所有顶点都加入到生成树顶点集合U中为止。,用普里姆算法构造最小生成树的过程,克鲁斯卡尔 (Kruskal) 算法,克鲁斯卡尔算法的基本思想： 设有一个有 n 个顶点的连通网络 N = V, E , 最初先构造一个只有 n 个顶点，没有边的非连通 图 T = V, , 图中每个顶点自成一个连通分量。 当在 E 中选到一条具有最小权值的边时,若该边的 两个顶点落在不同的连通分量上，则将此边加入 到 T 中；否则将此边舍去，重新选择一条权值最 小的边。 如此重复下去，直到所有顶点在同一个连通 分量上为止。,用克鲁斯卡尔算法构造最小生成树的过程,2020/8/6,55,最短路径方法,Djikstra算法 初始时（s为初始顶点），Ds=0，Di=inf（is） 1.在未访问顶点中选择Dv最小的顶点v，访问v，Sv=1. 2.依次考察v的邻接点w，若 Dv+weight() 重复1，2。直至所有的顶点被访问。 （找到出发点到其他各点的最短路径。）,2020/8/6,56,图的拓扑排序,AOV网：在有向图中，用顶点表示活动，