- 图的定义
线性表中我们把数据元素叫元素，树中将数据元素叫结点,在图中数据元素，我们则称之为顶点(Vertex)。
图( Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
需要注意的是线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。但是图不能没有顶点。
- 边
无向边:若顶点v到v之间的边没有方向，则称这条边为无向边(Edge)，用无序偶对（vi,vj)来表示。如果图中全都是无向边，则称该图为无向图。
有向边:若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧(Arc )。可以写作<vi,vj>。注意不能写作<vj,vi>。
总结：无向边用小括号“()”表示,而有向边则是用尖括号“<>”表示。
图上的边或弧上带权则称为网。
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。我们主要讨论的都是简单图。
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。
有很少条边或弧的图称为稀疏图,反之称为稠密图。
对于无向图G= (V{E)，如果边（v') ∈E，则称顶点v和V互为邻接点(Adjacent)，即v和v相邻接。
顶点v的度（Degree)是和v相关联的边的数目,记为TD(v)。
- 连通图
在无向图G中，如果从顶点vi到顶点vj有路径，则称vi和vj是连通的。如果对于图中任意两个顶点vi和vj都是连通的，则称G是连通图(ConnectedGraph)。
无向图中的极大连通子图称为连通分量。
在有向图G中，如果对于每一对vi、vj∈V、v≠V，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
- 图的储存结构
邻接矩阵储存方式：用两个数组来表示一个图，一个一维数组来储存顶点信息，一个二维数组（又叫邻接矩阵）来储存边的信息。
邻接表储存方式：将邻接矩阵中的二维数组改成n个链表，第i个链表储存i点到其他顶点的边的信息，可以节约储存空间。
链式前向星：参考这篇博客有关SPFA，Dijkstra和l链式前向星 - redintonc - 博客园 (cnblogs.com)
边集数组：将所有边储存在一个一维数组中，在最小生成树算法中会用来寻找权值最小的边。
标签：连通,vi,vj,基础,储存,数组,顶点,408 From： https://www.cnblogs.com/redintoncforever/p/17033251.html