最新图的定义和术语及存储结构ppt课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《最新图的定义和术语及存储结构ppt课件.ppt》由会员分享,可在线阅读,更多相关《最新图的定义和术语及存储结构ppt课件.ppt(36页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图的定义和术语及存储结构图的定义和术语及存储结构27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章章 图图9路径路径: :设图设图G=(V,VR)G=(V,VR)中的一个顶点序列中的一个顶点序列: :v=vv=vi,0 i,0 ,v,vi,1 i,1 , , v, , vi,mi,m=w =w 中,中,(v(vi,j-1 i,j-1 ,v,vi,ji,j) )(或(或 v vi,j-1i,j-1,v,vi,ji,j) VRVR 1jm,1jm,则称从顶点则称从顶点v
2、v 到顶到顶点点w w 之间存在一条路径。之间存在一条路径。路径长度:路径长度:路径上边路径上边(或弧)(或弧)的数目。的数目。ABECF如如: :从从A A到到F F长度为长度为 3 3 的路径的路径A,B,C,FA,B,C,F或或AA,E E,C C,FF简单路径简单路径: :指序列中顶点不重复出现的路径。指序列中顶点不重复出现的路径。简单回路简单回路: :指序列中第一个顶点和最后一个顶点相同,指序列中第一个顶点和最后一个顶点相同,其余顶点不重复出现的回路。其余顶点不重复出现的回路。10连通图:连通图:无向无向图图G G中任意中任意两个顶点之间都有路径相两个顶点之间都有路径相连通。连通。连
3、通分量:连通分量:非连通图中非连通图中的极大连通子图。的极大连通子图。BACDFEBACDFE强连通图:强连通图:在有向图中在有向图中, , 每一对顶点每一对顶点v vi i和和v vj j, , 都存都存在一条从在一条从v vi i到到v vj j和从和从v vj j到到v vi i的路径的路径强连通分量:强连通分量:非强连通非强连通图中的极大强连通子图。图中的极大强连通子图。ABECFABECF11生成树:生成树:v1v2v3v4生成森林:生成森林: 假设一个连通图有假设一个连通图有 n n 个顶点和个顶点和 e e 条边,其中条边,其中 n-1 n-1 条边和条边和 n n 个个顶点构成
4、一个极小连通子图,称顶点构成一个极小连通子图,称该极小连通子图为此连通图的生该极小连通子图为此连通图的生成树。成树。由若干棵由若干棵生成树生成树组成,含全部顶点,但构成组成,含全部顶点,但构成这些树的边是最少的。(对有向或无向图均这些树的边是最少的。(对有向或无向图均适用)适用)12CreatGraph(&G, V, VR)/按定义按定义(V,VR)(V,VR)构造图构造图DestroyGraph(&G) / / 销毁图销毁图结构的建立和销毁结构的建立和销毁对顶点的访问操作对顶点的访问操作LocateVex(G, u) / / 若若G G中存在顶点中存在顶点u u,则返回该顶点,则返回该顶点在
5、图中在图中“位置位置”,否则返回其它信息。,否则返回其它信息。GetVex(G, v) / / 返回返回 v v 的值。的值。PutVex(&G, v, value) / / 对对 v v 赋值赋值valuevalue。结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作遍历遍历插入或删除弧插入或删除弧基本操作基本操作对顶点的访问操作对顶点的访问操作13对邻接点的操作对邻接点的操作FirstAdjVex(G, v); /返回返回v v的的“第一个邻接点第一个邻接点” ” 若该若该顶点在顶点在G G中没有邻接点,则返回中没有邻接点,则返回“空空”。NextAd
6、jVex(G, v, w); /返回返回v v的(相对于的(相对于w w的)的) “ “下下一个邻接点一个邻接点”。若。若w w是是v v的最后一个邻接点,则返回的最后一个邻接点,则返回“空空”。插入或删除顶点插入或删除顶点InsertVex(&G, v); /在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G, v);/删除删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。14插入和删除弧插入和删除弧InsertArc(&G, v, w); / / 在在G G中增添弧中增添弧,若,若G G是是无向的,则还增添对称弧无向的,则还增添对称弧。DeleteArc(&G,
7、v, w); /在在G G中删除弧中删除弧,若,若G G是是无向的,则还删除对称弧无向的,则还删除对称弧。DFSTraverse(G, v, Visit(); /从顶点从顶点v v起深度优先遍历起深度优先遍历图图G G,并对每个顶点调用函数,并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点从顶点v起广度优先遍历图起广度优先遍历图G,并对每个顶点调用函数,并对每个顶点调用函数Visit一次且仅一次。一次且仅一次。遍遍 历历157.2 7.2 图的存储结构图的存储结构图的特点:图的特点:链式存储结构:链式存储结构:顺
8、序存储结构:顺序存储结构: 难!难! (多个顶点,无序可言,无法仅以(多个顶点,无序可言,无法仅以顶点坐标表达相互关系)顶点坐标表达相互关系)可用可用多重链表多重链表但可但可用用数组数组描述元素间关系。描述元素间关系。非线性结构非线性结构(m :nm :n)邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原各种表示法成立的原则:存入电脑后能唯则:存入电脑后能唯一复原一复原16 建立一个建立一个顶点表顶点表和一个和一个邻接矩阵邻接矩阵。 , ),( , ,.否否则则或或者者如如果果01AEjiEjijiarcs记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表
9、示各个顶点之间关系 设图设图 A = (A = (V V, , E E ) ) 有有 n n 个顶点,则图的邻接个顶点,则图的邻接矩阵是一个二维数组矩阵是一个二维数组 A A.arcs.arcs n nn n ,定义为:,定义为:17邻接矩阵:邻接矩阵:A.arcs =( v1 v2 v3 v4 v5 )v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表:顶点表:无向图的邻接矩阵如何表示?无向图的邻接矩阵如何表示?v1v2v3v5v4v418例例2 2 :有向图的邻接矩阵如何表示?:有向图的邻接矩阵如何表示?有向图的邻接矩阵可能
10、是不对称的。有向图的邻接矩阵可能是不对称的。顶点顶点v vi i的出度的出度= =第第i i行元素之和行元素之和; ; 顶点顶点v vi i的入度的入度= =第第i i列元素之和列元素之和; ; 顶点的度顶点的度= =第第i i行元素之和行元素之和+ +第第i i列元素之和。列元素之和。v1v2v3v4邻接矩阵:邻接矩阵:A.arcs =( v1 v2 v3 v4 )v1v2v3v4在有向图的邻接矩阵中,在有向图的邻接矩阵中, 第第i i行含义:以结点行含义:以结点v vi i为尾的弧为尾的弧( (即出度边);即出度边); 第第j j列含义:以结点列含义:以结点v vj j为头的弧为头的弧(
11、(即入度边)。即入度边)。顶点表:顶点表:0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 19例例3 3 : 有权图(即网络)的邻接矩阵如何表示?有权图(即网络)的邻接矩阵如何表示?定义:定义:A.arcs i j =Wij 或(或(vi, vj)VR 反之反之v1v2v3v4Nv5v65489755613邻接矩阵:邻接矩阵: N.arcs =(v1 v2 v3 v4 v5 v6)顶点表:顶点表: 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v620 容易实现图的操作,如:求某顶点的容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶度、判断顶点之
12、间是否有边(弧)、找顶点的邻接点等等。点的邻接点等等。 n n个顶点需要个顶点需要个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O(O(n n ) )。邻接矩阵法邻接矩阵法优点:优点:邻接矩阵法邻接矩阵法缺点:缺点:对稀疏图而言尤对稀疏图而言尤其浪费空间。其浪费空间。图的邻接矩阵在机内如何表示?图的邻接矩阵在机内如何表示? (参见教材(参见教材P161P161)注:注:用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 定义 术语 存储 结构 ppt 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内