图

一个图G=(V, E)由以下元素组成。

• V：一组顶点

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

  
  
  image.png

相邻顶点

由一条边连接在一起的顶点称为相邻顶点。比如，A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的

度

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

路径

路径是顶点v 1, v2,…, vk的一个连续序列，其中vi和vi+1是相邻的。以上一示意图中的图为例，其中包含路径A B E I和A C D G。

简单路径要求不包含重复的顶点。举个例子，A D G是一条简单路径。除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径，比如A D C A（最后一个顶点重新回到A）。

如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是连通的。

有向图和无向图

图可以是无向的（边没有方向）或是有向的（有向图）。如下图所示，有向图的边有一个方向。

image.png

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

图还可以是未加权的（目前为止我们看到的图都是未加权的）或是加权的。如下图所示，加权图的边被赋予了权值。

image.png

入度和出度

在有向图中，我们把度分为入度（In-degree）和出度（Out-degree）。

顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。

图的表示

1.邻接矩阵

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。如果索引为i的节点和索引为j的节点相邻，则array[i][j] === 1，否则array[i][j] === 0，如下图所示。

image.png

2.邻接表

我们也可以使用一种叫作邻接表的动态数据结构来表示图。邻接表由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。下面的示意图展示了邻接表数据结构。

image.png

尽管邻接表可能对大多数问题来说都是更好的选择，但以上两种表示法都很有用，且它们有着不同的性质（例如，要找出顶点v和w是否相邻，使用邻接矩阵会比较快）

3.关联矩阵

还可以用关联矩阵来表示图。在关联矩阵中，矩阵的行表示顶点，列表示边。如下图所示，使用二维数组来表示两者之间的连通性，如果顶点v是边e的入射点，则array[v][e] === 1；否则，array[v][e] === 0。

image.png

关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存。

代码demo

    /**
     * 使用邻接表存储图
     * 使用Map表示相邻顶点列表
    */
    class Graph{
      constructor(isDirected = false) {
        // 图是否有向（默认无向）
        this.isDirected = isDirected;
        // 使用数组存储所有顶点
        this.vertices = [];
        // 使用顶点名作为键，相邻顶点作为值
        this.adjList = new Map();
      }
      // 添加顶点
      addVertex(v){
        if(!this.vertices.includes(v)){
          this.vertices.push(v);
          // 顶点v的相邻顶点使用Set存储
          this.adjList.set(v, new Set());
        }
      }
      // 添加边，参数为连接边的两个顶点
      addEdge(v, w){
        if(!this.vertices.includes(v)){
          this.addVertex(v);
        }
        if(!this.vertices.includes(w)){
          this.addVertex(w);
        }
        this.adjList.get(v).add(w);
        // 如果是无向图，则再添加一条w到v的边
        if(!this.isDirected){
          this.adjList.get(w).add(v);
        }
      }
      // 返回顶点列表
      getVertices(){
        return this.vertices;
      }
      // 返回邻接表
      getAdjList(){
        this.adjList;
      }
    }

    const graph = new Graph();

    const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
    for(let i of myVertices){
      graph.addVertex(i);
    }
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('A', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'G');
    graph.addEdge('D', 'H');
    graph.addEdge('D', 'G');
    graph.addEdge('B', 'E');
    graph.addEdge('B', 'F');
    graph.addEdge('E', 'I');

    console.log(graph)