数据结构(C语言版)第7章图.ppt

《数据结构(C语言版)第7章图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、图的基本概念；2、图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（kruskul算法、prim算法）；5、最短路径（dijkstra算法、floyd算法）；6、AOV网络与拓扑排序；7、AOE网络与关键路径。教学内容图的特点顶点的前驱和后继个数无限制图的应用顶点之间的关系是任意的图中任意两个顶点之间都可能相关图（Graph）是一种非线性结构。语言学逻辑学物理化学电信工程数学计算机科学多对多北京西安南京杭州开封洛阳7.1图的定义和术语定义：图

2、是一种：数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型。ADTGraph{数据对象：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R={VR}VR={

3、v,w∈V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：定义：图(Graph)是一种复杂的非线性数据结构，由顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为：G＝(V,{VR})其中V是顶点的有穷非空集合；VR是顶点之间关系的有穷集合，也叫做弧或边集合。

4、弧是顶点的有序对，边是顶点的无序对。基本操作：{结构初始化}CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。{销毁结构}DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。{引用型操作}LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在和u相同的顶点，则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回

5、v的值。FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接点。若该顶点在G中没有邻接点，则返回“空”。顶点在图中的“位置”指的是，在图的存储结构中顶点之间自然形成的相对位置。若∈G，则称w为v的邻接点，若(v,w)∈G，则称w和v互为邻接点。NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。若v有多个邻接点，则在图的存储结

6、构建立之后，其邻接点之间的相对次序也就自然形成了。{加工型操作}PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧，若G是无向的，

7、则还增添对称弧。DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse(G,Visit());初始条件：图G存在，Visit是顶点的访问函数。操作结果：对图G进行深度优先遍历。遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,Visit());初始条件：图G存在，Visit是顶点的访问函数。操作结果：对图G进行广度

8、优先遍历。遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraph基本术语：有向图无向图顶点：图中的数据元素。v2v1v3v4G1v2v1v3v4v5G2弧：若∈VR，则表示从v到w的一条弧，且称v为弧尾，称w为弧头，此时的图称为有向图。G1=(V1,{A1})V1={v1,v2,v3,v4}A1={,,,}边：若∈VR必有∈VR，则以无序对(v,w)代表这两个有

9、序对，表示v和w之间的一条边，此时的图称为无向图。G2=(V2,{E2})V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}例：两个城市A和B，如果A和B之间的连线的涵义是表示两个城市的距离，则和是相同的，用(A,B)表示。如果A和B之间的连线的涵义是表示两城市之间人口流动的情况，则和