欢迎来到天天文库
浏览记录
ID:28798976
大小:253.00 KB
页数:3页
时间:2018-12-14
《计算机备考资料:数据结构基本概念(七)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构:基本概念(七) Ø图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E) 其中,G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。 Ø无向图与有向图 若顶点vi和vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi,vj)来表示;若从顶点vi到vj的边有方向,则称这条边为有向边(也称为弧),用有序偶对来表示,vi称为弧尾,vj称为弧头。如果图的任意两个顶点之间的边都是无向边,则称该图为无向图,否则称该图为有向图。 Ø简单图 若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。
2、 Ø邻接、依附 在无向图中,对于任意两个顶点vi和vj,若存在边(vi,vj),则称顶点vi和vj互为邻接点,同时称边(vi,vj)依附于顶点vi和vj。 在有向图中,对于任意两个顶点vi和vj,若存在弧,则称顶点vj是vi的邻接点,同时称弧依附于顶点vi和vj。 Ø无向完全图、有向完全图 在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n×(n-1)/2条边。 在有向图中,如果任意两顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边。 Ø稠密图、稀疏图 称边数很少
3、的图为稀疏图,反之,称为稠密图。 Ø顶点的度、入度、出度 在无向图中,顶点v的度是指依附于该顶点的边的个数,记为TD(v)。在具有n个顶点e条边的无向图中,有下式成立: 在有向图中,顶点v的入度是指以该顶点为弧头的弧的个数,记为ID(v);顶点v的出度是指以该顶点为弧尾的弧的个数,记为OD(v)。在具有n个顶点e条边的有向图中,有下式成立: Ø连通图、连通分量 在无向图中,若任意顶点vi和vj(i≠j)之间有路径,则称该图是连通图。非连通图的极大连通子图称为连通分量。 Ø强连通图、强连通分量 在有向图中,对任意顶点vi和vj(i≠j),若从顶点vi到vj和从
4、顶点vj到vi均有路径,则称该有向图是强连通图。非强连通图的极大强连通子图称为强连通分量。文后寄语:book118是一个专注于电子文档的在线分享平台,用户在此平台上不但可以自由交换文档,还可以分享最新的行业资讯。book118制定了严格的文档审核策略,以保证文档来源的合法性,对有可能引起知识产权纠纷的文档,网站不予收录。同时,道客巴巴采用了行业领先的文档加密及保护技术,最大程度上保证用户上传的文档的版权不被非法侵犯。注册1、会员信息是您在book118网站的身份标识,注册后,您可以浏览文档、在线阅读或下载,建立并管理自己的文档信息库;2、打开网站的首页,点击页面上方的信息
5、条文字"【免费注册】",在用户注册页面,输入用户名、密码、电子邮件、验证码,阅读"服务协议",并选中"同意"复选框,最后点击"注册"按钮;3、也可以在"登录"页面,点击"新用户注册"按钮,进入用户注册页面;
此文档下载收益归作者所有