百度自助网站建设,昌吉州建设局网站,wordpress手机主题浮动菜单,wordpress月会员目录
前言
图的基本概念
1.什么是图#xff1f;
2 .图的相关术语
3 .有向图和无向图
4.简单图和多重图
5.连通图、强连通图、非连通图 6.权与网
7.子图和(强)连通分量 8.生成树和生成森林 前言 今天我们学习一种新的数据结构-----图#xff0c;大家在日常生活中经常都… 目录
前言
图的基本概念
1.什么是图
2 .图的相关术语
3 .有向图和无向图
4.简单图和多重图
5.连通图、强连通图、非连通图 6.权与网
7.子图和(强)连通分量 8.生成树和生成森林 前言 今天我们学习一种新的数据结构-----图大家在日常生活中经常都会跟“图”打交道比如说地图电路图等等……那我们都会发现图都有一个共同特点那就是图里面的路径是没有规律的一个地点到另一个地点的路径是不唯一的同样的在数据结构当中图也是这样子的那下面就一起进入到图的学习当中吧~
图的基本概念
1.什么是图 前面总结了“树”这种数据结构而这篇博客总结的是更为复杂的一种数据结构图graph它表明了物件与物件之间的“多对多”的一种复杂关系。图包含了两个基本元素顶点vertex, 简称V和边edge,简称E。 定义结点集合V{v1,v2,v3,v4……}和连接节点的边集合 E{e1,e2,e3,e4……}组成的二元组GV,E 称作为图graph。图中节点集合的基数n称作为图的阶数(order)。图GV,E称作为n阶图或者n,m图。 2 .图的相关术语 完全图: 任意两个点都有一条边相连 稀疏图: 有很少边或弧的图 (enlogn)稠密图:有较多边或弧的图。网:边/弧带权的图。邻接:有边/弧相连的两个顶点之间的关系 存在(vi vj)则称vi和vj;互为邻接点; 存在vi,vj则称vi邻接到vj vi邻接于vj 关联(依附): 边/弧与顶点之间的关系 存在(vi, vj)/ vi, vj 则称该边/狐关联于vi和vj 顶点的度: 与该顶点相关联的边的数目记为TD(v)在有向图中,顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以v 为终点的有向边的条数记作ID(v) 顶点 v 的出度是以 v 为始点的有向边的条数记作 OD(v) 路径:接续的边构成的顶点序列。路径长度: 路径上边或弧的数目/权值之和。回路(环): 第一个顶点和最后一个顶点相同的路径简单路径: 除路径起点和终点可以相同外其余顶点均不相同的路径 简单回路(简单环): 除路径起点和终点相同外其余顶点均不相同的路径 3 .有向图和无向图 如果给图的每条边规定一个方向那么得到的图称为有向图。在有向图中从一个顶点出发的边数称为该点的出度而指向一个顶点的边数称为该点的入度。相反边没有方向的图称为无向图。 1.有向图的写法表示
2.无向图的写法表示
4.简单图和多重图 定义含有平行边的图叫做多重图 既不含平行边又不含有自换的图叫做简单图 多重图 简单图 5.连通图、强连通图、非连通图 连通图在无向图G( V,E) )中若对任何两个顶点 v、u都存在从v 到 u 的路径则称G是连通图 强连通图在有向图G( V,E) )中若对任何两个顶点 v、u都存在从v 到 u 的路径则称G是强连通图 区分无向图满足连通性就叫做连通图有向图叫做强连通图 非连通图跟连通图反过来存在一个节点v无法到达另一个节点u的图就称作为非连通图 6.权与网 权与网 图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费 带权的图称为网 网如图所示
7.子图和(强)连通分量 子图 下图中b和c哪个是a的子图 答案c 连通分量无向图G 的极大连通子图称为G的连通分量 极大连通子图意思是: 该子图是 G 连通子图将G 的任何不在该子图中的顶点加入子图不再连通 强连通分量有向图G 的极大强连通子图称为G的强连通分量 极大强连通子图意思是: 该子图是G的强连通子图将D的任何不在该子图中的顶点加入子图不再是强连通的. 补充 极小连通子图:该子图是G 的连通子图在该子图中删除任何一条边子图不再连通 8.生成树和生成森林 生成树:包含无向图G 所有顶点的极小连通子图 生成森林:对非连通图由各个连通分量的生成树的集合 以上就是本期的全部内容了如果你学过离散数学就都学过这些的这些图论的知识点很重要的一定要会哦下一期我们就讲图的存储结构。
分享一张壁纸
