图论(一)

图论

图论（Graph theory）是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。

图论起源于著名的柯尼斯堡七桥问题。

图

图是由顶点(Vertex)和边(Edge)组成，每条边的两端都必须是图的两个顶点(可以是相同的顶点)。而记号G(V,E)表示图G的顶点集合是V，边集合是E。

如下(就像公交车路线一样，四通八达的)

    v4────────────v5
   /
 v1────v6
   \  /
    v3

一般来说，图分为有向图和无向图，有向图的所有边都有方向，而无向图每一条边都是双向的。

术语

顶点的度:指的是和该顶点相连边的条数

出度:对于有向图来说，顶点的出边条数称为出度

入度:对于有向图来说，顶点的入边条数称为入度

权值:每一条边和顶点都可以有一定的属性，量化的属性称为权值，顶点和边的权值分别称为点权和边权

图的存储

一:邻接矩阵，一般在顶点不大于1000时，我们可以选用邻接矩阵实现图(实际上是二维数组)。

二:邻接表，C++可以采用vector(一种顺序容器，支持随机访问)实现邻接表。Java可以采用List去实