图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E）,其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图是一种较线性表和树更加复杂的数据结构。 在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
其中我们要明确的几个地方：
线性表中我们把数据元素叫做元素，树中将数据元素叫结点，在图中，数据元素我们称之为顶点（Vertex）线性表中可以没有数据元素，称为空表。树中没有可以没有结点，叫做空树。那么对于图中则不能没有顶点，在图的定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。 图1.无向图
如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。 图2.有向图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。我们要学习的主要就是简单图，类似有向图无向图都属于简单图。
来看一张不是简单图的示例：
图3.非简单图
在无向图中，如果任意两个顶点之间的都存在边，则称该图为无向完全图。 其中有一条性质，n个顶点的无向完全图有n*(n-1)/2条边。
图4.完全无向图
有很少条边或弧的图称为稀疏图，反之称为稠密图。
这里的稀疏和稠密是模糊的概念，都是相对而言的。比如我去上海世博会那天，参观的人数差不多50万人，我个人感觉人数实在太多，可以用稠密来形容，可后来听说，世博园里人数最多的一天达到了100万人，所以，对于50万人来说是多么稀疏吖。
带权的图通常称为网（Network）。
图5.网
权是什么?文章后面有定义，请往后看。
在无向图G中，如果从顶点v到顶点v’有路径，则称v和v‘是连通的。如果对于图中任意两个点vi、vj ∈V，vi和vj都是连通的，则称G是连通图（Connected Graph）。（∈数学符号，属于集合的意思） 这个概念很大，类似于抽象提层，和我们说的稠密和稀疏图一样，是一种更高级别的叫法。 来两张图我们看看： 图6.连通图 图7.非连通图 ，A与E或F无路径。
在有向图G中，如果对于每一对Vi,Vj ∈V、Vi≠Vj，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。 一张图认识一下，强连通图：
线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们称之为顶点（Wertex）。
在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。
若顶点Vi与Vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（Vi,Vj）来表示。
若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧（Arc），记为<Vi,Vj>。
以 [图2.有向图] 为例，连接顶点A到D的有向边就是弧，A称为弧尾（Tail）。
通俗理解：我指向你，我就是弧尾。
以 [图2.有向图] 为例，连接顶点A到D的有向边就是弧，D称为弧头（Head）。
通俗理解：我指向你，你就是弧头。
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。 这些权可以表示从一个顶点到另一个顶点的距离。见*[图5、网]*
假设有两个图G=（V,{E}）和G’=（V’,{E’}），如果V’⊆V，且E’⊆E，则称G’为G的子图（Subgraph）。 （⊆数学符号，表示包含（两个集合可能相等））
看一张图，右侧的图即为左侧图的子图：
还记得树的度吗？树内各结点拥有的子树的数量的最大值。
无向图，只有度。 无向图：顶点v的度(Degree)是和v相关联的边的数目，记为TD(v)。
有向图，有出度与入度之分。 有向图：以顶点v为头的弧的数目称为v的入度（InDegree）,记为ID(v)。 有向图：以顶点v为尾的弧的数目称为v的出度（OutDegree）,记为OD(v)。
从顶点V到V’的所有顶点的序列。
无向图：我们要用数学的方法表示出来： （V=Vi,0，Vi,1，…，Vi,m）,其中（Vi,j-1,Vi,j）∈E，1<=j<=m。
无向图，顶点B到顶点D有4种不同的路径，如下图所示： 下图中上方的两图路径长度为2，下方两图的路径长度为3。 有向图，我们用数学的方法表示，顶点序列应满足<Vi,j-1，Vi,j>∈E，1<=j<=m。
有向图，顶点B到顶点D有2种不同的路径，如下图所示： 左图路径长度为2，右图路径长度为3。 树中根节点到任意结点的路径是唯一的，但是在图中，顶点与顶点之间的路径却不是唯一的。
路径的长度是路径上的边或弧的数目。
序列中顶点不重复出现的路径称为简单路径。
第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。
除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
上图中的两图，粗线都构成环，左侧的环因第一个顶点和最后一点顶点都是B，且C、D、A没有重复出现，因此是一个简单环。而右侧的环，由于顶点C的重复，所以部署简单环。
无向图中的极大连通子图称为连通分量。 强调几点：
要是子图；子图要是连通的；连通子图含有极大顶点数；具有极大顶点数的连通子图包含依附于这些顶点的所有边。来看一组图： 图A是一个无向非连通图。但是它有两个连通分量，即图B和图C。而图D，尽管是图A的子图，但是它确不满足连通子图的极大顶点数（图B满足）。因此它不是图A的无向图的连通分量。
有向图中的极大强连通子图称作有向图的强连通分量。 上图中，图1并不是强连通图，因为顶点A到顶点D存在路径，而D到A不存在。图2就是强连通图，而且强连通显然图2是图1的极大强连通子图，即是它的强连通分量。
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示。一个一维数组存储图中的顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。 第一张图就能看明白无向图的邻接矩阵： 第二张图就能看明白有向图的邻接矩阵： 创建一个邻接矩阵的代码片段：
//TODO 待补充//TODO 待补充
//TODO 待补充
//TODO 待补充
//TODO 待补充
基于邻接矩阵的深度优先遍历算法的案例如下：
// TODO 待补充基于邻接矩阵的广度优先遍历算法的案例如下：
// TODO 待补充//TODO 待补充
//TODO 待补充
//TODO 待补充
//TODO 待补充
本章内容需要进行实践，代码片还在编写中，等这个系列完成后回头来补充，但是前面的概念和关键术语也至关重要，得先记住。
码字不易，求个关注。
微信公众号： 一粒尘埃的漫旅
里面有很多想对大家说的话，就像和朋友聊聊天。 写代码，做设计，聊生活，聊工作，聊职场。 我见到的世界是什么样子的？ 搜索关注我吧。
