• 线性结构中，元素仅有线性关系，每个元素只有一个直接前驱和直接后继；
  • 树形结构中，数据元素（结点）之间有着明显的层次关系，每层上的元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；
  • 图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都可能相关。

(1) 图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

  1. 无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi，Vj) 来表示。如下左图，G= (V1,{E1})，其中顶点集合V1={A，B，C，D}; 边集合E1={ (A,B) ，（B,C），(C,D)， (D,A) , (A,C) } 。圆括号
  2. 有向边：若从顶点Vi 到Vj的边有方向，则称这条边为有向边，也称为弧。用有序偶〈Vi,Vj>来表示， Vi称为弧尾， Vj称为弧头。 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，表示弧，注意不能写成。如下右图，G= (V2,{E2})，其中顶点集合V2={A，B，C，D}; 弧集合E2={，，，}。尖括号

(2) 图的基本术语

  1. 子图：假设有两个图G= (V，{E})和G’= (V’，{E’})，如果V’是V的子集，且E’是E的子集，则称G’为G的子图。如下图带底纹的图均为左侧无向图与有向图的子图。

  2. 无向完全图和有向完全能图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n (n-1) 条边。

  3. 稀疏图和稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，这里的概念是相对而言的。

  4. 权和网：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。如下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。

  5. 邻接点：对于无向图G= (V,{E})， 如果边(v,v’)属于E， 则称顶点v和v‘互为邻接点，即v和v’相邻接、边(v,v’)依附于顶点v和v’，或者说(v,v’)与顶点v和v’相关联。

  6. 度、入度和出度：点v的度是和v相关联的边的数目，记为TD(v)。如上图左侧上方的无向图，顶点A与B互为邻接点，边(A，B) 依附于顶点A 与B 上，顶点A 的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。
    对于有向图G= (V,{E})，如果弧属于E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v的弧和顶点v， v’相关联。以顶点v为头的弧的数自称为v的入度
    ，记为ID (v); 以v为尾的弧的数目称为v的出度，记为OD (v); 顶点v的度为TD(v) =ID(v) +OD (v)。上图 左侧下方的有向图，顶点A的入度是2 (从B到A的弧，从C到A的弧)，出度是1 (从A到D的弧)，所以顶点A 的度为2+1=3。此有向图的弧有4 条，而各顶点的出度和=1+2+1+0=4，各顶点的入度和=2+0+1+1=4。

  7. 路径和路径的长度*：从顶点v 到顶点v’的路径是一个顶点序列。路径的长度是路径上的边或弧的数目。有向图的路径也是有向的。

  8. 回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环。

  9. 简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。如下图，左侧的环因第一个顶点和最后一个顶点都是B，且C、 D、 A没有重复出现，因此是一个简单环。 而右侧的环，由于顶点C的重复，它就不是简单环。

    10.连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。 如果对于图中任意两个顶点vi、vj ∈E， vi，和vj都是连通的，则称G是连通图。 下图的图1，它的顶点A到顶点B、 C、 D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、 B、 C、D相互都是连通的，所以它本身是连通图。

    无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调:

11.强连通图和强分量：在有向图G中，如果对于每一对vi，vj属于E，vi不等于vj，从vi到vj和vj 到vi都有路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

12.连通图的生成树：一个极小的连通子图， 它含有图中全部的n 个顶点，但只有足以构成一棵树的n-1条边。比如下图的图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2 或图3，就满足n个顶点n-1条边且连通的定义了， 它们都是一棵生成树。从这里也可知道，如果一个图有n 个顶点和小于n-1条边，则是非连通图，如果多于n-1 边条，必定构成一个环， 因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2 和图3，随便加哪两顶点的边都将构成环。 不过有n-1条边并不一定是生成树，比如图4。

13.有向树和生成森林：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点， 其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成， 含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 如下图的图1 是一棵有向图。去掉一些弧后，它可以分解为两棵有向树，如图2和图3，这两棵就是图1有向图的生成森林。

链接：https://www.jianshu.com/p/d9ca383e2bd8
来源：简书