DBS第十章s图.ppt
《DBS第十章s图.ppt》由会员分享,可在线阅读,更多相关《DBS第十章s图.ppt(72页珍藏版)》请在三一文库上搜索。
1、第10章 图,引 言 图是比线性表、树和集合更一般、更复杂的数据结构。 区别于线性结构、树结构和集合结构,在图结构中,数据元素之间的关系是任意的,每个元素都可以和任何其它元素相关。 本章讨论图的基本概念、图的存储表示方法以及若干常见的图运算,包括图的遍历和最小代价生成树。,数据结构,DATA STRUCTURE,内容提要 1、图的基本概念 2、图的存储结构 包括图的邻接矩阵表示和邻接表表示法及其实现 3、图的遍历:深度优先和宽度优先遍历 4、最小代价生成树:普里姆算法,10.1 图的基本概念,与线性表、树和集合不同,在图结构中,每个数据元素都可以与任何其它数据元素相关。图在许多方面都有所应用。
2、,课堂提要 第10章 图 10.1 图的基本概念 10.2 图的存储结构 10.3 图的遍历 10.5 最小代价生成 树,(b) (a)的图表示,(a) 电路示例,图10-1 电路示例及对应的图表示,图(graph):是数据结构 G=(V,E),其中V(G)是G中结点的有限非空集合,结点的偶对称为边(edge);E(G)是G中边的有限集合。 图中的结点又称为顶点(vertex)。,10.1.1 图的定义与术语,1,0,2,3,4,(a)图G1,图中 : V(G1)=0,1,2,3,4 E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4),有向图(dir
3、ected graph):指图中代表边的偶对是有序的。 用代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。 无向图(undirected graph):指图中代表边的偶对是无序的 在无向图中边(u,v )和(v,u)是同一条边。,1,0,2,3,4,(b)有向图G2,1,0,2,3,4,(a)无向图G1,1,0,2,3,4,1,0,2,3,4,(a)无向图G1,(b)有向图G2,图中 V(G1)=V(G2)=0,1,2,3,4 E(G1)=(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4) E(G2)=,自回路:如果图中存在无向边(u
4、,u)或有向边, 则称这样的边为自回路。 多重图:指图中两个顶点间允许有多条相同的边。,自回路和多重图的例子,邻接:如果(u,v)是无向图中的一条边,则称顶点u和v相邻接,并称边(u,v)与顶点u和v相关联。 例如:顶点1和2是相邻接的。,完全图:如果一个图有最多的边数,称为完全图。 无向完全图有n(n-1)/2条边, 有向完全图有n(n-1)条边。 例如:左图是一个完全图。有6条边。,无向完全图,如果是有向图中的一条边,则称顶点u邻接到v;称顶点v邻接自u ,并称边与顶点u和v相关联。,子图:图G的一个子图是图G=(V,E),其中V(G)V(G), E(G)E(G).,1,0,2,3,4,1
5、,0,2,3,4,G1,G2,路径:在无向图G中,一条从s到t的路径是存在一个顶点序 列(s,v1,v2,vk,t),使得(s,v1),(v1,v2),(vk,t) 都是图G中的边。 对于有向图顶点序列s,v1,v2,vk,t,应使, ,都是图G中的边。,路径长度: 指路径上边的数目。,简单路径: 除起点和终点可以相同外,路径上其余顶点各不相同。,回路: 起点和终点相同的简单路径。,(0,1,2,3);(0,1,2,3,4,2,0);(0,1,2,3,4,0)都是路径,它们的路径长度分别为3,6,5。 其中(0,1,2,3)和(0,1,2,3,4,0)是简单路径, (0,1,2,3,4,0)又
6、是回路。,无向图中如果两个顶点u和v之间存在一条路径,则称顶点u和v是连通的,否则是不连通的。 连通图:无向图中如果任意两个顶点之间是连通的。 连通分量:无向图的极大连通子图。,0和3是连通的。实际上该图任意两个顶点都是连通的,故该图是连通图。,0和6是不连通的。该图是非连通图,但它存在两个连通分量。,注意极大的含义:如果某个连通子图再加上一个顶点后,仍然是连通的,则它不是连通分量。,3,强连通图:有向图中如果任意两个顶点u和v之间,存在一条从u到v的路径,同时存在一条从v到u的路径,则称该有向图为强连通图。 强连通分量:有向图的极大强连通子图。,3,4,4,3,例如左图中,顶点1,2度分别为
7、2和4。 右图中,顶点0的入度和出度分别为3和1,顶点0的度为4,顶点2的入度和出度分别为?,顶点的度:与该顶点相关联的边的数目。 入度:有向图中顶点v的入度指以v为头的弧的数目; 出度:有向图中顶点v的出度指以v为尾的弧的数目。 有向图中,顶点的度=入度+出度。,生成树:无向图的生成树是一个极小连通子图,它包含图中所有顶点,但只有足以构成一棵树的(n-1)条边。去掉一条就不连通,再加上一条边将构成回路。,有向图的生成森林:是一个子图,由若干棵互不相交的有根有向树组成,包含图中所有的顶点。,1,0,2,3,4,图G1的生成树,图G1,有根有向树:是一个有向图,它恰有一个顶点的入度为0,其余顶点
8、的入度为1。如果略去边的方向,处理成无向图后,则图是连通的。,网:在图的每条边上加上一个数字称为权,也称代价, 带权的图称为网。,有向无环图(DAG图):不包含回路的有向图。 自由树:不包含回路的连通图。,ADT 101 Graph 数据: 顶点的非空集合V和边的集合E,每条边由V中顶点的偶对表示。 运算: void CreateGraph( Graph* g, int n, T noedge ) 后置条件: 已构造一个只有n个结点,不包含任何边的有向图。 BOOL Add( Graph *g, int u, int v, T w) 后置条件: 向图中添加权值为w(若边上没有权,则w0)的边,
9、若插入成功,则函数返回TRUE,否则返回FALSE。 BOOL Delete( Graph *g, int u, int v) 后置条件:从图中删除边,若删除成功,则函数返回TRUE,否则返回FALSE。 BOOL Exist( Graph g, int u, int v) 后置条件:如果图中存在边,则函数返回TRUE,否则返回FALSE。 int Vertices Graph g) 后置条件:函数返回图中顶点数目。 ,上面列出的只是图的最基本的运算。在以后的各小节中,我们将通过添加新运算,陆续扩充ADT 101 的图抽象数据类型。主要包括以下图运算: (1) 深度优先搜索图:void DFS
10、(Graph g); (2) 宽度优先搜索图:void BFS(Graph g); (3) 拓扑排序:void TopoSort(Graph g); (4) 关键路径:void CriticalPath(Graph g); (5) 普里姆算法求最小代价生成树:void Prim(Graph g,int k); (6) 克鲁斯卡尔算法求最小代价生成树:void Kruskal(Graph g,int edges); (7) 迪杰斯特拉算法求单源最短路径:void Dijkstra(Graph g,int k, T d, int p); (8) 弗洛伊德算法求所有顶点之间的最短路径:void Fl
11、oyd(Graph g,T*&d, int *&path)。,1、图的矩阵表示法及其实现 2、图的邻接表表示法及其实现,10.2 图的存储结构,10.2.1 图的矩阵表示法,1、邻接矩阵,一个有n个顶点的图G=(V,E)的邻接矩阵是一个nn的矩阵A,A的每个元素是0或1。,课堂提要 第10章 图 10.1 图的基本概念 10.2 图的存储结构 10.3 图的遍历 10.5 最小代价生成 树,设V=0,1,2,n-1,如果G是无向图,则A的元素定义为:,如果G是有向图,则A的元素定义为:,如果G是带权的有向图(网),那么A中的元素定义如下:,图 10.7 图的邻接矩阵,0,邻接矩阵,例如:,0,
12、如果G是有向图,则A的元素定义为:,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,强连通分量,1、邻接矩阵C语言定义,10.2.2 图的邻接矩阵实现,typedef struct graph T NoEdge; /两结点间无边时的值(0或) int Vertices; /图中顶点数 T* A; /指向存储邻接矩阵的二维数组的指针 Graph;,建立邻接矩阵( 【程序101】 )。 void CreateGraph(Graph* g, int n, T noedge ) int i, j; g-No
13、Edge=noedge; g-Vertices=n; g-A=(T*)malloc(n*sizeof(T*); for(i=0; iAi=(T*)malloc(n*sizeof(T); for (j=0; jAij=noedge; g-Aii=0; ,a,L,O,M,M,O,L,L,0,0,0,0,noedge,noedge,noedge,noedge,noedge,noedge,BOOL Exist(Graph g, int u,int v) if(un-1|vn-1|u=v|auv=noEdge) return false; return true; ,3、边的搜索、插入和删除,/判边是否
14、存在,3,1是否有边?,1,3是否有边?,有边!,无边!,BOOL Add(Graph *g, int u, int v, T w) int n=g-Vertices; if(un-1 | vn-1 | u=v | g-Auv!=g-NoEdge) printf(“BadInputn“); return FALSE; g-Auv=w; return TRUE; ,/边的插入,1,插入0,2边,/边的删除 BOOL Delete(Graph *g, int u, int v) int n=g-Vertices; if(un-1 | vn-1 | u=v | g-Auv=g-NoEdge) pri
15、ntf(“BadInputn“); return FALSE; g-Auv=g-NoEdge; return TRUE; ,1,删除0,2边,10.2.3 邻接表表示法,要点: 1、为图中每一个顶点建立一个单链表; 2、顶点u的单链表中的每一个结点指示u的一个邻接点v , 即代表一条边(u,v) 或 顶点u的单链表记录了与u相邻接(邻接自u)的所有顶点。 每个单链表相当于邻接矩阵的一行,它指示了该行中的非零的元素。,01 2 3,1 ,3 ,0,0,2 ,3、边结点的结构,指示顶点u的一个邻接点,指向u的下一个边结点,边上的权值,u,1 ,3 ,v,0,2 ,存放顶点的名称及其他信息,指向u的
16、第一个边结点,u,1 ,3 ,v,0,2 ,4、每个单链表可设立一个存放顶点u的有关信息的表头结点,也称顶点结点。顶点结点存入一个一维数组。,01 2 3,(a)图G1的邻接表,01 2 3,1 ,3 ,0,0,2 ,(b)图G2的邻接表,typedef struct enode int AdjVex; T W; struct enode * NextArc; ENode; typedef struct graph int Vertices ; ENode* A; Graph;,边结点的结构类型,图中的顶点数,3. 建立邻接表 函数CreateGraph构造一个有n个顶点,但不包含边的有向图。
17、由于图的顶点数事先并不知道,所以我们使用动态存储分配的一维指针数组。,void CreateGraph(Graph* g, int n) int i; g-Vertices=n; g-A=(ENode*)malloc(n*sizeof(ENode*); for(i=0; iAi=NULL; ,搜索、插入或删除从顶点u发出的边,只在Au所指向的单链表中操作。程序如下:,3、边的搜索、插入和删除,3 ,2,0,1,2是否有边?,/搜索边的函数 BOOL Exist(Graph g, int u, int v) int n; ENode* p; n=g.Vertices; if(un-1) retu
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DBS 第十
链接地址:https://www.31doc.com/p-2976492.html