北京师范大学数据结构教学资料图市公开课金奖市赛课一等奖课件.pptx
《北京师范大学数据结构教学资料图市公开课金奖市赛课一等奖课件.pptx》由会员分享,可在线阅读,更多相关《北京师范大学数据结构教学资料图市公开课金奖市赛课一等奖课件.pptx(146页珍藏版)》请在咨信网上搜索。
1、146-146-1 1n图基本概念图基本概念n图存储表示图存储表示n图遍历与连通性图遍历与连通性 n最小生成树最小生成树n最短路径最短路径 n活动网络活动网络第八章第八章 图图第1页第1页146-146-2 2图基本概念图基本概念n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间关及顶点间关系集合构成一个数据结构:系集合构成一个数据结构:Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点有穷非空集合;是顶点有穷非空集合;E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间关系有穷集合,也叫做边是顶点之间关系有穷集合,也叫做边
2、(edge)集合。集合。Path(x,y)表示从表示从 x 到到 y 一条单向通路一条单向通路,它是有方向。它是有方向。第2页第2页146-146-3 3 n有向图与无向图有向图与无向图 在有向图中,顶点对在有向图中,顶点对 是有序。在无向图中,顶点对是有序。在无向图中,顶点对(x,y)是无序。是无序。n完全图完全图 若有若有 n 个顶点无向图有个顶点无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点有向图有个顶点有向图有n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。00001111222265433第3页第3页146-146-4 4
3、 n邻接顶点邻接顶点 假如假如(u,v)是是 E(G)中一条边,则中一条边,则称称 u 与与 v 互为邻接顶点互为邻接顶点。n子图子图 设有两个图设有两个图G(V,E)和和G(V,E)。若若V V 且且E E,则称图则称图G是图是图G子图。子图。n权权 一些图边含有与它相关数一些图边含有与它相关数,称之为权。这称之为权。这种带权图叫做网络。种带权图叫做网络。子图子图01230130123023第4页第4页146-146-5 5n顶点度顶点度 一个顶点一个顶点v度是与它相关联边条数。记度是与它相关联边条数。记作作TD(v)。在有向图中。在有向图中,顶点度等于该顶点入顶点度等于该顶点入度与出度之和
4、。度与出度之和。n顶点顶点 v 入度入度是以是以 v 为终点有向边条数为终点有向边条数,记作记作 ID(v);顶点顶点 v 出度出度是以是以 v 为始点有向边条数为始点有向边条数,记作记作 OD(v)。n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿沿一些边通过一些顶点一些边通过一些顶点 vp1,vp2,vpm,到达顶,到达顶点点vj。则称顶点序列。则称顶点序列(vi vp1 vp2.vpm vj)为从顶为从顶点点vi 到顶点到顶点 vj 路径。它通过边路径。它通过边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E边。边。第5页第5页14
5、6-146-6 6n路径长度路径长度 非带权图路径长度是指此路径上边非带权图路径长度是指此路径上边条数。带权图路径长度是指路径上各边权之和。条数。带权图路径长度是指路径上各边权之和。n简朴路径简朴路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互相重复互相重复,则称这样路径为简朴路径。则称这样路径为简朴路径。n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重叠重叠,则称这样路径为回路或环。则称这样路径为回路或环。012301230123第6页第6页146-146-7 7n连通图与连通分量连通图与连通分量 在在无向图无向图中中,若从顶
6、点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通。假如是连通。假如图中任意一对顶点都是连通图中任意一对顶点都是连通,则称此图是连通则称此图是连通图。非连通图极大连通子图叫做连通分量。图。非连通图极大连通子图叫做连通分量。n强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中,若对于若对于每一对顶点每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi路径路径,则称此图是强连通图。非强连通图极则称此图是强连通图。非强连通图极大强连通子图叫做强连通分量。大强连通子图叫做强连通分量。n生成树生成树 一个连通图生成树是其极小连通子图,一
7、个连通图生成树是其极小连通子图,在在 n 个顶点情形下,有个顶点情形下,有 n-1 条边。条边。第7页第7页146-146-8 8图抽象数据类型图抽象数据类型nclass Graph n/对象:由一个顶点非空集合和一个边集合构成n/每条边由一个顶点对来表示。npublic:n Graph();/建立一个空图n void insertVertex(const T&vertex);n /插入一个顶点vertex,该顶点暂时没有入边n void insertEdge(int v1,int v2,int weight);n /在图中插入一条边(v1,v2,w)n void removeVertex(i
8、nt v);n /在图中删除顶点v和所有关联到它边 第8页第8页146-146-9 9 void removeEdge(int v1,int v2);/在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点,则返回true,不然返回false T getWeight(int v1,int v2);/函数返回边(v1,v2)权值 int getFirstNeighbor(int v);/给出顶点 v 第一个邻接顶点位置 int getNextNeighbor(int v,int w);/给出顶点 v 某邻接顶点 w 下一个邻接顶点;第9页第9页146-146-1010图存储表示
9、图存储表示n图模板基类图模板基类 在模板类定义中数据类型参数在模板类定义中数据类型参数表表 中,中,T是顶点数据类型,是顶点数据类型,E是边上所附数据类型。是边上所附数据类型。n这个模板基类是按照最复杂情况(即带权无这个模板基类是按照最复杂情况(即带权无向图)来定义,假如需要使用非带权图,可向图)来定义,假如需要使用非带权图,可将数据类型参数表将数据类型参数表 改为改为。n假如使用是有向图,也能够对程序做相应改假如使用是有向图,也能够对程序做相应改动。动。第10页第10页146-146-11 11图模板基类图模板基类 const int maxWeight=;/无穷大值(=)const int
10、 DefaultVertices=30;/最大顶点数(=n)template class Graph /图类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点数 int getVertexPos(T vertex);/给出顶点vertex在图中位置public:第11页第11页146-146-1212 Graph(int sz=DefaultVertices);/结构函数 Graph();/析构函数 bool GraphEmpty()const/判图空否 return numEdges=0;
11、int NumberOfVertices()return numVertices;/返回当前顶点数 int NumberOfEdges()return numEdges;/返回当前边数virtual T getValue(int i);/取顶点 i 值 virtual E getWeight(int v1,int v2);/取边上权值 virtual int getFirstNeighbor(int v);/取顶点 v 第一个邻接顶点第12页第12页146-146-1313virtual int getNextNeighbor(int v,int w);/取邻接顶点 w 下一邻接顶点 virt
12、ual bool insertVertex(const T vertex);/插入一个顶点vertex virtual bool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权为cost virtual bool removeVertex(int v);/删去顶点 v 和所有与相关联边 virtual bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);第13页第13页146-146-1414邻接矩阵邻接矩阵 (Adjacency Matrix)(Adjacency Matrix)n在图邻接矩阵表示中,有一个
13、统计各个顶点在图邻接矩阵表示中,有一个统计各个顶点信息信息顶点表顶点表,尚有一个表示各个顶点之间关,尚有一个表示各个顶点之间关系系邻接矩阵邻接矩阵。n设图设图 A=(V,E)是一个有是一个有 n 个顶点图个顶点图,图邻接图邻接矩阵是一个二维数组矩阵是一个二维数组 A.edgenn,定义:,定义:第14页第14页146-146-1515n无向图邻接矩阵是对称无向图邻接矩阵是对称;n有向图邻接矩阵也许是不对称。有向图邻接矩阵也许是不对称。0123012第15页第15页146-146-1616n在有向图中在有向图中,统计第统计第 i 行行 1 个数可得顶点个数可得顶点 i 出出度度,统计第,统计第
14、j 列列 1 个数可得顶点个数可得顶点 j 入度入度。n在无向图中在无向图中,统计第统计第 i 行行(列列)1 个数可得顶点个数可得顶点i 度度。网络邻接矩阵网络邻接矩阵第16页第16页146-146-1717863129542031用邻接矩阵表示图类定义用邻接矩阵表示图类定义template class Graphmtx:public Graph friend istream&operator (istream&in,Graphmtx&G);/输入第17页第17页146-146-1818friend ostream&operator (ostream&out,Graphmtx&G);/输出p
15、rivate:T*VerticesList;/顶点表 E*Edge;/邻接矩阵int getVertexPos(T vertex)/给出顶点vertex在图中位置 for(int i=0;i=0&i=numVertices?VerticesListi:NULL;E getWeight(int v1,int v2)/取边(v1,v2)上权值 return v1!=-1&v2!=-1?Edgev1v2:0;int getFirstNeighbor(int v);/取顶点 v 第一个邻接顶点第19页第19页146-146-2020 int getNextNeighbor(int v,int w);/
16、取 v 邻接顶点 w 下一邻接顶点 bool insertVertex(const T vertex);/插入顶点vertex bool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权值为cost bool removeVertex(int v);/删去顶点 v 和所有与它相关联边 bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);第20页第20页146-146-2121template Graphmtx:Graphmtx(int sz)/结构函数 maxVertices=sz;numVertices=0;
17、numEdges=0;int i,j;VerticesList=new TmaxVertices;/创建顶点表 Edge=(int*)new int*maxVertices;for(i=0;i maxVertices;i+)Edgei=new intmaxVertices;/邻接矩阵 for(i=0;i maxVertices;i+)/矩阵初始化 for(j=0;j maxVertices;j+)Edgeij=(i=j)?0:maxWeight;第21页第21页146-146-2222template int Graphmtx:getFirstNeighbor(int v)/给出顶点位置为v第
18、一个邻接顶点位置,/假如找不到,则函数返回-1 if(v!=-1)for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;第22页第22页146-146-2323template int Graphmtx:getNextNeighbor(int v,int w)/给出顶点 v 某邻接顶点 w 下一个邻接顶点 if(v!=-1&w!=-1)for(int col=w+1;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)retu
19、rn col;return-1;第23页第23页146-146-2424n邻接表是邻接矩阵改进形式。为此需要把邻邻接表是邻接矩阵改进形式。为此需要把邻接矩阵各行分别组织为一个单链表。接矩阵各行分别组织为一个单链表。n在邻接表中,同一个顶点发出边链接在同一在邻接表中,同一个顶点发出边链接在同一个边链表中,每一个链结点代表一条边(边个边链表中,每一个链结点代表一条边(边结点),结点中有另一顶点下标结点),结点中有另一顶点下标 dest 和指针和指针 link。对于带权图,边结点中还要保留该边权。对于带权图,边结点中还要保留该边权值值cost。n顶点表第顶点表第 i 个顶点中保留该顶点数据,以及它个
20、顶点中保留该顶点数据,以及它相应边链表头指针相应边链表头指针adj。邻接表邻接表 (Adjacency List)(Adjacency List)第24页第24页146-146-2525ABCDdata adjABCD0123dest linkdest link 130210无向图邻接表无向图邻接表n统计某顶点相应边链表中结点个数,可得该顶统计某顶点相应边链表中结点个数,可得该顶点度。点度。n某条边某条边(vi,vj)在邻接表中有两个边结点,分别在邻接表中有两个边结点,分别在第在第 i 个顶点和第个顶点和第 j 个顶点相应边链表中。个顶点相应边链表中。第25页第25页146-146-2626d
21、ata adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻接表逆邻接表(入边表入边表)102 011有向图邻接表和逆邻接表有向图邻接表和逆邻接表ABC第26页第26页146-146-2727BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 (带权图带权图)邻接表邻接表n统计出边表中结点个数,得到该顶点出度;统计出边表中结点个数,得到该顶点出度;n统计入边表中结点个数,得到该顶点入度。统计入边表中结点个数,得到该
22、顶点入度。第27页第27页146-146-2828n在邻接表边链表中,各个边结点链入顺序任意,在邻接表边链表中,各个边结点链入顺序任意,视边结点输入顺序而定。视边结点输入顺序而定。n设图中有设图中有 n 个顶点,个顶点,e 条边,则用邻接表表示条边,则用邻接表表示无向图时,需要无向图时,需要 n 个顶点结点,个顶点结点,2e 个边结点;个边结点;用邻接表表示有向图时,若不考虑逆邻接表,用邻接表表示有向图时,若不考虑逆邻接表,只需只需 n 个顶点结点,个顶点结点,e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时,能够节约大量存储空间。时,能够节约大量存储空间。另外,把同一个顶点所有
23、边链接在一个单链表另外,把同一个顶点所有边链接在一个单链表中,也使得图操作更为便捷。中,也使得图操作更为便捷。第28页第28页146-146-2929用邻接表表示图类定义用邻接表表示图类定义 template struct Edge /边结点定义 int dest;/边另一顶点位置 E cost;/边上权值 Edge*link;/下一条边链指针 Edge()/结构函数 Edge(int num,E cost)/结构函数 :dest(num),weight(cost),link(NULL)bool operator!=(Edge&R)const return dest!=R.dest;/判边等否
24、;第29页第29页146-146-3030template struct Vertex /顶点定义 T data;/顶点名字Edge*adj;/边链表头指针;template class Graphlnk:public Graph /图类定义friend istream&operator (istream&in,Graphlnk&G);/输入friend ostream&operator (ostream&out,Graphlnk&G);/输出第30页第30页146-146-3131private:Vertex*NodeTable;/顶点表(各边链表头结点)int getVertexPos(c
25、onst T vertx)/给出顶点vertex在图中位置 for(int i=0;i=0&i NumVertices)?NodeTablei.data:0;E getWeight(int v1,int v2);/取边(v1,v2)权值bool insertVertex(const T&vertex);bool removeVertex(int v);bool insertEdge(int v1,int v2,E cost);bool removeEdge(int v1,int v2);int getFirstNeighbor(int v);int getNextNeighbor(int v,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京师范大学 数据结构 教学 资料 公开 金奖 市赛课 一等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。