《软件技术基础概论 教学课件 ppt 作者 吕林涛第5章 图》由会员分享，可在线阅读，更多相关《软件技术基础概论 教学课件 ppt 作者 吕林涛第5章 图（42页珍藏版）》请在金锄头文库上搜索。
1、21:04:38,第5章 图,21:04:38,相对于树结构： 图结构是一种更复杂的非线性结构 两个结点之间的邻接关系可以是任意的 图结构可用来描述更加复杂的对象,21:04:38,本章主要内容: 图的基本概念 图的存储结构 图的遍历,21:04:38,5.1 图的基本概念,图的定义,图的基本术语,21:04:38,图（Graph）是由非空的顶点集合V与描述顶点之间关系边（或者弧）的集合E组成，其形式化定义为：G=(V, E),图G中的每一条边都是没有方向的 边是图中顶点的无序偶对：(vi, vj) (vi, vj)表示顶点vi和顶点vj相连的边 (vi, vj)与(vj, vi)表示同一条边
2、 vi和vj互为邻接点,无向 图,21:04:38,无向图的表示,G1=(V1, E1) 其中： V1=v1, v2, v3, v4 E1=(v1, v2), (v1, v4), (v2, v4), (v3, v4),21:04:38,图G中的每一条边都是有方向的 边是图中顶点的有序偶对：vi, vj vi, vj 表示从顶点vi指向顶点vj的一条有向边 vi邻接到vj，或者接vj邻接于vi vi, vj 依附于vi和vj,有向 图,21:04:38,有向图的表示,G2=(V2, E2) 其中： V2=v1, v2, v3, v4, v5 E2 =, , , , , ,21:04:38,5.1
3、 图的基本概念,图的定义,图的基本术语,21:04:38,无向完全图：任意两个顶点之间都有一条边的无向图 有向完全图：任意两个顶点之间都有方向相反的两条边存在的有向图 顶点的度：顶点的度是指依附于顶点v的边数，通常记为D(v)。 有向图中顶点的入度、出度：顶点v的入度是指以v为终点的边的个数，记为ID(v)；顶点v的出度是指以v为起点的边的个数，记为OD(v)。 有向图顶点的度：定义为该顶点的入度和出度之和，即D(v)=ID(v)OD(v)。,21:04:38,路径、路径长度：若G为无向图，则从顶点vp到顶点vq的路径是指存在一个顶点序列：vp, vi1, vi2, , vin, vq，使得(
4、vp, vi1), (vi1, vi2), , (vin, vq)分别为图G中的边；若G为有向图，其路径也是有方向的，它由图G中的有向边vp, vi1,vi1, vi2, ,vin, vq组成。路径长度是路径上边或弧的个数 回路、简单路径、简单回路：若一条路径上的起点和终点相同，则称该路径为回路或环。若路径中的顶点不重复出现，则称该路径为简单路径。 子图：对图G=(V, E)和图G=(V, E)，若存在V是V的子集，E是E的子集，且E中的边都依附于V中的顶点，则称图G是G的一个子图,21:04:38,连通和连通图：在无向图中，如果从顶点vi到另一顶点vj（ij）有路径，则称顶点vi和顶点vj是
5、连通的。如果图中任意两个顶点都是连通的，则称该图是连通图 强连通和强连通图：在有向图中，如果从顶点vi到另一个顶点vj（ij）有路径，则称顶点vi到顶点vj是连通的。若图中任意一对顶点vi和vj（ij）均有从顶点vi到顶点vj的路径，也有从顶点vj到顶点vi的路径，则称该有向图是强连通图,21:04:38,21:04:38,21:04:38,本章主要内容: 图的基本概念 图的存储结构 图的遍历,21:04:38,从图的定义可知，一个图的信息包括两个部分：图中顶点的信息以及描述顶点之间的关系边或弧的信息。无论采取什么方法来建立图的存储结构，都要完整、准确地反映这两部分的信息。 为适于用C语言描述
6、，从本节起顶点序号由0开始，即图的顶点集的一般形式为 V=v0, v1, , vn-1,21:04:38,5.2 图的存储结构,邻接矩阵,邻接表,21:04:38,邻接矩阵存储结构：用一维数组存储图中顶点的信息，并用矩阵来表示图中各顶点之间的邻接关系。 假定图G=(V, E)有n个顶点，即V=v0, v1, , vn-1，则表示G中各顶点相邻关系需用一个nn的矩阵，且矩阵元素为：,21:04:38,21:04:38,在采用邻接矩阵方式表示图时，除了用一个二维数组存储用于表示顶点相邻关系的邻接矩阵之外，还需要用一个一维数组存储顶点信息。一个图在顺序存储结构下的类型定义如下：,typedef st
7、ruct char vertexMAXSIZE; /顶点为字符型且顶点表的长度小于MAXSIZE int edgesMAXSIZEMAXSIZE; /边为整型且edges为邻接矩阵 MGraph; /MGraph为采用邻接矩阵存储的图类型,21:04:38,建立一个无向图的邻接矩阵存储程序员如下:,void CreatMGraph(MGraph *g, int e, int n) /建立无向图的邻接矩阵g-egdes，n为顶点个数，e为边数 int i, j, k; printf(“Input data of vertexs(0n-1): n“); for(i=0;ivertexi=i; /读
8、入顶点信息 for(i=0;iedgesij=0; /初始化邻接矩阵 for(k=1;kedgesij=1; g-edgesji=1; ,21:04:38,5.2 图的存储结构,邻接矩阵,邻接表,21:04:38,邻接表储结构：是一种顺序存储与链式存储相结合的存储方法。对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表；然后，将所有顶点的邻接表表头指针放入到一个一维数组中，就构成了图的邻接表,21:04:38,21:04:38,邻接表类型定义：,typedef struct node /邻接表结点 int adjvex; /邻接点域 struc
9、t node *next; /指向下一个邻接边结点的指针域 EdgeNode; /邻接表结点类型 typedef struct vnode /顶点表结点 int vertex; /顶点域 EdgeNode *firstedge; /指向邻接表第一个邻接边结点的指针域 VertexNode; /顶点表结点类型,21:04:38,建立一个无向图的邻接表存储程序：,void CreatAdjlist(VertexNode g, int e, int n) /建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 EdgeNode *p; int i, j, k; printf(“Input
10、date of vertex(0n-1);n“); for(i=0;iadjvex=j; /在顶点vi的邻接表中添加邻接点为j的结点 p-next=gi.firstedge; /插入是在邻接表表头进行的 gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; ,21:04:38,21:04:38,本章主要内容: 图的基本概念 图的存储结构 图的遍历,21:04:38,图的遍
11、历是指从图中的任一顶点出发，按照事先确定的某种搜索方法依次对图中所有顶点进行访问且仅访问一次的过程。其复杂性主要表现在以下四个方面： （1）任何一个顶点都可以作为第一个被访问的结点 （2）在非连通图中，从一个顶点出发只能访问它所在的连通分量上的顶点，需考虑如何选取下一个未被访问的顶点来继续访问图中其余的连通分量 （3）如果有回路存在，则一个顶点被访问后有可能沿回路又回到该顶点 （4）一个顶点可以和其他多个顶点相邻，当该顶点访问过后则存在如何从众多相邻顶点中选取下一个要访问的顶点问题,21:04:38,5.3 图的遍历,深度优先遍历,广度优先遍历,图的应用,21:04:38,深度优先的基本思想是
12、：假设初始状态是图中所有顶点都未曾访问过，则深度优先搜索可以从图中某个顶点v出发即先访问v，然后依次从v的未曾访问过的邻接点出发，继续深度优先搜索图，直至图中所有和v有路径相通的顶点都被访问过。若此时图中尚有顶点未被访问过，则另选一个未曾访问过的顶点作为起始点，重复上述深度优先搜索的过程，直到图中的所有顶点都被访问过为止。,21:04:38,深度优先类似于树的先根遍历，是树的先根遍历的一种推广，搜索顶点的次序是沿着一条路径尽量向纵深发展,v0 v1 v3 v6 v4 v2 v5,21:04:38,深度优先搜索遍历图的过程是一个递归过程，可以用递归算法来实现。在算法中为了避免在访问过某顶点后又沿
13、着某条回路回到该顶点这种重复访问的情况出现，就必须在图的遍历过程中对每一个访问过的顶点进行标识。在遍历算法中对n个顶点的图设置了一个长度为n的访问标志数组visitedn，每个数组元素被初始化为0，一旦某个顶点i被访问则相应的visitedi就置为1来作为访问过的标志。,21:04:38,深度优先遍历的算法程序如下：,int visitedMAXSIZE; /MAXSIZE为大于或等于无向图顶点个数的常量 void DFS(VertexNode g, int i) EdgeNode *p; printf(“%4d“, gi.vertex); /输出顶点i信息，即访问顶点i visitedi=1
14、; /置顶点i为访问过的标志 p=gi.firstedge; /根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) /当邻接边结点不为空时 if(!visitedp-adjvex) /如果邻接的这个边结点未被访问过 DFS(g, p-adjvex); /对这个边结点进行深度优先搜索 p=p-next; /查找顶点i的下一个邻接边结点 void DFSTraverse(VertexNode g, int n) /深度优先搜索遍历用邻接表存储的图，其中g为顶点表，n为顶点个数 int i; for(i=0;in;i+) visitedi=0; /访问标志
15、置0 for(i=0;in;i+) /对n个顶点的图查找未访问过的顶点并由该顶点开始遍历 if(!visitedi) /当visitedi等于0时即顶点i未访问过 DFS(g, i); /从未访问过的顶点i开始遍历 ,21:04:38,5.3 图的遍历,深度优先遍历,广度优先遍历,图的应用,21:04:38,广度优先搜索的基本思想是：从图中某顶点v出发，访问顶点v后再依次访问与v相邻接的未曾访问过的其余邻接边结点v1，v2，vk；接下来再按上述方法访问与v1邻接的未曾访问过的各邻接边结点，与v2邻接的未曾访问过的各邻接边结点与vk邻接的未曾访问过的各邻接边结点，这样逐层下去直至图中的全部顶点都被访问过。广度优先搜索遍历图的特点是尽可能先进行横向搜索，即先访问的顶点其邻接边结点也先访问，后访问的顶点其邻接边结点也后访问。,21:04:38
