七章图ppt课件.ppt
《七章图ppt课件.ppt》由会员分享,可在线阅读,更多相关《七章图ppt课件.ppt(92页珍藏版)》请在三一文库上搜索。
1、第七章 图,图的基本概念,图 由顶点(Vertex)集合及顶点间的关系(即边,Edge)集合组成的一种数据结构:Graph( V, E ) V = x | x 某个数据对象 顶点的有穷非空集合; E1 = (x, y) | x, y V E1是顶点之间关系的有穷集合,也叫做边(Edge)集合,此时的图称为无向图。 或E2 = | x, y V & Path (x, y) E2 表示从 x 到 y 的一条弧(Arc),且称x为弧尾,y为弧头,这样的图称为有向图。,有向图与无向图 在有向图中,顶点对 是有序的。 在无向图中,顶点对(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-
2、1)/2 条边, 则此图为无向完全图。 若有 n 个顶点的有向图有n(n-1) 条边, 则此图为有向完全图,邻接顶点 如果 (u, v) 是 E(G) 中的一条边,则称 u 与 v 互为邻接顶点。 子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络(Network)。 顶点的度(Degree) 一个顶点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点(弧头)的有向边的条数, 记作 ID(v
3、); 顶点 v 的出度是以 v 为始点(弧尾)的有向边的条数, 记作 OD(v)。,顶点的度(TD)=出度(OD)+入度(ID) TD(B) =OD(B)+ID(B) =1+2 =3,路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm,到达顶点vj。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点vi 到顶点 vj 的路径。 它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。,简单路
4、径 若路径上各顶点 v1,v2,.,vm 均不 互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 简单回路 若回路上各顶点 v1,v2,.,vm 均不 互相重复, 则称这样的回路为简单回路。,连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的
5、极大强连通子图叫做强连通分量。,有向图 强连通图,无向图 连通图,生成树 假设一个连通图的n个顶点和n-1条边构成一个极小连通子图,称该极小连通子图为此连通图的生成树。 在极小连通子图中增加一条边,则一定有环。 在极小连通子图中去掉一条边,则成为非连通图 注意:有n个顶点,n-1条边的图不一定是生成树,生成森林 对非连通图,称由各个连通分量的生成树的集合为此非连通图的生成森林,图的存储结构,1、邻接矩阵(数组)表示法 有一个记录各个顶点信息的顶点表, 还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.Edgenn,定
6、义:,无向图的邻接矩阵是对称的;,在有向图中 统计第 i 行 1 的个数可得顶点 i 的出度, 统计第 j 列 1 的个数可得顶点 j 的入度。 在无向图中, 统计第 i 行 (或列) 1 的个数可得顶点i 的度。,网络的邻接矩阵,用邻接矩阵表示的结构定义 const int NumVertices = 10; /顶点个数 typedef char VertexData; /顶点数据类型 typedef int EdgeData; /边上权值类型 typedef struct VertexData vexListNumVertices; /顶点表 EdgeData EdgeNumVertice
7、sNumVertices; /邻接矩阵, 可视为边之间的关系 int n, e; /图中当前的顶点个数与边数 MTGraph;,2、邻接表 表示法 邻接表:是图的一种链式存储结构。 顶点的结点结构 data; / 顶点信息 firstarc; /指针,指向第一条依附该顶点的弧 弧的结点结构 adjvex; / 该弧所指向的顶点的位置 nextarc;/指针,指向下一条弧 info; / 该弧相关信息,如:权,无向图的邻接表 同一个顶点发出的边链接在同一个边链表中,每一个链结点代表一条边(边结点), 结点中有另一顶点的下标 dest 和指针 link。,有向图的邻接表和逆邻接表,网络 (带权图)
8、 的邻接表,带权图的边结点中保存该边上的权值 cost。 顶点 i 的边链表的表头指针 adj 在顶点表的下标为 i 的顶点记录中,该记录还保存了该顶点的其它信息。 在邻接表的边链表中,各个边结点的链入顺序任意,视边结点输入次序而定。 设图中有 n 个顶点,e 条边,则用邻接表表示无向图时,需要 n 个顶点结点,2e 个边结点;用邻接表表示有向图时,若不考虑逆邻接表,只需 n 个顶点结点,e 个边结点。,邻接表表示的图的定义 typedef char VertexData; /顶点数据类型 typedef int EdgeData; /边上权值类型 typedef struct node /边
9、结点 int dest; /目标顶点下标 EdgeData cost; /边上的权值 struct node * next; /下一边链接指针 EdgeNode;,typedef struct /顶点结点 VertexData data; /顶点数据域 EdgeNode * firstAdj; /边链表头指针 VertexNode; typedef struct /图的邻接表 VertexNode VexList NumVertices; /邻接表 int n, e; /图中当前的顶点个数与边数 AdjGraph;,邻接表的构造算法(无向图) void CreateGraph (AdjGrap
10、h G) cin G.n G.e; /输入顶点个数和边数 for ( int i = 0; i G.VexListi.data; /输入顶点信息 G.VexListi.firstAdj = NULL; for ( i = 0; i tail head weight; EdgeNode * p = new EdgeNode; p-dest = head; p-cost = weight;,/链入第 tail 号链表的前端 p-link = G.VexListtail.firstAdj; G.VexListtail.firstAdj = p; p = new EdgeNode; p-dest =
11、tail; p-cost = weight; /链入第 head 号链表的前端 p-link = G.VexListhead.firstAdj; G.VexListhead.firstAdj = p; ,图的遍历,从图中某一顶点出发访遍图中所有的顶点,且使每个顶点仅被访问一次,这一过程就叫做图的遍历 (Traversing Graph)。 图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问,可设置一个标记顶点是否被访问过的辅助数组 visited 0n-1。,辅助数组 visited 的初始状态为 0, 在图的
12、遍历过程中, 一旦某一个顶点 i 被访问, 就立即让 visited i 为 1, 防止它被多次访问。 两种图的遍历方法: 深度优先搜索DFS (Depth First Search) 广度优先搜索BFS (Breadth First Search) 遍历结果与具体存储相关,深度优先搜索DFS 深度优先搜索过程,访问图中某一起始顶点 v 后, 由 v 出发, 访问它的任一邻接顶点 w1; 再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2; 然后再从 w2 出发, 进行类似的访问, 如此进行下去, 直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着, 退回一步, 退到前一次刚
13、访问过的顶点, 看是否还有其它没有被访问的邻接顶点。 如果有, 则访问此顶点, 之后再从此顶点出发, 进行与前述类似的访问; 如果没有, 就再退回一步进行搜索。 重复上述过程, 直到连通图中所有顶点都被访问过为止。,图的深度优先搜索算法 void Graph_Traverse (AdjGraph G) int * visited = new int G.n; for ( int i = 0; i G.n; i+ ) visited i = 0; /访问数组 visited 初始化 for ( int i = 0; i G.n; i+ ) /可有多个连通分量 if ( ! visitedi )
14、DFS (G, i, visited ); /从顶点 i 出发开始搜索 delete visited; /释放 visited ,void DFS (AdjGraph G, int v, int visited ) cout GetValue (G, v) ; /访问顶点 v visitedv = 1; /顶点 v 作访问标记 int w = GetFirstNeighbor (G, v); /取 v 的第一个邻接顶点 w while ( w != -1 ) /若邻接顶点 w 存在 if ( !visitedw ) DFS (G, w, visited ); /若顶点 w 未访问过, 从w开始
15、搜,递归 w = GetNextNeighbor (G, v, w ); /取顶点 v 排在 w 后的下一个邻接顶点 ,广度优先搜索BFS 广度优先搜索过程,访问了起始顶点 v 之后, 由 v 出发, 依次访问 v 的各个未被访问过的邻接顶点 w1, w2, , wt, 然后再顺序访问 w1, w2, , wt 的所有还未被访问过的邻接顶点。 再从这些访问过的顶点出发,再访问它们的所有还未被访问过的邻接顶点, 如此做下去,直到图中所有顶点都被访问到为止。 广度优先搜索类似于树的层序遍历,广度优先搜索是一种分层的搜索过程, 每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此
16、, 广度优先搜索不是一个递归的过程。 为了实现逐层访问, 算法中使用了一个队列,以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。 为避免重复访问, 需要一个辅助数组 visitedn,给被访问过的顶点加标记。,图的广度优先搜索算法 void Graph_Traverse (AdjGraph G) int * visited = new int G.n; for ( int i = 0; i G.n; i+ ) visited i = 0; /访问数组 visited 初始化 for ( int i = 0; i G.n; i+ ) if ( ! visitedi ) BFS (G,
17、i, visited ); /从顶点 i 出发开始搜索 delete visited; /释放 visited ,void BFS (AdjGraph G, int v, int visited ) cout q; InitQueue( ,w = GetNextNeighbor (G, v, w); /重复检测 v 的所有邻接顶点 /外层循环,判队列空否 / BFS,图的连通性问题,连通分量 当无向图为非连通图时, 从图中某一顶点出发, 利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点, 只能访问到该顶点所在的最大连通子图(即:连通分量)的所有顶点。 若从无向图的每一个连通分量
18、中的一个顶点出发进行遍历, 可求得无向图的所有连通分量。,求连通分量的算法需要对图的每一个顶点进行检测: 若已被访问过,则该顶点一定是落在图中已求得的连通分量上; 若还未被访问,则从该顶点出发遍历图,可求得图的另一个连通分量。 对于非连通的无向图,所有连通分量的生成树组成了非连通图的生成森林。,生成树 用不同的遍历图的方法,可以得到不同的生成树; 从不同的顶点出发,也可能得到不同的生成树。 n 个顶点的连通网络的生成树有 n 个顶点和n-1 条边。 最小生成树 使用且仅使用该网络中的n-1 条边来联结网络中的 n 个顶点; 各边上的权值的总和达到最小。,普里姆Prim算法 用于构造最小生成树
19、基本思想: 从连通网络 N = V, E 中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。 以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。 采用邻接矩阵作为图的存储表示。,在构造过程中,还设置了两个辅助数组: lowcosti 存放生成树顶点集合内顶点到生成树外顶点i的各边的当前最小权值; nearvexi 记录生成树顶点集合内哪个顶点距离集合外顶点i最近。 例子,若选择从顶
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 七章图 ppt 课件
链接地址:https://www.31doc.com/p-2577506.html