《数据结构》课件(c语言)第07章

《数据结构》课件(c语言)第07章

ID:40004972

大小:1.20 MB

页数:117页

时间:2019-07-17

《数据结构》课件(c语言)第07章_第1页
《数据结构》课件(c语言)第07章_第2页
《数据结构》课件(c语言)第07章_第3页
《数据结构》课件(c语言)第07章_第4页
《数据结构》课件(c语言)第07章_第5页
资源描述:

《《数据结构》课件(c语言)第07章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《数据结构》第七章图(重点)主要内容•图的概念•图的存储结构数组表示法——邻接矩阵邻接表表示法十字链表表示法邻接多重表表示法•图的遍历深度优先搜索广度优先搜索2主要内容•图的连通性问题无向图的连通分量和生成树构造最小生成树的Prim算法构造最小生成树的Kruskal算法•有向无环图•拓扑排序•关健路径•最短路径3第七章图内容和要求图及其有关的基本概念、图的存储结构及其图的遍历,最短路径、拓扑排序的关健路径,动态存储管理。要求获得有关图结构及其应用方面的初步知识和经验。理解图及其有关的基本概念,图的存储方法,熟悉遍历图的深度优先(DFS)和广度优

2、先(BFS)的搜索算法,了解最短路径、拓扑排序、关健路径的方法及算法的基本思想。重点图的三种常用的存储表示,DFS法和BFS法。难点是图的邻接多重存储表示,DFS法和BFS法,最短路径。4什么是图图形结构是一种较线性表结构和树形结构更为复杂的非线性数据结构。在人工智能、工程、数学、物理、化学、计算机科学等学科领域中,图形结构均有着广泛的应用。线性表结构:数据元素即结点之间仅有线性关系。树形结构:数据元素之间具有明显的层次关系。每层中的结点可允许有若干个孩子结点,但仅允许有一个双亲结点(前趋)。图形结构:数据元素之间的关系是任意的,图中任意两个结

3、点之间都可能相关。事实上,树形结构是图形结构的一种特殊情况。图的概念5图常用来解决的几类主要问题1.模拟计算机与通信网络的联接;2.表示一张地图的一组坐标以及坐标之间的距离,以求得最短路径;3.模拟交通网络的流量;4.寻找从开始状态到目标状态的路径,如人工智能问题求解;5.模拟计算机算法,显示程序状态的变化;6.为复杂活动各子任务的完成寻找顺序,如大型建筑的建造;…………图的概念6定义:图是一种数据结构,它的形式化定义为Graph=(V,R)其中V={x

4、x∈dataobject}R={VR}VR={<x,y>

5、P(x,y)∧(x,y∈V)

6、}可以简记为G=(V,E)其中V是顶点的有穷非空集合,E是V中顶点的偶对(称为边)的有穷集。通常亦可将图G的顶点集和边集分别记作V(G)和E(G)。若E(G)为空集,则表示图G仅有顶点而没有边。图的定义7示例1有向图G1和无向图G2G1G2图的定义V(G1)={v1,v2,v3,v4}E(G1)={,,,}V(G2)={v1,v2,v3,v4,v5}E(G2)={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}V1V2V3V4V1V2V4

7、V5V38顶点:图中的数据元素。弧:有向边,用以尖括号括起来的有序对表示。弧尾:有向边的始点vi。弧头:有向边的终点vj。有向图:图G中每条边都是有向边(弧)。无向图:图G中每条边都是没有方向的,这些边用以(vi,vj)形式的无序对表示。图的术语V1V2V3V4V1V2V4V5V39图的顶点数n和边数e的关系:对有向图,0≤e≤n(n-1);对无向图,。有向完全图:恰有n(n-1)条有向边(即弧)的有向图。无向完全图:恰有条无向边的无向图。稀疏图:图中边或弧的数目e<

8、≈n2(准确地说,无向图的e接近于,有向图的e接近于n(n-1)。图的术语V1V2V3V4V1V2V4V5V310子图:设有两个图G=(V,E)和G`=(V`,E`),如果V`V,E`E,则称G`为G的子图。邻接点:若无向边(v,v`)∈E,则称顶点v和v`互为邻接点。关联:称无向边(v,v`)与顶点v和v`相关联。顶点V的度:与v相关联的边的数目,记为TD(v)。顶点V的入度:有向图中,以顶点V为弧头(即终端点)的弧的数目,记为ID(V)。顶点V的出度:有向图中,以顶点V为弧尾(即初始点)的弧的数目,记为OD(V)。示例2有向图G1:顶点数

9、目n=4;有向边或弧的数目e=4;ID(V1)=1,OD(V1)=2,TD(V1)=3。无向图G2:顶点数目n=5;无向边的数目e=6;TD(V1)=2。注.一个有n个顶点,e条边或弧的图,有:图的术语V1V2V3V4G1V1V2V4V5V3G211路径:图G中由顶点V到V`的路径是一个顶点序列V=Vi0,Vi1,···,Vim=V`,其中(Vij-1,Vij)∈E,1≤j≤m。若图G是个有向图,则由顶点V到V`的路径亦是有向的,它由E(G)中的有向边∈E,1≤j≤m组成。路径的长度:图G中由顶点V到V`的路径长度是指在

10、该路径上的边或弧的数目。简单路径:若图G中由顶点V到V`的一条路径上,除了V和V`可以相同外,其余顶点均不相同,则称此路径为一条简单路径。简单回路:起

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。