数据结构-7 图

《数据结构-7 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、井冈山大学计算机科学系井冈山大学计算机科学系冷明冷明lengming@jgsu.edu.cnlengming@jgsu.edu.cn课前思考：前2-6章我们讲了哪些数据结构?非线性结构线性数组树栈队列串表二叉树n个元仅在表尾一端插入零个或者线性表中进行插入另一端删多个字符分支关系素的有的元素本和删除的除的线性组成的序定义的层身也是一限序列线性表表列种结构次结构结点间具有唯一前驱、唯一后继关系一对多结点之间是一对一的关系的关系非线性结构(树)来描述该家族谱系关系爷爷大伯叔叔父亲堂兄堂姐哥哥自己妹妹∑数据元素之间有着明显的层次关系∑每一层的数据元素可能和下一层中多个元素相关：每个父亲可

2、以有多个子女∑每一层的数据元素只能和上一层中一个元素相关：每个人只有一个父亲非线性结构(树)来描述该电路？非线性结构-图∑数据元素之间没有层次关系∑数据元素之间的关系可以是任意的：任意两个数据元素之间都可能相关7.1图的基本概念¾图的定义图(graph)是由一个非空的顶点集合和一个描述顶点之间多对多关系的边集合组成的非线性数据结构G=(V,E)图G的顶点集合和边集合分别记为V(G)和E(G)∑V(G)={v

3、v∈某个数据对象集}:它是顶点的有穷非空集合∑E(G)={

4、v,w∈V且P(v,w)}:它是顶点之间关系的有穷集合，也叫边集合，其中P(v,w)表示从v到w的一条单向

5、通路7.17.1图的定义和术语图的定义和术语¾图的应用举例例2电路∑顶点:元件例1交通图（公路、铁路）∑边:连接元件之间的线路∑顶点:地点∑边:连接地点的公路例3通讯线路图∑交通图中单行道双行道，∑顶点:地点用有向边、无向边表示∑边:地点间的连线V0V1V0V1例4产品的生产流程图V2∑顶点:工序V3V4V2V3∑边:各道工序之间的顺序关系7.17.1图的定义和术语图的定义和术语¾有向图若图G中的每条边都是有方向的，则称G为有向图在有向图中，一条有向边是由两个顶点组成的有序对∑有序对用尖括号表示:表示一条由v到v的有向边ijij∑弧:有向边∑弧的始点v：弧尾i∑弧的终点v

6、:弧头j7.17.1图的定义和术语图的定义和术语¾有向图的应用举例v1v2G有序对：1用以为vi起点、以vj为终点的有向线段表示，称为弧v3v4有向图G的顶点集和边集分别为1∑顶点集V（G）:{v，v，v，v}11234∑边集E（G）:{，，，}1121324327.17.1图的定义和术语图的定义和术语¾无向图若∈E(G),必有∈E(G)若图G中的每条边都满足上述条件，则称之为无向图无向图中的边均是顶点的无序对，通常用圆括号表示。∑(v，w):表示v和w之间的无向边7.17.1图的定义和术语图的定义和术语¾无

7、向图的应用举例v1v2无序对(vi,vj)：G2v3用连接顶点vi、vj的线段表示，称为无向边v4v5无向图G的顶点集和边集分别为2∑顶点集V（G）:{v，v，v，v，v}212345∑边集E（G）:{（v，v），（v，v），（v，v），（v，v），2l2131423（v，v），（v，v）}25457.17.1图的定义和术语图的定义和术语¾在以后图的相关讨论中，约定∑一条边中涉及的两个顶点必须不相同：若（v，v）或ij是E（G）中的一条边，则要求v≠vijij∑无向图：一对顶点间不能有两条无向边∑有向图：一对顶点间不能有相同方向的两条有向边∑用n表示图中顶点数目;用e表示

8、图中边数7.17.1图的定义和术语图的定义和术语在n个顶点的无向完全图中，边的条数为n(n-1)/2。证明：在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。证毕。7.17.1图的定义和术语图的定义和术语¾完全图对一个具有n个顶点的无向图，其边数e≤n（n-1）/2V若e=n（n-1）/2，则该无向图称为无向完全图对一个具有n个顶点的有向图，其边数e≤n（n-1）V若e=n（n-1），则该有向图称

9、为有向完全图7.17.1图的定义和术语图的定义和术语¾完全图的应用举例G3v1G4v1v2v3v2v3v4v4无向完全图G有向完全图G34∑4个顶点:{v，v，v，v}∑4个顶点:{v，v，v，v}12341234∑6条边:n（n-1）/2∑12条边:n（n-1）7.17.1图的定义和术语图的定义和术语G3v1¾顶点的度v2v3v4对于无向图G∑若（v，v）是一条无向边，则称顶点v和v互为邻接点ijij∑边（v，v）依附于顶点v和vijij∑边（v，v）和顶点v、v相