《图定义和基本术语.docx》由会员分享，可在线阅读，更多相关《图定义和基本术语.docx（18页珍藏版）》请在金锄头文库上搜索。
1、图定义和基本术语(精)程序设计算法篇图图的遍历算法及其应用 / 目录第 6 章 图 .2图的定义和基本术语 .2图的储藏和创办 .3图的储藏表示 .3图的创办 .6图的遍历 .6深度优先搜寻 .6广度优先搜寻 .7遍历算法的应用 .8应用问题归纳 .8求一条包含图中所有极点的简单路径. 9求距 v0 最短路径长度最长的一个极点. 10图的连通性问题 .11无向图的连通重量和生成树.11最小生成树 .13有向无环图及其应用 .13文档编号完成时间第 1 页完 成 人张昱更正时间程序设计算法篇第6章图图图的遍历算法及其应用图的定义和基本术语1、图的特色任意两个数据元素之间都可能相关。结点之间的关系
2、是多对多的。G = (V, E)2、基本术语结点：极点结点间的关系 ：无向图 ：边 (v,w)，v 与 w 互为毗邻点，边 (v,w)依靠于极点 v,w，边 (v,w)和极点 v,w 相关系v 的度：和v 相关系的边的数目。有向图 ：弧 ，v 弧尾， w 弧头，极点 v 毗邻到极点 w，极点 w 毗邻自极点 v，弧 和极点 v,w 相关系。v 的入度：以v 为头的弧的数目；v 的出度：以v 为尾的弧的数目；v 的度： v 的入度与出度之和。路径、回路 (环 )、简单路径、简单回路(简单环 )连通性 ：若从极点 v 到极点 v有路径，则称 v 和 v是连通的图的规模 ：极点数 n、边 (弧 )数
3、 e、极点的度 (有向图：入度 /出度 )子图 ： G=V(,E), G = (V, E) ，若 V V 且 E E，则称 G是 G 的子图。图的分类 ：1）关系的方向性（无向/有向）、关系上可否有附加的数权(图 /网 )有向图、无向图、有向网、无向网2）边 (弧 )数：完好图 (边数 =n(n-1)/2 的无向图 )、有向完好图(弧数 =n(n-1) 的有向图 )稀罕图 (enlog n)3）连通性：无向图 ：连通图 (任意两极点都是连通的 )、连通重量 (极大连通子图 )、生成树 (极小连通子图 )、生成森林有向图 ：强 /弱连通图、强连通重量、生成树(极小连通子图)、生成森林3、抽象数据
4、种类定义ADT Graph 数据对象V ： V 是拥有相同特色的数据元素的会集，称为极点集。数据关系R：R = VRVR = |v,wV 且 P(v,w) ， 表示从 v 到 w 的弧，谓词 P(v,w)定义了弧 的意义或信息基本操作 ：CreateGraph(&G , V, VR)初始条件： V 是图的极点集，VR 是图中弧的会集操作结果：按V 和 VR 的定义构造图GDestroyGraph(&G)初始条件：图G 存在操作结果：销毁图GLocateVex(G,u)初始条件：图G 已存在， u 和 G 中极点有相同特色文档编号完成时间第 2 页完 成 人张昱更正时间程序设计算法篇图图的遍历算
5、法及其应用操作结果：若 G 中存在极点 u，则返回该极点在图中地址，否则返回其他信息GetVex(G, v)初始条件：图G 存在， v 是 G 中某个极点操作结果：返回v 的值PutVex(&G , v, value)初始条件：图G 存在， v 是 G 中某个极点操作结果：对v 赋值 valueFirstAdjVex(G , v)初始条件：图G 存在， v 是 G 中某个极点操作结果：返回 v 的第一个毗邻极点。若极点在 G 中没有毗邻极点，则返回“空”NextAdjVex(G , v, w)初始条件：图G 存在， v 是 G 中某个极点， w 是 v 的毗邻极点操作结果：返回v 的 (有对于
6、 w 的 )下一个毗邻极点。若w 是 v 的最后一个毗邻点，则返回“空”InsertVex(&G , v)初始条件：图G 存在， v 和 G 中极点有相同特色操作结果：在图中增添新极点vDeleteVex(&G , v)初始条件：图G 存在， v 是 G 中某个极点操作结果：删除G 中极点 v 及其相关的弧InsertArc(&G , v, w)初始条件：图G 存在， v 和 w 是 G 中两个极点操作结果：在图G 中增添弧 ，若 G 是无向的，则还应增添对称弧DeleteArc(&G , v, w)初始条件：图G 存在， v 和 w 是 G 中两个极点操作结果：删除G 中的弧 ，若 G 是无
7、向的，则还应删除对称弧DFSTraverse(G , v, visit()初始条件：图G 存在， v 是 G 中某个极点， visit 是对极点的应用函数操作结果： 从极点 v 起深度优先遍历图G，并对每个极点调用函数visit()一次且至多一次。一旦visit() 失败，则操作失败BFSTraverse(G , v, visit()初始条件：图G 存在， v 是 G 中某个极点， visit 是对极点的应用函数操作结果： 从极点 v 起广度优先遍历图G，并对每个极点调用函数visit()一次且至多一次。一旦visit() 失败，则操作失败 ADT Graph图的储藏和创办图的储藏表示1、图的储藏表示解析极点之间的关系是多对多的 (m:n) ，由于 m 和 n 都是不定的， 无法给出一个这种多对多的关系向线性关系的照射公式图中的关系不能够经过 次序映像 (即经过极点之间的储藏地址反响极点之间的逻辑关系)反映；必定别的引入储藏空间反响极点之间的毗邻关系。文档编号完成时间第 3页完成人张昱更正时间程序设计算法篇图图的遍历算法及其应用图的储藏构造：1）极点信息；2）边 (弧 ) 信息； 3）整体信息：极点数、边(弧 )数、图
