七章图.PPT
《七章图.PPT》由会员分享,可在线阅读,更多相关《七章图.PPT(142页珍藏版)》请在三一文库上搜索。
1、1,第七章 图,图(Graph)是一种较线性表和树更为复杂的数据结构。 线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关; 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。,2,图(Graph)是由非空的顶点集合和一个描述顶点之间关系边(或者弧)的集合组成,其形式化定义为: G(V,E) Vvi| vidataobject E( vi,vj)| vi, vj V P(vi, vj) 其中,G表示一个图,V是
2、图G中顶点的集合,E是图G中边的集合,集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线,即偶对(vi,vj)表示一条边。,图的定义和术语,3,在该图中 集合Vv1,v2,v3,v4,v5; 集合E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。,(1)无向图 在一个图中,如果任意两个顶点构成的偶对(vi, vj)E是无序的,即顶点之间的连线是没有方向的,则称该图为无向图。如下图所示是一个无向图G1。,4,(2)有向图 在一个图中,如果任意两个顶点构成的偶对(vi, vj)E是有序的,即顶点之间的连线是有方向的,则称该图为有向图。,
3、G2=(V2,E2) V2=v1,v2,v3,v4 E2=, , , ,5,(3)顶点、边、弧、弧头、弧尾。 图中,数据元素vi称为顶点(vertex );(vi, vj)表示在顶点vi和顶点vj之间有一条直接连线。 在无向图中,则称这条连线为边;边用顶点的无序偶对(vi, vj)来表示,称顶点vi和顶点vj互为邻接点,边(vi, vj)依附于顶点vi与顶点vj; 在有向图中,一般称这条连线为弧。弧用顶点的有序偶对来表示,有序偶对的第一个结点vi被称为始点(或弧尾),在图中就是不带箭头的一端;有序偶对的第二个结点vj被称为终点(或弧头),在图中就是带箭头的一端。,6,(4)无向完全图。在一个无
4、向图中,如果任意两顶点都有一条直接边相连接,则称该图为无向完全图。在一个含有n个顶点的无向完全图中,有n(n-1)/2条边。 (5)有向完全图。在一个有向图中,如果任意两顶点之间都有方向互为相反的两条弧相连接,则称该图为有向完全图。在一个含有n个顶点的有向完全图中,有n(n-1)条边。 (6)稠密图、稀疏图。若一个图接近完全图,称为稠密图;称边数很少的图为稀疏图。,7,(7)顶点的度、入度、出度。 顶点的度(degree)是指依附于某顶点v的边数,通常记为TD(v) 。 在有向图中,要区别顶点的入度与出度的概念。顶点v的入度是指以顶点为终点的弧的数目,记为ID(v);顶点v出度是指以顶点v为始
5、点的弧的数目,记为OD(v)。 TD(v)=ID(v)OD(v)。,在G1中有: D(v1)=2 D(v2)=3 D(v3)=3 D(v4)=2 D(v5)=2,8,在G2中有: ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2,对于具有n个顶点、e条边的图,顶点vi的度D (vi)与顶点的个数以及边的数目满足关系:,9,8)边的权、网图。 与边有关的数据信息称为权(weight)。边上带权的图称为网图或网络(network)。如
6、果边是有方向的带权图,则就是一个有向网图。,10,(9)路径、路径长度。顶点vp到顶点vq之间的路径(path)是指顶点序列vp,vi1,vi2, , vim,vq.。其中,(vp,vi1),(vi1,vi2),,(vim,.vq)分别为图中的边。路径上边的数目称为路径长度。,无向图G1中,v1v4v3v5与v1v2v5是从顶点v1 到顶点v5 的两条路径,路径长度分别为3和2。,11,(10)回路、简单路径、简单回路。 序列中顶点不重复出现的路径称为简单路径。 除第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,或者简单环。,如图中的v1v3v4v1。,12,(11)子图。
7、对于图G=(V,E),G=(V,E),若存在V是V的子集 ,E是E的子集 ,且E中的边所关联的顶点均在V中,则称图G是G的一个子图。,13,(12)连通的、连通图、连通分量。在无向图中,如果从一个顶点vi到另一个顶点vj(ij)有路径,则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的,则称该图是连通图。无向图的极大连通子图称为连通分量。,14,(13)强连通图、强连通分量。对于有向图来说,若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径,也有从vj到vi的路径,则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。,15,7.2 图的存储结构,邻接
8、矩阵(Adjacency Matrix)的存储结构,就是用一维数组存储图中顶点的信息,用矩阵表示图中各顶点之间的邻接关系。假设图G(V,E)有n个确定的顶点,即Vv0,v1,vn-1,则表示G中各顶点相邻关系为一个nn的矩阵,矩阵的元素为: 1 若(vi,vj)或是E(G)中的边 Aij= 0 若(vi,vj)或不是E(G)中的边,7.2.1数组表示法(也称为邻接矩阵表示法),16,若G是网图,则邻接矩阵可定义为: wij 若(vi,vj)或是E(G)中的边 Aij= 0或 若(vi,vj)或不是E(G)中的边 其中,wij表示边(vi,vj)或上的权值;表示一个计算机允许的、大于所有边上权值
9、的数。,17,define INFINITY INT_MAX /最大值 define MAX_VERTEX_NUM 20 /最大顶点个数 typedef enum DG,DN,UDG,UDN GraphKind;/ typedef struct ArcCell VRType adj; /弧是否相通,或权值 InfoType *info; /弧的相关信息 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; /邻接矩阵
10、int vexnum, arcnum; /图的当前顶点和弧数 GraphKind kind; /图的种类标志 Mgraph;,图的数组(邻接矩阵)存储表示,18,通过邻接矩阵,求的各个顶点的度 对于无向图:,对于有向图,出度,入度,19,算法7.1在邻接矩阵的存储结构上创建图,Status CreateGraph( MGraph / CreateGraph,20,Status CreateUDN(MGraph / CreateUDN,算法 7.2采用数组(邻接矩阵)表示法,构造无向网G,21,7.2.2 邻接表,22,邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i
11、个单链表中的结点表示依附于顶点Vi的边。 头结点 表结点 因为是每个顶点建立一个单链表,每个单链表的表头结点通常以顺序存储结构(一维数组)的形式存储,以便随机访问任一顶点的链表。,23,邻接表存储表示,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode; /边表结点 typedef struct VNode VertexType data; ArcNode *firstarc; Vnode, AdjListMAX_VERTEX_
12、NUM; /表头结点 typedef struct AdjList vertices; int vexnum , arcnum; /顶点数和弧数 int kind; /图的种类标志 ALGraph;,24,建立无向图的邻接表,creatadjlist(ALGraph ga ) int i,j,k; ArcNode *s; for (i=0; iadjvex=j; s- nextarc = ga. vertices i. firstarc; ga. vertices i. firstarc =s; s=(ArcNode *)malloc(sizeof(ArcNode); s-adjvex=i;
13、s- nextarc = ga. vertices j. firstarc; ga. vertices j. firstarc =s; ,25,相对于矩阵存储,对于稀疏图,采用邻接表存储能节省空间; 对于无向图的邻接表,表头结点对应的单链表的结点个数图中对应结点的度; 对于有向图的邻接表,表头结点对应的单链表的结点个数图中对应结点的出度; 为了方便求有向图的入度,可以建立一个图的逆邻接表; 逆邻接表:在表头结点所指向的链表中存放的是,指向该表头结点的弧的始点;(如图P164,P7.10的c),26,7.2.3 十字链表,十字链表(Orthogonal List)是有向图的一种存储方法,它实际上
14、是邻接表与逆邻接表的结合,即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。,27,28,有向图的十字链表存储表示的形式描述如下: #define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex , headvex; /*该弧的尾和头顶点的位置*/ struct ArcBox * hlink, *tlink; /分别为弧头和弧尾 相同的弧的链域*/ InfoType info; /*该弧相关信息的指针*/ ArcBox; typedef struct VexNode VertexType data: Ar
15、cBox *fisrin, *firstout; /*分别指向该顶点第一条入弧和出弧*/ VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; /*表头向量*/ int vexnum , arcnum; /*有向图的顶点数和弧数*/ OLGraph;,29,Status CreateDG(OLGraph / 输入弧含有相关信息,此略 / CreateDG,算法7.3采用十字链表存储表示,构造有向图G,30,7.2.4邻接多重表,邻接多重表(Adjacency Multilist)主要用于存储无向图。因为,如果用邻接表存储无向图,每条边的两个边
16、结点分别在以该边所依附的两个顶点为头结点的链表中,这给图的某些操作带来不便。例如,对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。,31,32,33,邻接多重表存储表示的形式描述如下: #define MAX_VERTEX_NUM 20 typedef emnu unvisited,visited VisitIf; typedef struct EBox VisitIf mark: /*访问标记*/ int ivex , jvex; /*该边依附的两个顶点的位置*/ struct EBox
17、 *ilink , *jlink; /*分别指向依附这两个顶点的下一条边*/ InfoType info; /*该边信息指针*/ EBox; typedef struct VexBox VertexType data; EBox *fistedge; /*指向第一条依附该顶点的边*/ VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum , edgenum; /*无向图的当前顶点数和边数*/ AMLGraph;,34,7.3 图的遍历,从图中某一顶点出发访遍图中所有顶点,且使图中每一顶点仅被访问一次,这一过程称图的遍
18、历。 为了便于记录顶点有否访问过,设一个数组visitedn,当visitedi=1时表示顶点Vi已访问过;当 visiti=0时表示顶点Vi未访问过。 图的遍历包括:深度优先搜索和广度优先搜索。,35,深度优先搜索(depth_first_search),假定给定G的初态是所有顶点匀未曾访问过,在G中任选一顶点Vi为初始出发点,则深度优先搜索可定义如下: 首先,访问出发点Vi,并将其标记为已访问过,然后,依此从Vi出发搜索Vi的某一个邻接点Vj,若Vj未曾访问过,则以Vj为新的出发点继续进行深度优先搜索;重复上述过程,直到图中所有顶点都被访问过为止。,36,/ 算法7.4 对图G作深度优先遍
19、历。 bool VisitedMAX; Status (*VisitFunc)(int v) void DFSTraverse(Graph G, Status (*Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = false; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS void DFS(Graph G, int v) / 算法7.5 visitedv = true; VisitFunc(v); / 访问第v个顶点 f
20、or (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) DFS(G, w); ,37,深度优先搜索的时间复杂度 如采用邻接矩阵存储,则时间复杂度为:O(n2) 如采用邻接表存储存储,则时间复杂度为:O(ne),38,连通图深度优先搜索举例(矩阵表示),39,/图的结构 typedef struct vextype vexsn; adjtype arcsnn; graph;,40,/*从Vi+1出发深度优先搜索图g,g用邻接矩阵表示*/ int visitedn ; /全局变量 graph g ; /全局变量 DF
21、S( int i ) int j; printf(“node:%cn”,g.vexsi); visitedi=1; for (j=0;jn;j+) if (g.arcsij=1) /递归调用 ,41,连通图深度优先搜索举例(邻接表),无向图如下: 该图的邻接表如下:,该图的遍历顺序为:,42,typedef struct node int adjvex; struct node *next; edgenode; typedef struct vextype vertex; edgenode *link; vexnode;,42,43,/*从Vi+1出发深度优先搜索图gl,gl用邻接表表示*/
22、vexnode gln DFSL(int i ) int j; edgenode *p; printf(“node:%cn”,gli.vertex); visitedi=true; p=gli.link; while(p!=null) if (!visited p-adjvex) DFSL(p-adjvex); /递归调用 p=p-next; ,44,广度优先搜索(breadth-first-search),从图中某顶点Vi出发,在访问了Vi之后依次访问Vi的各个未曾访问过的邻接点,再依次从这些邻接点出发广度搜索遍历图,直至图中所有的顶点都访问过。,45,void BFSTraverse(Gr
23、aph G, Status (*Visit)(int v ) for (v=0; v=0; w=NextAdjVex(G, u, w) if (!visitedw) / u的尚未访问的邻接顶点w入队列Q visitedw = TRUE; Visit(w); EnQueue(Q, w); /if /while /if / BFSTraverse,算法7.6 按广度优先非递归遍历图G。,46,连通图广度优先搜索举例(矩阵表示),0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 七章图
链接地址:https://www.31doc.com/p-3182614.html