图零基础学数据结构.ppt

,Click to edit Master title style,Click to edit Master text styles,图零基础学数据结构,10.1 图的定义与相关概念,图是一种非线性的数据结构，图中的数据元素之间的关系是多对多的关系。本节主要介绍图的定义和图的相关概念。,10.1.1 图的定义,图G是由数据元素集合V与边的集合E组成的一种数据结构。数据元素常称为顶点，因此数据元素集合称为顶点集合。其中，顶点集合V不能为空，边表示顶点之间的关系，用连线表示。图G的形式化定义为：G=(V,E)，其中，V=x|x数据元素集合，E=|Path(x,y)/(xV,yV)。,10.1.1 图的定义,10.1.2 图的相关概念,1邻接点,2顶点的度,3路径,4子图,5连通图和强连通图,6生成树,7网,10.1.2 图的相关概念,子图：,10.1.2 图的相关概念,连通图与强连通图：,10.1.2 图的相关概念,生成树：,10.1.2 图的相关概念,网：,10.1.3 图的抽象数据类型,1数据对象集合,2基本操作集合,10.2 图的存储结构,图的存储方式有四种：邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链表表示法。本节的主要学习内容是图的这四种存储结构。,10.2.1 邻接矩阵表示法,图的邻接矩阵表示也称为数组表示，图的邻接矩阵就是利用C语言中的两个数组实现。其中一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。,10.2.1 邻接矩阵表示法,10.2.1 邻接矩阵表示法,图的邻接矩阵存储结构可以用C语言描述如下：,#define INFINITY 10000/*定义一个无限大的值*/,#define MaxSize 50/*最大顶点个数*/,typedef enumDG,DN,UG,UNGraphKind;/*图的类型：有向图、有向网、无向图和无向网*/,typedef struct,VRType adj;/*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/,InfoPtr*info;/*与弧或边的相关信息*/,ArcNode,AdjMatrixMaxSizeMaxSize;,typedef struct/*图的类型定义*/,VertexType vexMaxSize;/*用于存储顶点*/,AdjMatrix arc;/*邻接矩阵，存储边或弧的信息*/,int vexnum,arcnum;/*顶点数和边（弧）的数目*/,GraphKind kind;/*图的类型*/,MGraph;,10.2.2 邻接表表示法,图的邻接表表示法是一种链式存储方式。在图的邻接表中，对图中的每个顶点都建立一个单链表，用来表示边或弧，这种表示顶点之间关系的链表称为边表，相应地，结点称为边结点。在每个单链表前面设置一个头结点，存放图中的各个顶点结点，这种表称为表头结点表，相应地，结点称,为表头结点。,10.2.2 邻接表表示法,10.2.2 邻接表表示法,图的邻接表存储结构可以用C语言描述如下：,#define MaxSize 50/*最大顶点个数*/,typedef enumDG,DN,UG,UNGraphKind;/*图的类型：有向图、有向网、无向图和无向网*/,typedef struct ArcNode/*边结点的类型定义*/,int adjvex;/*弧指向的顶点的位置*/,InfoPtr*info;/*与弧相关的信息*/,struct ArcNode*nextarc;/*指示下一个与该顶点相邻接的顶点*/,ArcNode;,typedef struct VNode/*头结点的类型定义*/,VertexType data;/*用于存储顶点*/,ArcNode*firstarc;/*指示第一个与该顶点邻接的顶点*/,VNode,AdjListMaxSize;,typedef struct/*图的类型定义*/,AdjList vertex;,int vexnum,arcnum;/*图的顶点数目与弧的数目*/,GraphKind kind;/*图的类型*/,AdjGraph;,10.2.2 邻接表表示法,图的逆邻接链表表示,10.2.3 十字链表表示法,十字链表是有向图的又一种链式存储结构，它是将有向图的邻接表与逆邻接链表结合起来的存储结构表示。因此，在十字链表中，同样包括表头结点和边结点。在十字链表中，将表头结点称为顶点结点，边结点称为弧结点。,10.2.3 十字链表表示法,有向图的十字链表存储结构可以用C语言描述如下：,#define MaxSize 50/*最大顶点个数*/,typedef struct ArcNode/*弧结点的类型定义*/,int headvex,tailvex;/*弧的头顶点和尾顶点位置*/,InfoPtr*info;/*与弧相关的信息*/,struct*hlink,*tlink;/*指示弧头和弧尾相同的结点*/,ArcNode;,typedef struct VNode/*顶点结点的类型定义*/,VertexType data;/*用于存储顶点*/,ArcNode*firstin,*firstout;/*分别指向顶点的第一条入弧和出弧*/,VNode;,typedef struct/*图的类型定义*/,VNode vertexMaxSize;,int vexnum,arcnum;/*图的顶点数目与弧的数目*/,OLGraph;,10.2.4 邻接多重链表表示法,邻接多重链表表示是无向图的另一种链式存储结构。在无向图的邻接表存储表示中，虽然可以很容易对邻接表进行操作，但是图的每一条边在邻接表中需要存储两个结点，如果要检查某个边是否被访问过，则需要在邻接表中找到两个结点。而邻接多重表是将图的一条边用一个结点表示。,10.2.4 邻接多重链表表示法,10.2.4 邻接多重链表表示法,无向图的多重链表存储结构可以用C语言描述如下：,#define MaxSize 50/*最大顶点个数*/,typedef struct EdgeNode/*边结点的类型定义*/,int mark,ivex,jvex;/*访问标志和边的两个顶点位置*/,InfoPtr*info;/*与边相关的信息*/,struct*ilink,*jlink;/*指示与边顶点相同的结点*/,EdgeNode;,typedef struct VNode/*顶点结点的类型定义*/,VertexType data;/*用于存储顶点*/,EdgeNode*firstedge;/*指向依附于顶点的第一条边*/,VexNode;,typedef struct/*图的类型定义*/,VexNode vertexMaxSize;,int vexnum,edgenum;/*图的顶点数目与边的数目*/,AdjMultiGraph;,10.3 图的应用举例,本节主要采用邻接矩阵和邻接表作为存储结构，说明图的创建和图的输出等相关操作。,10.3.1 采用邻接矩阵创建图,下面通过一个实例来说明采用邻接矩阵的图的创建。,例10_1 编写算法，采用邻接矩阵创建一个有向网N。,1图的相关操作,2测试部分,10.3.2 采用邻接表创建图,下面通过一个实例来说明采用邻接表创建图。,例10_2 编写算法，采用邻接表创建一个无向图G。,1图的相关操作,2测试部分,10.4 图的遍历,与树类似，遍历也是图的一种重要的操作，图的遍历是访问图中每个顶点仅被访问一次的操作。图的遍历方式主要有两种：深度优先遍历和广度优先遍历。本节的主要学习内容包括图的深度优先遍历、图的广度优先遍历。,10.4.1 图的深度优先遍历,1图的深度遍历的定义,2图的深度遍历的算法实现,10.4.2 图的广度优先遍历,1图的广度优先遍历的定义,2图的广度优先遍历的算法实现,10.4.3 图的遍历应用举例,下面利用一个例子来说明图的深度优先遍历和广度优先遍历的应用。,例10_3 采用邻接表创建一个无向图G6，并实现对图的深度优先遍历和图的广度优先遍历。,10.5 图的连通性问题,在第一节已经介绍了连通图和强连通图，在图的具体应用中也会经常涉及到图的连通性问题。本节的主要学习内容包括无向图的连通性和最小生成树。,10.5.1 无向图的连通分量与生成树,在无向图的深度优先和广度优先遍历的过程中，对于连通图，从任何一个顶点出发，就可以遍历图中的每一个顶点。,10.5.1 无向图的连通分量与生成树,10.5.2 最小生成树,1普里姆算法,2克鲁斯卡尔算法,10.5.2 最小生成树,普里姆算法,10.5.2 最小生成树,10.5.2 最小生成树,下面通过一个例子来说明普里姆算法的应用。,例10_4 利用邻接矩阵创建一个图10.24所示的无向网N，然后利用普里姆算法求无向网的最小生成树。,10.5.2 最小生成树,10.5.2 最小生成树,2克鲁斯卡尔算法,10.6 有向无环图,有向无环图是描述工程或系统过程的一个非常重要的工具。有向无环图是指一个没有环的有向图。在有向无环图描述工程的过程中，将工程分为若干个活动，即子工程。在这些子工程即活动之间，它们之间互相制约。,10.6.1 AOV网与拓扑排序,1AOV网,10.6 有向无环图,10.6.1 AOV网与拓扑排序,2拓扑排序,10.6.2 AOE网与关键路径,1AOE网,10.6.2 AOE网与关键路径,2关键路径,10.6.3 关键路径应用举例,例10_5 采用邻接表创建如图10.30所示的有向网，并求网中顶点的拓扑序列，然后计算该有向网的关键路径。,1有向网的关键路径,2有向网的创建与输出,3测试代码部分,10.6.3 关键路径应用举例,10.7 最短路径,在日常生活中，经常会遇到求两个地点之间的最短路径的问题，如在交通网络中城市A与城市B的最短路径。可以将每个城市作为图的顶点，两个城市的线路作为图的弧或者边，城市之间的距离作为权值，这样就把一个实际的问题转化为求图的顶点之间的最短路径问题。,10.7.1 从某个顶点到其余各顶点的最短路径,1从某个顶点到其它顶点的最短路径算法思想,10.7.1 从某个顶点到其余各顶点的最短路径,10.7.1 从某个顶点到其余各顶点的最短路径,例10_6 建立一个如图10.33所示的有向网N，输出该有向网N中从v0开始到其它各顶点的最短路径及从v0到各个顶点的最短路径长度。,10.7.2 每一对顶点之间的最短路径,如果要计算每一对顶点之间的最短路径，只需要以任何一个顶点为出发点，将迪杰斯特拉算法重复执行n次，就可以得到每一对顶点的最短路径。这样求出的每一个顶点之间的最短路径的时间复杂度为O(n,3,)。,1各个顶点之间的最短路径算法思想,2各个顶点之间的最短路径算法实现,3弗洛伊德算法应用举例,10.7.2 每一对顶点之间的最短路径,10.7.2 每一对顶点之间的最短路径,例10_7 创建如图10.36所示的有向网，并利用弗洛伊德算法求解各个顶点之间的最短路径长度，并输出最短路径所经过的顶点。,10.8 图的应用举例,本节将通过几个具体实例来说明图的具体应用。其中包括求图中距离顶点v的最短路径长度为k的所有顶点、求图中顶点u到顶点v的简单路径。,10.8.1 距离某个顶点的最短路径长度为k的所有顶点,下面通过一个实例，说明距离某个顶点v,0,的最短路径长度为k的所有顶点的算法实现。,例10_8 创建一个无向图G，求距离顶点v0的最短路径长度为k的所有顶点。,10.8.2 求图中顶点u到顶点v的简单路径,要求图中顶点u到顶点v的简单路径，其实也是有关图的遍历问题。下面以一个实例来说明求解u到v的简单路径的具体应用。,例10_9 创建一个无向图，求图中从顶点u到顶点v的一条简单路径，并输出所在路径。,10.9,小结,本章主要介绍了另一种非线性的数据结构图。,图在数据结构中占据着非常重要的地位，图反映的是一种多对多的关系。,图由顶点和边（弧）构成，根据边的有向和无向可以将图分为两种：有向图和无向图。,图的存储结构有四种：邻接矩阵存储结构、邻接表存储结构、十字链表存储结构和邻接多重表存储结构。,图的遍历分为两种：广度优先遍历和深度优先遍历。,构造最小生成树的算法主要有两个：普里姆算法和库鲁斯卡尔算法。关键路径是指路径最长的路径，关键路径表示了完成工程的最短工期。最短路径是指从一个顶点到另一个顶点路径长度最小的一条路径。,