图：一种非线性数据结构。图是一组由边连接的节点（或顶点）。任何二元关系都用图来表示。
一个图由 G=(V,E)组成

  • V：一组顶点
  • E：一组边，连接V中的顶点

    术语

    image.png

    相邻顶点

    有一条边连接在一起的顶点称为 相邻顶点 。比如A-B，A-C，A-D 都是相邻的。

    度

    一个顶点的 度 是其相邻顶点的数量。比如A和其他三个顶点连接，因此A的度是3。

    路径

    路径是顶点V1，V2，……，Vk的一个连续序列，其中Vi和Vi+1是相邻的，根据下图，其中ABEI和ACDG，简单路径要求不包含重复的顶点
    环 也是一个简单的路径，比如ADCA（最后一个顶点重新回到了A）。如果图中不存在环，则改图没无环的，如果图中每两个顶点间都存在路径，则该图是连同的。

    有向图和无向图

    如果图中每 两个顶点间在双向上都存在路径 ，则该图是 强连通 ，例如，C和D是强连通，而A和B不是强连通。
    image.png

    加权 未加权

邻接矩阵

图常见的实现就是 邻接矩阵 ,如下图。每个节点都和一个整树相关联，该整数将作为数组的索引。常用一个二维数组来表示顶点之间的连接，如果索引为i的节点和索引为j节点的相邻，则array[i][j] === 1，否则array[i][j] ===0
image.png
缺点：不是强连通图（稀疏图）如果使用邻接矩阵来表示，很多矩阵中会有很多0，意味着浪费计算机存储空间来表示根本不可能存在的边。
着给定顶点的相邻顶点，即使只有一个顶点 都需要迭代一整行。

邻接表

使用邻接表的动态数据结构来表示图，玲姐表由每个顶点的相邻顶点列表组成。存在好几种方式来表示这种数据结构，可以使用数组，链表，散列，字典来表示相邻顶点列表。
image.png

关联矩阵

关联矩阵中，矩阵的行表示顶点，矩阵的列表示边。使用二维数组来表示两者之间的连接关系，如顶点V是边E的入射点，则array[v][e] === 1 ,否则,array[v][e] ===0。
image.png
TODO