1 图的定义
image.png
图是由顶点的有穷非空集合和顶点之间的边的集合组成, 通常表示为 : G(V,E) , G表示一个图, V是图G中顶点的集合, E是图G中边的集合。
注意点：
- 线性表中，把数据元素叫做元素， 树中， 把数据元素叫做结点， 图中的数据元素， 我们叫做顶点（Vertex）
- 线性表中, 可以没有数据元素, 称为空表, 书中可以没有结点, 叫做空树, 图中必须有顶点, 在定义中, V是顶点的集合, 我们强调顶点集合 V 有穷非空
- 在线性表中, 相邻的数据元素之间具有线性关系, 树结构中, 相邻两层的结构点具有层次关系, 图中,
任意两个顶点都有可能有关系, 顶点之间的逻辑关系称作边, 边的集合可以是空的
2 各种图的定义
无向边 : 若顶点 Vi 到 Vi 的边没有方向, 则称这条边为无向边(Edge), 用无序偶对( ViVi) 来表示。
如果图中任意两个顶点都是五向边， 则称该图为无向图，由于图是无向的， 连接顶点AD 的边， 可以写作（A,D） 也可以写作(D,A)
image.png
有向边 : 若从顶点 Vi 到Vj的边有方向, 则称作这条边为有向边, 也称作弧(Arc)。
用有序偶对 <Vi, Vj >来表示
image.png
简单图 : 在图中, 若不存在顶点到自身的边, 且同一条边不重复出现, 则称这样的图为简单图
在无向图中, 若任意两个顶点之间都存在边, 则称该图为无向完全图。
image.png
在有向图中， 如果任意两个顶点之间都存在方向互为相反的两条弧， 则称该图为有向完全图。 含有 n(n-1)条边
image.png
3 图的定义与属于总结
- 图按照 有向无向 分为有向图和无向图, 无向图由顶点和边构成, 有向图由顶点和弧构成, 弧有弧头和弧尾之分
- 图按照边或弧的多少分为稀疏图和稠密图, 如果在任意两个顶点之间都存在边, 叫完全图, 有向的就叫有向完全图, 无向的叫 无向完全图, 若无重复的边或者顶点到自身的边则叫简单图
- 图中顶点有邻接, 依附的概念, 无向图的边树叫做度。 有向图顶点分入度 和出度
- 图上的边或弧带权责称为网
- 图中顶点存在路径， 两顶点之间存在路径则说明是连通的， 如果路径最终回到起始点则称为环， 当中不重复叫简单路径。 若任意两顶点是连通的， 则称为连通图。 图中有子图， 若子图极大连通则就是连通分量， 有向的则称强连通分量。
4 图的抽象数据类型
image.png
网友评论