参考书籍：严蔚敏、李冬梅、吴伟民《数据结构 (C语言版) (第2版)》

因为图的相关概念太多，图的存储结构和遍历（这二者关联比较密切），以及图的应用内容也很多，所以概念就单独拎出来放一篇文章里。

一、图的定义

        图（Graph）G由两个集合V和E组成，记为G = (V, E)，其中V是顶点的有穷非空集合，E是V
中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合，边集E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。

❗注意：图不能为空图，图中必须至少有1个顶点。

        有向图：边集E(G)为有向边的集合。

        有向边：在有向图中，顶点对<x,y>是有序的，它称为从顶点x到顶点y的一条有向边。因此，<x,y>与<y,x>是不同的两条边。对<x,y>而言，x是有向边的始点，y是有向边的终点。<x,y>也称作一条弧，则x为弧头，y为弧尾。

        无向图：边集E(G)为有向边的集合。

        无向边：在无向图中，顶点对(x, y)是无序的，它称为与顶点x和顶点y相关联的一条边。这条边没有特定的方向，(x, y)与(y, x)是同一条边。为了有别于有向图，无向图的顶点对用一对圆括号括起来。

二、图的基本术语

        子图：假设有两个图G = (v, E)和G′ = (v′, E′)，如果v′⊆v且E′⊆ E，则称G′为G的子图。若满足 v'' = v，则称其为G的生成子图（生成子图包含原图的所有顶点）。       

        完全图：完全图中任意两个顶点之间都存在边。其中，对于无向图，若具有  条边，则称为无向完全图。对于有向图，若具有 n(n − 1) 条弧，则称为有向完全图。有向完全图中任意两个顶点都存在方向相反的两条弧。

        稀疏图和稠密图：有很少条边或弧（如 ）的图称为稀疏图，反之称为稠密图

        权和网：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权值。这些权值可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

        邻接点：对于无向图G，如果图的边(v, v′)∈E，则称顶点v和v′互为邻接点，即v和v′相邻接。边(v, v′)依附于顶点v和v′，或者说边(v, v′)与顶点v和v′相关联。

        度、入度和出度：顶点v的度是指和v相关联的边的数目，记为TD(v)。对于有向图，顶点v的度分为入度和出度。入度是以顶点v为头的弧的数目，记为ID(v)；出度是以顶点v为尾的弧的数目，记为OD(v)。顶点v的度为TD(v) = ID(v) + OD(v)。一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边的图，则满足：

        即，图的全部顶点之和等于边数的两倍。

1. 图（不管有向图还是无向图）的全部顶点之和等于边数的 2 倍。

2. 有向图的全部顶点的入度之和与出度之和相等，并且等于边数。因为每条有向边都有一个起点和终点。

        路径和路径长度：在无向图G中，从顶点v到顶点v′的路径是一个顶点序列。如果G是有向图，则路径也是有向的，顶点序列应满足。路径长度是一条路径上经过的边或弧的数目。

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

        简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

若一个图有 n 个顶点，且有大于 n-1 条边，则此图一定有环。

        连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v′有路径，则称v和v′是连通的。如果对于图中任意两个顶点vi,vj∈V，vi和vj都是连通的，则称G是连通图。图1.1(b)中的G2就是一个连通图，而图1.2(a)中的G3则是非连通图，但G3有3个连通分量，如图1.2(b)所示。所谓连通分量，指的是无向图中的极大连通子图。

若一个图有 n 个顶点，且有小于 n-1 条边，则此图一定是非连通图。

        强连通图和强连通分量：在有向图G中，如果对于每一对vi, vj∈V, vi ≠ vj，从vi到vj
和从vj到vi都存在路径（任意一对顶点都相互连通），则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。所谓连通分量，指的是无向图中的极大连通子图。例如，图1.1(a)中的G1不是强连通图，但它有两个强连通分量，如图1.3所示。

        连通图的生成树：一个含有图中全部顶点，但 只有足以构成一棵树的n−1条边 的 极小连通子图，这样的连通子图称为连通图的生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。

一棵有n个顶点的生成树 有且仅有 n − 1条边。如果一个图有n个顶点和小于n − 1条边，则是非连通图。如果它多于n −1条边，则一定有环。但是，有n −1条边的图不一定是生成树。

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