数据结构 - 图的基本术语

图(Graph)概念

 图(Graph)是1种比线性表和树更加复杂的数据结构。
   线性结构：研究数据元素之间的1对1关系。除第1个和最后1个元素外，任何1个元素都有唯1的1个直接先驱和直接后继。
   树结构：是研究数据元素之间的1对多的关系。每一个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯1的1个元素相干，数据元素之间有明显的层次关系。

图结构：研究数据元素之间的多对多的关系。在这类结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相干。
图的利用极其广泛，已渗透到诸如语言学、逻辑学、物理、化学、电讯、计算机科学和数学的其它分支。

图的定义和术语

  图：是由顶点构成的有穷非空集合和顶点之间边的集合组成。通常表示为G=(V,E) 。其中：
  G：表示1个图；
  V：G中顶点(Vertex)的集合，记为V(G)；
  E：图G中边的集合，记为E(G) 。

注意点：
1、图中数据元素，称为顶点(Vertex)（线性表：元素；树：结点）
2、顶点集合有穷非空（线性表：空表；树：空树）
3、图中任意两个结点都可能有关系，顶点之间的逻辑关系用边来表示。（线性表：线性关系；树：层次关系）

无向图（Undirected graphs）

无向图（Undirected graphs）
无向边：顶点v到w之间的边没有方向。用无序偶对(v, w)表示。

无向图：图中任意两个顶点之间的边都是无向边。

在无向图中，对?(v,w)?E(G) ，有(w,v)?E(G) ，即E(G)是对称，则用 (v,w)或(w,v) 表示v和w之间的1条边便可。

有向图（Directed graphs）

有向边：顶点v到w之间的边有方向。有向边也称为弧（Arc），用有序偶对（v, w）表示。 v称为弧尾(tail)或初始点(initial node)，w称为弧头(head)或终点(terminal node) 。

有向图：图中任意两个顶点之间的边都是有向边。

完全无向图

安全有向图

有很少边或弧的图（e

图的顶点与边间关系

有向图顶点与边的关系：
顶点的邻接，对有向图G=(V ，E)，若有向弧（v,w）?E，则称
顶点v “邻接到”顶点w，
顶点w “邻接自”顶点v ，
弧（v,w） 与顶点v和w “相干联” 。
顶点的入度、出度：对有向图G=(V ，E)， ?vi ?V ，
以vi作为出发点（弧尾）的有向边(弧)的数目称为顶点vi的出度(Outdegree)，记为OD(vi) ；
以vi作为终点（弧头）的有向边(弧)的数目称为顶点vi的入度(Indegree)，记为ID(vi) 。
顶点vi的出度与入度之和称为vi的度，记为TD(vi) 。即
TD(vi)=OD(vi)+ID(vi)

路径、路径长度、回路

对无向图G=(V，E)，若从顶点v经过若干条边能到达w，称顶点v和w是连通的，又称顶点v到w有路径(Path) 。其路径是1个顶点序列
(v=vi0vi1…vim=w) ，vij?V且(vij⑴, vij)?E j=1,2, …,m
对有向图G=(V，E)，从顶点v到w有有向路径，指的是从顶点v经过若干条有向边(弧)能到达w。即
(v=vi0vi1…vim=w) ，vij?V且（vij⑴, vij）?E j=1,2, …,m

路径的长度：路径上的边或有向边(弧)的数目。
简单路径：在1条路径中，没有重复相同的顶点；
回路(环)：第1个顶点和最后1个顶点相同的路径；
简单回路(简单环)：在1个回路中，若除第1个与最后1个顶点外，其余顶点不重复出现。

连通图、连通份量

对无向图G=(V，E)，
如果对图中任两个顶点vi ，vj ?V，vi和vj都是连通的，则称图G是连通图，否则称为非连通图。
若G是非连通图，则极大的连通子图称为G的连通份量。 （如果从顶点v到w有路径，称v和w是连通的。）
对有向图G=(V，E)，
若?vi ，vj ?V， vi ≠vj都有从vi到 vj 和从vj到vi的有路径，称图G是强连通图，否则称为非强连通图。
若G是非强连通图，则极大的强连通子图称为G的强连通份量。
“极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。

生成树

生成树：1个连通图(无向图)的生成树是1个极小连通子图，它含有图中全部n个顶点和只有足以构成1棵树的n⑴条边，称为图的生成树。
关于无向图的生成树的几个结论：
1棵有n个顶点的生成树有且唯一n⑴条边；
如果1个图有n个顶点和小于n⑴条边，则是非连通图；
如果多于n⑴条边，则1定有环；
有n⑴条边的图不1定是生成树。

有向树、生成森林

有向树：只有1个顶点的入度为0 ，其余顶点的入度均为1的有向图。
生成森林：1个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

网

带权图：每一个边(或弧)都附加1个权值的图。
网或网络：带权的连通图(包括弱连通的有向图)。
网络是工程上经常使用的1个概念，用来表示1个工程或某种流程