《数据结构图》PPT课件.ppt
《《数据结构图》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据结构图》PPT课件.ppt(110页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第7章 图陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓1东普鲁士的七桥问题东普鲁士的七桥问题七桥问题的数学模型A BD C 图的应用历史w东普鲁士的七桥问题东普鲁士的七桥问题w要求从某一地出发,经过每座桥恰巧一次,最后仍要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。回到原地。w1736年欧拉将陆地作顶点,将桥作边,从而将这个年欧拉将陆地作顶点,将桥作边,从而将这个实际问题抽象成图的模型。实际问题抽象成图的模型。w“一笔划问题一笔划问题”:当两个顶点的度为偶数,其余顶:当两个顶点的度为偶数,其余顶点的度为奇数时,可以从一个偶数顶点出发,经过点的度为奇数时,可以从一个偶数顶点出发,经过每条边一次,
2、最后到达另一偶数顶点。每条边一次,最后到达另一偶数顶点。w“欧拉回路问题欧拉回路问题”:只有所有的顶点的度都是偶数,:只有所有的顶点的度都是偶数,才能从一个顶点出发,经过每条边一次,最后回这才能从一个顶点出发,经过每条边一次,最后回这个顶点。个顶点。w欧拉证明欧拉证明七桥问题无解七桥问题无解。清华大学2001设在设在4地(地(A,B,C,D)之间架设有)之间架设有6座桥,如图所示:座桥,如图所示:要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地。(1)试就以上图形说明:此问题有解的条件是什么?)试就以上图形说明:此问题有解的条件是什么?
3、(5分)分)(2)设图中的顶点数为)设图中的顶点数为n,试用试用C或或PASCAL描述与求解此问题有关描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路。(的数据结构并编写一个算法,找出满足要求的一条回路。(10分)分)本章目录w7.1图的定义和术语图的定义和术语w7.2图的存储结构图的存储结构n7.2.1数组表示法数组表示法n7.2.2邻接表邻接表(*7.2.3十字链表十字链表*7.2.4邻接多重表邻接多重表)w7.3图的遍历图的遍历n7.3.1深度优先搜索深度优先搜索n7.3.2广度优先搜索广度优先搜索w7.4图的连通性问题图的连通性问题n7.4.1图的连通分量和生成树图
4、的连通分量和生成树n7.4.2最小生成树最小生成树w7.5有向无环图及其应用有向无环图及其应用n7.5.1拓扑排序拓扑排序n*7.5.2关键路径关键路径w7.6最短路径最短路径(*7.7算法设计举例)算法设计举例)n7.6.1从某个源点到其它各顶点的最短路径从某个源点到其它各顶点的最短路径n7.6.2每一对顶点之间的最短路径每一对顶点之间的最短路径主要内容w知识点知识点n1图的定义,概念、术语及基本操作。图的定义,概念、术语及基本操作。n2图的存储结构,特别是邻接矩阵和邻接表。图的存储结构,特别是邻接矩阵和邻接表。n3图的深度优先遍历和宽度优先遍历。图的深度优先遍历和宽度优先遍历。n4图的应用
5、(连通分量,最小生成树,拓扑排序,关键路经,图的应用(连通分量,最小生成树,拓扑排序,关键路经,最短路经)。最短路经)。w重点难点重点难点n1基本概念中,完全图、连通分量、生成树和邻接点是重点。基本概念中,完全图、连通分量、生成树和邻接点是重点。n2建立图的各种存储结构的算法。建立图的各种存储结构的算法。n3图的遍历算法及其应用。图的遍历算法及其应用。n4通过遍历求出连通分量的个数,深(宽)度优先生成树。通过遍历求出连通分量的个数,深(宽)度优先生成树。n5最小生成树的生成过程。最小生成树的生成过程。n6拓扑排序的求法。关键路经的求法。拓扑排序的求法。关键路经的求法。n7最短路径的手工模拟。最
6、短路径的手工模拟。图的示例(有向图与无向图)V1V4V2V3V5V4V3V2V1结点之间的关系:多对多,任两个结点之间结点之间的关系:多对多,任两个结点之间都都可能可能有关系存在有关系存在v图图(Graph)图图G是由两个集合是由两个集合V(G)和和E(G)组成组成 的的,记为记为G=(V,E)其中:其中:V(G)V(G)是顶点的非空有限集是顶点的非空有限集 E(G)E(G)是边的有限集合,边是顶点的无序对或有序对是边的有限集合,边是顶点的无序对或有序对v有向图有向图有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成组成 V(G)V(G)是顶点的非空有限集,是顶点的非空有限集,E(
7、G)E(G)是有向边(也称弧)的有是有向边(也称弧)的有限集合,弧是顶点的有序对,记为限集合,弧是顶点的有序对,记为,vi,vjvi,vj是顶点,是顶点,vi vi为弧尾,为弧尾,vjvj为弧头为弧头v无向图无向图无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组成组成 V(G)V(G)是顶点的非空有限集,是顶点的非空有限集,E(G)E(G)是边的有限集合,边是顶是边的有限集合,边是顶 点的无序对,记为(点的无序对,记为(vi,vjvi,vj)或(或(vj,vi)vj,vi),并且(并且(vi,vjvi,vj)=()=(vj,vivj,vi)图图的概念(的概念(1)例例G1图图G1中
8、:中:V(G1)=v1,v2,v3,v4E(G1)=,G2图图G2中:中:V(G2)=v1,v2,v3,v4E(G2)=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)v1v2v3v4v1v2v3v4图的示例图的示例v有向完全图有向完全图:n n个顶点的有向图最大边数是个顶点的有向图最大边数是n(n-1)n(n-1)v无向完全图无向完全图:n n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2n(n-1)/2v邻接点邻接点:若若(vi,vjvi,vj)是是一条无向一条无向边,则称边,则称vi vi和和vjvj互为互为v关联关联:vi
9、 vi和和vjvj互为邻接点,称互为邻接点,称边边(vi,vjvi,vj)关联于顶点关联于顶点vi vi和和vjvjv顶点的度顶点的度v无向图中,顶点的度为与每个顶点相连的边数无向图中,顶点的度为与每个顶点相连的边数,记为记为D(v)v有向图中,顶点的度分成入度与出度,其中入度是以该顶有向图中,顶点的度分成入度与出度,其中入度是以该顶点为头的弧的数目,记为点为头的弧的数目,记为ID(v)。出度是以该顶点为尾的弧出度是以该顶点为尾的弧的数目的数目,记为记为OD(v)。顶点的度为入度和出度的和,即顶点的度为入度和出度的和,即D(v)=ID(v)+OD(v)。v1v3v4v2v1v2v3v4图的概念
10、(图的概念(2 2)v子图子图如果图如果图G(V,E)G(V,E)和图和图G(V,E),G(V,E),满足:满足:VV V V,EE E E 则称则称GG为为G G的子图的子图24513635621v1v3v4v2v1v3v2v3v4图的概念(图的概念(3 3)1573246路径:路径:1,2,3,5,6,3路径长度:路径长度:5简单路径:简单路径:1,2,3,5回路:回路:1,2,3,5,6,3,1简单回路:简单回路:3,5,6,3v路径是顶点的序列是顶点的序列V=Vp,ViV=Vp,Vi1 1,ViVin n,Vq,Vq,满足满足(Vp,ViVp,Vi1 1),),(ViVi1 1,Vi,
11、Vi2 2),),(ViVin n,Vq,Vq)E(G),E(G),则称则称vpvp到到vqvq存在路径存在路径.v路径长度路径长度沿路径边的数目或沿路径各边权值之和沿路径边的数目或沿路径各边权值之和.v回路回路第一个顶点和最后一个顶点相同的路径叫回路第一个顶点和最后一个顶点相同的路径叫回路v简单路径简单路径序列中顶点不重复出现的路径叫简单路径序列中顶点不重复出现的路径叫简单路径v简单回路简单回路除了第一个顶点和最后一个顶点外,其余顶点不除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫简单回路重复出现的回路叫简单回路路径:路径:1,2,5,7,6,5,2,3路径长度:路径长度:7简单
12、路径:简单路径:1,2,5,7,6回路:回路:1,2,5,7,6,5,2,1简单回路:简单回路:1,2,3,1245136图的概念(图的概念(4 4)v连通连通从顶点从顶点ViVi到顶点到顶点vjvj有一条路径,则说有一条路径,则说ViVi和和vjvj是连通的是连通的v连通图连通图图中任意两个顶点都是连通的图叫图中任意两个顶点都是连通的图叫连通图连通图v连通分量连通分量无向图中的无向图中的最大最大(含的边和顶点最多含的边和顶点最多)连通连通子子图图v强连通图强连通图有向图中,如果对每一对有向图中,如果对每一对Vi,VjVi,Vj V V,ViVi VjVj,从从ViVi到到VjVj 和从和从V
13、jVj到到 ViVi都存在路径,则称都存在路径,则称G G是是强连通图强连通图强连通图35621536强连通分量连通图245136245136非强连通图图的概念(图的概念(5 5)连通分量及强连通分量示例连通分量及强连通分量示例ABDCEFABCDEFv3v2v1G3的强连通分量的强连通分量G4及其两个连通分量及其两个连通分量v权权与图的边或弧相关的数叫与图的边或弧相关的数叫权权v网网(络)络)带权的图叫带权的图叫网网v1v2v4v5v33111024865图的概念(图的概念(6 6)w一一个个连连通通图图的的生生成成树树是是一一个个极极小小连连通通子子图图,它它含含有有图图中中全全部部顶顶点
14、点,但但只只有有足足以以构构成成一一棵棵树的树的n-1条边。条边。w一棵有一棵有n个顶点的生成树有且仅有个顶点的生成树有且仅有n-1条边。条边。图的概念(7)15732461573246连通图生成树(自由树)树或自由树或无根树w无回路的图称为树或自由树或无根树图的概念(8)w有向树:有向树:只有一个顶点的入度为只有一个顶点的入度为0,其余,其余顶点的入度为顶点的入度为1的有向图。的有向图。V1V4V2V3有向树是有向树是弱弱连通连通的的抽象数据类型图的定义ADTGraph 数据对象数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。是具有相同特性的数据元素的集合,称为顶点集。数据关系数据
15、关系R:R=VRVR=|v,w V|v,w V且且P(v,wP(v,w),表示从表示从v v到到w w的弧,的弧,谓词谓词P(v,wP(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作基本操作P:GraphCreat(G,,V,VR);GraphDestory(G);GraphLocateVertex(G,v);GraphGetVertex(G,v);GraphFirstAdj(G,v);GraphNextAdj(G,v,w);GraphInsertVertex(G,v);GraphDeleteVertex(G,v);GraphInsertArc(G,v,w);GraphDelete
16、Arc(G,v,w);DFSTtraverse(G,v,Visit();BFSTtraverse(G,v,Visit();ADTGraph图的主要操作GraphLocateVertex(G,v);GraphGetVertex(G,v);GraphFirstAdj(G,v);GraphNextAdj(G,v,w);图的存储结构:数组表示w数据结构的存储表示,既要表示数据结构的存储表示,既要表示数据元素数据元素(值),又要表示数据元素之间的(值),又要表示数据元素之间的关系关系;w图的任意两个结点(顶点)之间都可能有关图的任意两个结点(顶点)之间都可能有关系,因此用二维数组来表示;系,因此用二维数
17、组来表示;w二维数组中元素二维数组中元素aij=0表示表示vi和和vj没有关系,没有关系,即即vi和和vj不邻接不邻接(或没有(或没有vi邻接到邻接到vj)w对于网,可以用对于网,可以用aij表示表示权权。若。若vi和和vj不邻接不邻接(或没有(或没有vi邻接到邻接到vj),则可以用无限大),则可以用无限大表表示权。示权。图的存贮结构_数组表示w#define MAXNODE 64 图中顶点的最大个数图中顶点的最大个数 wtypedef char VertexType;顶点的数据类型顶点的数据类型wtypedef int EdgeType;边或弧的类型边或弧的类型wtypedef struct
18、 w VertexType vexsMAXNODE;顶点向量顶点向量w EdgeType arcsMAXNODEMAXNODE;w 邻接矩阵邻接矩阵w int vexnum,arcnum;图的顶点数和弧数图的顶点数和弧数w MGraph;图的存贮结构:邻接矩阵 若若顶顶点点只只是是编编号号信信息息,边边上上信信息息只只是是有有无无(边边),则则数组表示法可以简化为如下的邻接矩阵表示法数组表示法可以简化为如下的邻接矩阵表示法:typedef int AdjMatrixMAXNODEMAXNODE;typedef int AdjMatrixMAXNODEMAXNODE;*有有n n个顶点个顶点的图
19、的图G=(V,R)G=(V,R)的邻接矩阵为的邻接矩阵为n n阶方阵阶方阵A,A,其定其定义如下:义如下:图的存储结构:数组表示v3v2v4v1v3v2v1v1v3v2v432457图的邻接矩阵表示法的特点w对于对于无向图无向图:邻接矩阵一定是一个对称矩阵邻接矩阵一定是一个对称矩阵 行(列)非零元素个数,表示度行(列)非零元素个数,表示度 w对于对于有向图有向图:矩阵不一定是一个对称矩阵不一定是一个对称矩矩阵阵 行非零元素个数,表示出度行非零元素个数,表示出度 列非零元素个数,表示入度列非零元素个数,表示入度u邻接矩阵的存储空间只和顶点个数有关,和邻接矩阵的存储空间只和顶点个数有关,和边数无关
20、边数无关建立无向图的邻接矩阵存储结构void CreatAdjMatrix(AdjMatrixt g)/建立无向图的邻接矩阵存储结构建立无向图的邻接矩阵存储结构 int i,j,n;scanf(“%d”,&n);for(i=1;i=n;j+)for(j=1;j=n;j+)gij=0;scanf(&i,&j);while(i&j)/两顶点之一为两顶点之一为0表示结束表示结束 gij=1;gji=1;scanf(&i,&j);邻接矩阵注释若图顶点信息复杂,除用二维数组存储若图顶点信息复杂,除用二维数组存储顶点间关系的顶点间关系的邻接矩阵邻接矩阵外,还需要一个外,还需要一个具有具有n个元素的个元素的
21、一维数组一维数组存储顶点信息,存储顶点信息,其中下标其中下标i的元素存储顶点的元素存储顶点vi的信息。的信息。图的存储结构:邻接表(adjacency list)w对图中每个顶点建立一个邻接关系的对图中每个顶点建立一个邻接关系的单单链表链表,并将,并将其表头指针用向量其表头指针用向量(一维数组一维数组)存储存储,该结构称为邻接该结构称为邻接表。表。w无向图的无向图的第第i i个链表个链表将图中将图中与顶点与顶点v vi i相邻接的所有顶相邻接的所有顶点链接起来点链接起来,也就是链表中的表头结点到链表中的,也就是链表中的表头结点到链表中的每个结点表示了与表头结点每个结点表示了与表头结点vi相关的
22、边。相关的边。w有向图的有向图的第第i i个链表个链表,链接了,链接了以顶点以顶点v vi i为尾(射出)为尾(射出)的所有(射入)顶点的所有(射入)顶点,也就是链表中的表头结点到,也就是链表中的表头结点到链表中的每个结点表示了图中关联到表头结点链表中的每个结点表示了图中关联到表头结点vi的的所有弧所有弧。邻接表中的结点结构adjvexnextinfo表结点头结点firstarcdata邻接表的类型定义#define MAXNODE 64 图中顶点的最大个数图中顶点的最大个数 typedef char VertexType;顶点的数据类型顶点的数据类型typedef struct ArcNod
23、e 边表结点边表结点 int adjvex;邻接点在顶点向量中的下标邻接点在顶点向量中的下标 struct ArcNode *next;指向下一邻接点的指针指向下一邻接点的指针 InfoType *info;和弧和弧(或边或边)相关的信息指针相关的信息指针 ArcNode;typedef struct 顶点结点顶点结点 VertexType vertex;顶点信息顶点信息 ArcNode *firstarc;指向第一邻接点的指针指向第一邻接点的指针 VerNode;typedef struct VerNode verticesMAXNODE;邻接表邻接表 int vexnum,arcnum;顶
24、点和边的数目顶点和边的数目 AlGraph;邻接表示例(无向图)对于无向图,第对于无向图,第i i个顶点的度为第个顶点的度为第i i个链表的结点数个链表的结点数v3v2v4v10 v11 v22 v33 v4100022113332v3v2v10 v11 v22 v3102邻接表示例(有向图)图的存储结构:逆邻接表w若问题总对入度更关心,则可以把线性链表的若问题总对入度更关心,则可以把线性链表的表结点的数据域更改即可:由表尾改为表头:表结点的数据域更改即可:由表尾改为表头:所有以头结点为表头的弧组成的线性链表。所有以头结点为表头的弧组成的线性链表。此时该邻接表称为此时该邻接表称为逆邻接表逆邻接
25、表。v3v2v10 v11 v22 v3011建立有向图的邻接表存储结构(1)void CreatAdjList(AlGraph g)/建立有向图的邻接表存储结构建立有向图的邻接表存储结构 int n,m=0;scanf(“%d”,&n);/输入顶点个数输入顶点个数 for(i=1;iadjvex=j;p-i.firstarc;i.firstarc=p;m+;/弧的个数加弧的个数加1 scanf(&v1,&v2)/while g.vexnum=n;g.arcnum=m;/CreatAdjList十字链表:有向图另一存储结构w邻接表和逆邻接表相结合的存储结构邻接表和逆邻接表相结合的存储结构w弧结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构图 数据 结构图 PPT 课件
限制150内