05.图
约 410 字大约 1 分钟
图（Graph）是一种复杂的非线性表结构。
顶点（vertex）：图中的元素；
边（edge）：图中的顶点与其他任意顶点建立连接的关系；
顶点的度（degree)：跟顶点相连接的边的条数。
入度（In-degree）和出度（Out-degree）：对于有向图，一个顶点的入度是指以其为终点的边数；出度指以该顶点为起点的边数；
图有多种类型，包括有向图、无向图、简单图、多重图、有向图、无向图等；
图的分类
图的存储
邻接矩阵表示法
是图的常用存储表示，它的底层依赖一个二维数组。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息 
无向图
我们可以设置两个数组，顶点数组为vertex[4]={v0,v1,v2,v3}，边数组arc[4][4]为上图右边这样的一个矩阵。
对于矩阵的主对角线的值，即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3]，全为0是因为不存在顶点的边。 
有向图：
顶点数组为vertex[4]={v0,v1,v2,v3}，弧数组arc[4][4]为下图右边这样的一个矩阵。主对角线上数值依然为0。
但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc[1][0]=1，而v到v没有弧，因此arc[0][1]=0。 