北京理工大学数据结构

北京理工大学数据结构

ID:36718130

大小:694.50 KB

页数:38页

时间:2019-05-10

北京理工大学数据结构_第1页
北京理工大学数据结构_第2页
北京理工大学数据结构_第3页
北京理工大学数据结构_第4页
北京理工大学数据结构_第5页
资源描述:

《北京理工大学数据结构》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第7章图第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的最小生成树7.1图的定义与术语一、图的定义1、图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中:V(G)是顶点的非空有限集E(G)是边的有限集合,边是顶点的无序对或有序对。图的分类有向图无向图37.1图的定义与术语2、有向图——有向图G是由两个集合V(G)和E(G)组成的。其中:V(G)是顶点的非空有限集。E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为,v,w是顶点,v为弧尾,w为

2、弧头。47.1图的定义与术语例如:G1=V1={A,B,C,D,E}E1={,,,,, ,}EACBD57.1图的定义与术语3、无向图——无向图G是由两个集合V(G)和E(G)组成的。其中:V(G)是顶点的非空有限集。E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)。67.1图的定义与术语例如:G2=V2={v0,v1,v2,v3,v4}E2={(v0,v1),(v0,v3

3、),(v1,v2),(v1,v4), (v2,v3),(v2,v4)}V0V4V3V1V277.1图的定义与术语例如:G2=V2={v0,v1,v2,v3}E2={,,,}V0V1V2V3例245136G1V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}87.1图的定义与术语图的应用举例例1、交通图(公路、铁路)顶点:地点边:连接地点的路例2、电路图顶点:元件边

4、:连接元件之间的线路例3、通讯线路图顶点:地点边:地点间的连线例4、各种流程图如产品的生产流程图。顶点:工序边:各道工序之间的顺序关系97.1图的定义与术语二、图的基本术语1、邻接点及关联边邻接点:边的两个顶点关联边:若边e=(v,u),则称顶点v、u关联边e2、顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中:顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n,边数为e图的所有顶点的度数和=2*e(每条边对图的所有顶点的度数和“贡献”2度)

5、V0V4V3V1V2eV0V1V2V3107.1图的定义与术语3、路径、回路无向图G=(V,E)中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…,k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。无向图G1V0V4V3V1V2路径:V0,V1,V2,V3回路:V0,V1,V2,V3,V0117.1图的定义与术语3、路径、回路有向图D=(V,E)中的顶点序列v1,v2,…,vk,若E(i=1,2,…,k-1),v=v1,u=vk,

6、则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。有向图G2V0V1V2V3路径:V0,V2,V3回路:V0,V2,V3,V0127.1图的定义与术语4、连通图(强连通图)在无(有)向图G=中,若对任何两个顶点v、u都存在从v到u的路径,则称G是连通图(强连通图)非连通图连通图强连通图非强连通图V0V1V2V3V0V2V3V1V5V4V0V4V3V1V2V0V1V2V3137.1图的定义与术语5、子图设有两个图G=(V,E),G1=(V1,E1),若V1V,E1E,而且E1关联的顶点都在V

7、1中,则称G1是G的子图;(b)、(c)都是(a)的子图(d)V4V1V2(c)V0V4V3V1V2(a)V0V4V3V1V2(b)V0V4V3V1V2147.1图的定义与术语6、连通分量(强连通分量):无(有)向图的极大(强)连通子图。极大(强)连通子图:该子图是(强)连通子图,若再将G的任何不在该子图中的顶点加入,子图就不再(强)连通。非连通图V0V2V3V1V5V4连通分量157.1图的定义与术语强连通分量V0V1V2V3非连通图V0V2V3V1167.1图的定义与术语7、生成树包含无向图G所有顶点的极小连通子

8、图称为G生成树。极小连通子图意思是:该子图是G的连通子图,在该子图中删除任何一条边,子图不再连通。G1的生成树V0V4V3V1V2章连通图G1V0V4V3V1V2连通所有顶点无回路17V0V1V2V37.2图的存储结构一、数组表示法(邻接矩阵表示)邻接矩阵:G的邻接矩阵是满足如下条件的n阶矩阵:A[i][j]=1若(vi,vj)E或

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

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

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