软件开发技术--数据结构四-图.ppt
- 文档编号:4724979
- 上传时间:2023-05-07
- 格式:PPT
- 页数:19
- 大小:2.14MB
软件开发技术--数据结构四-图.ppt
《软件开发技术--数据结构四-图.ppt》由会员分享,可在线阅读,更多相关《软件开发技术--数据结构四-图.ppt(19页珍藏版)》请在冰点文库上搜索。
第三章数据结构,(四)图,图,树的局限性:
树只能表示层次关系。
例如在图中,任何两个数据元素之间都可能存在关系。
定义,简单图G=(V,E)是由非空顶点集合V和可空边集合E组成。
边是顶点的有序对(有向图中的边)或无序对(简单图,即无向图中的边)。
例:
图中顶点的集合为V(G)=v1,v2,v3,v4,v5,边的集合为E(G)=(v1,v2),(v1,v3),(v1,v4),(v2,v3),图的复杂程度,图的基本概念,无向图G=(V,E)中,如果(vi,vj)是E中的一条边,则称顶点vi和vj互为邻接点。
与顶点v相关联的边的数目称为顶点v的度。
v1到vn的路径(Path):
在一个图中,若从顶点v1出发,沿一些边经过顶点v2,v3,vn-1到达顶点vn,则称顶点序列(v1,v2,v3,.,vn-1,vn)是v1到vn的路径。
图的存储邻接矩阵表示法,邻接矩阵中的元素:
邻接矩阵表示法优点:
插入/删除顶点方便:
插入一个顶点,只需要将对应的一个矩阵元素由0改为1.顶点的度计算简单:
无向图中每个顶点的度就等于邻接矩阵中该顶点所在行或列的非零元素的个数。
邻接矩阵用二维数组存储。
如果Vi和Vj之间存在边。
如果Vi和Vj之间没有边。
邻接矩阵例子,图的遍历,从图中某一顶点出发访问图中的所有顶点,且使每个顶点仅被访问一次,这一过程称为图的遍历。
根据搜索策略的不同,图的遍历方法有两种:
深度优先遍历:
采用深度优先搜索(DeepFirstSearch,DFS)算法进行图的遍历,称为图的深度优先遍历。
广度优先遍历:
采用广度优先搜索(BroadFirstSearch,BFS)算法进行图的遍历,称为图的广度优先遍历。
DFS与BFS,深度优先搜索(DFS)算法是尽可能“深”地搜索图。
在该算法中先访问初始顶点v,再访问与顶点v邻接的未访问的顶点。
如果顶点v没有邻接顶点,或它的邻接顶点都已访问过,则回溯到顶点v的前驱顶点。
如果回溯到遍历开始的第一个顶点,则遍历结束。
如果图中仍有未访问过的顶点,遍历将继续从未访问的一个顶点重新开始。
广度优先搜索(BFS)与DFS类似,只是尽可能“宽”地搜索图。
从图中某个顶点v出发,访问v后在依次访问与v邻接的各个未访问顶点,;再依次从这些顶点出发访问与其邻接的但未访问过的顶点,直到到所有邻接的顶点均被访问过为止。
如果图中尚有顶点未被访问,则遍历将继续从未访问过的一个顶点重新开始。
深度优先遍历示例,深度优先遍历vs.广度优先遍历,vs.,深度优先遍历顺序:
A,B,D,F,E,C,G.广度优先遍历顺序:
A,B,C,E,D,F,G.,图的广度优先遍历,使用一个队列。
实现遍历的处理过程如下:
1.把队列置空。
2.访问出发顶点,置该顶点已被访问的标志。
3.让出发顶点进队。
4.若队列不空,则:
(a)取出队首中的顶点v。
(b)在邻接矩阵中,依次取得与顶点v邻接的各个顶点。
(1)若当前取得的邻接顶点未被访问,置该顶点已被访问的标志。
该顶点进队。
(2)取得下一个邻接顶点,转
(1)(c)转45.若队列空,则处理过程结束。
实现过程,图类的定义,publicclassGraphprivateint,data;/存放邻接矩阵的数据privateintdimension;/图中的点数privatestringresult;publicGraph(int,data)this.data=data;this.dimension=data.GetLength(0);,类文件graph.cs,图的广度优先遍历代码,privatestringbfs(intstartVertex,boolvisited)intj,k;Queuelq=newQueue();/生成一个队列lq.Enqueue(startVertex);/将起始顶点放入队列while(lq.Count!
=0)/判断队列是否为空k=Convert.ToInt32(lq.Dequeue();/从队列中取出队首元素,放到k中visitedk=true;/设置该顶点被访问过this.result+=“”+(k+1);/输出该顶点for(j=0;jthis.dimension;j+)/将于该顶点邻接的所有未被访问过的顶点全部放入队列中if(datak,j!
=0,图的广度优先遍历代码,publicstringbroadFirst()this.result=“”:
/每次遍历前,把遍历的结果先初始化boolvisited;visited=newboolthis.dimension;for(inti=0;ithis.dimension;i+)visitedi=false;for(i=0;ithis.dimension;i+)if(!
visitedi)/找到一个未被访问的顶点作为起点,进行广度优先搜索bfs(i,visited);returnthis.result;,图类测试主窗体及编码,一、主窗体设计如图,图类测试主窗体及编码,privatevoidbutton1_Click(objectsender,EventArgse)int,data=Graph.LoadData(textBox1.Text);/LoadData方法的代码请参见教材P68gr=newGraph(data,data.GetLength(0);/data.GetLength(0)获得数组第一维的长度privatevoidbutton2_Click(objectsender,EventArgse)textBox2.Text=gr.deepFirst();/gr是在窗体类中定义的。
二、主窗体代码读文件和遍历按钮,深度优先遍历算法,递归算法privatevoiddfs(intstartVertex,boolvisited)intj;result+=+(startVertex+1);visitedstartVertex=true;for(j=0;jthis.dimension;j+)if(datastartVertex,j!
=0,深度优先遍历算法,publicstringdeepFirst()this.result=;boolvisited=newboolthis.dimension;for(inti=0;ithis.dimension;i+)visitedi=false;for(inti=0;ithis.dimension;i+)if(!
visitedi)dfs(i,visited);returnthis.result;,作业,实现本节书中例子注意:
ArrayList类和Queue类是C#提供的数据结构。
在System.Collections命名空间中。
因此,使用前必须引用该命名空间。
UsingSystem.Collections;,Queue类,入队:
采用Enqueue方法出队:
采用Dequeue方法具体实例见第12页PPT。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件 开发 技术 数据结构
![提示](https://static.bingdoc.com/images/bang_tan.gif)