《数据结构8图》由会员分享，可在线阅读，更多相关《数据结构8图（61页珍藏版）》请在金锄头文库上搜索。
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 有向图G2,G
2、2=(V2,E2)V2=v1,v2,v3,v4E2=, G1=( V, E ) 集合Vv1,v2,v3,v4,v5集合E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。,2018/9/15,4,权 某些图的边具有与它相关的数, 称之为权。在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。带权图叫做网。有向网、无向网。,1,2,3,
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,2018/9/15,6,完全图 对有n个顶点的图，若为有向图且边数为n(n-1) ，则称其为有向完全图。若为无向图且边数为n(n-1)/2，则称其为无向完全图；边或弧数 ,称vi邻接到vj， 弧关联于顶点vi和vj.,顶点的度 一个顶点v的度是与它相关联的边的条数。 记作TD(v)。,顶点 v 的入度 是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数,记作 OD(v)。,子图 设有两个图 G(V,
4、 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、通分量。,2018/9/15,10,强连通图与强连通分量 在有向图中, 若对于每一 对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,生成树 一个连通图的生成树是它的极小连通子图，含图中n个顶点，有n-1条边。,含图中n个顶点，有n-1条边的图一定生成树吗？,2018/9/15,12,生成森林 在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。,2018/9/15,13,基本操作P：/结构的建立和销毁: CreateGraph( / 对v赋值va
6、lue。,2018/9/15,14,对邻接点的操作: FirstAdjVex(G, v); / 返回v的第一个邻接点。若该顶点 /在G中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); /返回v的（相对于w的）下一个 邻接点。若w是v的最后一个邻接点，则返回“空”。 插入或删除顶点InsertVex( / 删除G中顶点v及其相关的弧。,2018/9/15,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 vextype; /*顶点的数据类
8、型*/ 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; ,邻接表存储结构 (Adjacency Li
9、st),无向图的邻接表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标 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邻接但还没有访问过的顶点 w2；然后再从 w2 出 发，
12、进行类似的访问， 如此进行下去，直至到达 所有的邻接顶点都被访问过的顶点 u 为止。接着， 退回一步，退到前一次刚访问过的顶点，看是否还 有其它没有被访问的邻接顶点。如果有，则访问此 顶点，之后再从此顶点出发，进行与前述类似的访 问；如果没有，就再退回一步进行搜索。重复上述 过程，直到连通图中所有顶点都被访问过为止。,深度优先搜索DFS ( Depth First Search ),深度优先搜索的示例,深度优先搜索算法 int visitedn; graph g;DFS(int i) /*图用邻接矩阵表示*/ int j;printf(“node:%cn”,g.vexsi);visitedi=
13、TRUE;for (j=0;jadjvex)DFSL(p-adjvex);p=p-next; ,邻接表的形式说明 /*边表结点定义*/ typedef struct node int adjvex;struct node *next; edgenode; /*顶点表结点定义*/ typedef struct vextype vertex;edgenode *link; vexnode;,例子,遍历结果：A、C、B、D,深度优先,广度优先搜索BFS ( Breadth First Search ),广度优先搜索的示例,广度优先搜索过程 广度优先生成树,使用广度优先搜索在访问了起始顶点 v 之后，
14、由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, , wt，然后再顺序访问 w1, w2, , wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。 与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组 visite
15、d ，给被访问过的顶点加标记。,广度优先搜索算法 BSF(int k) /*图用邻接矩阵表示*/ int i,j; /1SETNULL(Q);printf(“%cn”,g.vexsk);visitedk=TRUE;ENQUEUE(Q,K);while (!EMPTY(Q),while (!EMPTY(Q) i=DEQUEUE(Q); /2for (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);,
