1. 图的概念
1.1 图的定义:
图是一个由顶点集合 V 和一个弧集 R 构成的数据结构.
ADT Graph {? 数据对象 V:V 是具有相同特性的数据元素的集合, 称为顶点集.? 数据关系 R:?R = {VR}?VR = {<v,w>|v,wV 且 P(v,w),<v,w > 表示从 v 到 w 的弧,
谓词 P(v,w)定义了 < v,w > 的意义或信息}
1.2 图的重要术语
(1)无向图: 在一个图中, 如果任意两个顶点构成的偶对(v,w)∈E 是无序的, 即顶点之间的连线是没有方向的, 则称该图为无向图.
(2)有向图: 在一个图中, 如果任意两个顶点构成的偶对(v,w)∈E 是有序的, 即顶 点之间的连线是有方向的, 则称该图为有向图.
(3)无向完全图: 在一个无向图中, 如果任意两顶点都有一条直接边相连接, 则称该图 为无向完全图. 在一个含有 n 个顶点的无向完全图中, 有 n(n-1)/2 条边.
(4)有向完全图: 在一个有向图中, 如果任意两顶点之间都有方向互为相反的两条弧相 连接, 则称该图为有向完全图. 在一个含有 n 个顶点的有向完全图中, 有 n(n-1)条边.
(5)稠密图, 稀疏图: 若一个图接近完全图, 称为稠密图; 称边数很少 (e<nlogn) 的图为稀疏图.
(6)顶点的度, 入度, 出度: 顶点的度 (degree) 是指依附于某顶点 v 的边数, 通常记为 TD (v). 在有向图中, 要区别顶点的入度与出度的概念. 顶点 v 的入度是指以顶点为终点的弧的 数目, 记为 ID (v); 顶点 v 出度是指以顶点 v 为始点的弧的数目, 记为 OD (v). TD (v)=ID (v)+OD (v). 可以证明, 对于具有 n 个顶点, e 条边的图, 顶点 vi 的度 TD (vi)与顶点的个数以及边的 数目满足关系:
(()
(7)边的权, 网图: 与边有关的数据信息称为权(weight). 在实际应用中, 权值可以有 某种含义. 边上带权的图称为网图或网络(network). 如果边是有方向的带权图, 则就是一 个有向网图.
(8)路径, 路径长度: 顶点 vp 到顶点 vq 之间的路径 (path) 是指顶点序列 vp,vi1,vi2, ..., VIM,vq.. 其中,(vp,vi1),(vi1,vi2),...,(VIM,.vq)分别为图中的边. 路径上边的数目称为路径长度.
(9)简单路径, 简单回路: 序列中顶点不重复出现的路径称为简单路径. 除第一个顶点 与后一个顶点之外, 其他顶点不重复出现的回路称为简单回路, 或者简单环.
(10)子图: 对于图 G=(V,E),G'=(V',E'), 若存在 V'是 V 的子集 ,E'是 E 的子 集, 则称图 G'是 G 的一个子图.
(11)连通图, 连通分量: 在无向图中, 如果从一个顶点 vi 到另一个顶点 vj(i≠j)有路径, 则称顶点 vi 和 vj 是连通的. 如果图中任意两顶点都是连通的, 则称该图是连通图. 无向图的 极大连通子图称为连通分量.
(12)强连通图, 强连通分量: 对于有向图来说, 若图中任意一对顶点 vi 和 vj(i≠j)均有 从一个顶点 vi 到另一个顶点 vj 有路径, 也有从 vj 到 vi 的路径, 则称该有向图是强连通图. 有 向图的极大强连通子图称为强连通分量.
(13)生成树: 所谓连通图 G 的生成树, 是 G 的包含其全部 n 个顶点的一个极小连通子 图. 它必定包含且仅包含 G 的 n-1 条边. 在生成树中添加任意一条属于原图中的边必定会产 生回路, 因为新添加的边使其所依附的两个顶点之间有了第二条路径. 若生成树中减少任意 一条边, 则必然成为非连通的.
(14)生成森林: 在非连通图中, 由每个连通分量都可得到一个极小连通子图, 即一棵 生成树. 这些连通分量的生成树就组成了一个非连通图的生成森林.
2. 图的存储及基本操作
来源: http://www.bubuko.com/infodetail-2948915.html