计算机备考资料：数据结构基本概念(七)

《计算机备考资料：数据结构基本概念(七)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、也可以在"登录"页面，点击"新用户注册"按钮，进入用户注册页面;