七、图
7.1图的定义
图( Graph)是由顶点的有穷非空集合和顶点之间边的集合组，通常表示为: G(V,E),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
- 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex）
- 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。那么对于图呢？在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
- 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
7.1.1 各种图的定义
无序对(unordered pair)一种特殊的集合.即仅含两个元素的集合.
有向图
每条边都是有方向的
无向图
每条边都是无方向的
完全图
任意两个点都有一条边相连
稀疏图
有很少边或弧的图(e <nlogn)
稠密图
有较多边或弧的图
网
边/弧带权的图
邻接
有边/弧相连的两个顶点之间的关系
存在(Vi, Vj),则称v和v:互为邻接点;
存在<Vi, Vj>,则称Vi邻接到Vj, Vj邻接于Vi;
关联(依附)
边/弧与顶点之间的关系
存在(Vi, Vj)/<Vi, Vj>，则称该边/弧关联于Vi和Vj;
顶点的度
与该顶点相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度与出度之和。
顶点V的入度是以v为终点的有向边的条数,记作ID(v)
顶点v的出度是以V为始点的有向边的条数，记作OD(v)
看实例：
当有向图中仅1个顶点的入度为0,其余顶点的入度均为1,此时是何形状?是树!而且是一棵有向树!
路径
若干条边构造的顶点序列
路径长度
路径上边或弧的数目/权值之和
如果没有权值，上图这个路径的长度就是2
如果边有权值，那么边上的权值相加就是路径长度
回路(环)
第一个顶点和最后一个顶点相同的路径
简单路径
除路径起点和终点可以相同外，其余顶点均不相同的路径
简单回路(简单环)
除路径起点和终点相同外，其余顶点均不相同的路径。
连通图(强连通图)
在无(有)向图G=(V, {E} )中，若对任何两个顶点v、u都存在从V到u的路径，则称G是连通图(强连通图)
从图中能很明白的看出各个概念之间的差异
这里不多解释
子图
如上，可以轻松看出图b和图c都是图a的子图
连通分量
无向图G的极大连通子图称为G的连通分量。
极大连通子图是指顶点的个数已经是最大的了，在添加顶点的话子图不能形成连通了
强连通分量
有向图G的极大强连通子图称为G的强连通分量。
极大强连通子图意思是:该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。
极小连通子图
该子图是G的连通子图，在该子图中删除任何一条边子图不在连通
极小连通子图可以包含所有顶点，也可以不包含所有顶点
生成树
包含无向图G所有顶点的极小连通子图
生成森林
对非连通图，由各个连通分量的生成树的集合
7.1.2图的定义与术语总结
图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图
图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
图上的边或弧上带权则称为网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若千棵有向树构成生成森林。
