图是一组由边连接的节点（或顶点）。它有以下几种表示方法：

1. 邻接矩阵；
2. 邻接表；
3. 关联矩阵；

邻接矩阵表示法

• 可以使用二维数组来存储邻接矩阵，数组的下标表示节点，值表示两个节点直接有没边，有边则为 1，否则为 0
• 如果图的边带有权重，则可以把 1 换为权重的值

邻接表表示法
记录每个节点，及其相邻节点的数据结构。可以用字典、对象来存储邻接表

以下，我们使用邻接表法来创建一个图。

图：即将创建的图和它的邻接表表示法

定义图类的操作方法

• addVertex(vertex:string):void 用来添加图的节点
• addEdge(from:string,to:string):void 用来添加节点的邻居节点

数据结构

怎么用 JavaScript 定义图的数据结构？
因为我们要使用邻接表法来创建图，所以一般是一个节点对应一组邻居节点，那么就可以使用对象来记录，键为节点，值为邻居节点数组。然后我们再用一个字段来表示是 有向图 还是 _无向图_，有向图的话代表如果 A 到 B 有边，那么 B 到 A 也是有边的。

1. 声明图的骨架
   使用neighbors对象来存储邻接表

   
    class Graph {
        constructor(isDirected) {
            this.vertices = [];
            this.neighbors = {};
            // 有向图还是无向图
            this.isDirected = isDirected;
        }
    }
    

2. 实现添加图的节点

   
   addVertex(vertex) {
     this.vertices.push(vertex);
     // 顺便初始化邻接表
     this.neighbors[vertex] = [];
   }
   

3. 实现添加节点间的边

   
   addEdge(from,to) {
     this.neighbors[from].push(to);
     //如果是无向图，则反向也是有边
     if(!this.isDirected) {
       this.neighbors[to].push(from);
     }
   }
   

4. 使用方法

   
   // 1. 实例化Graph类
   const graph = new Graph(false);
   // 2. 添加节点
   const vertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
   vertexes.forEach((item) => graph.addVertex(item));
   // 3. 添加节点边的关系
   graph.addVertex();
   graph.addEdge("A", "B");
   graph.addEdge("A", "C");
   graph.addEdge("A", "D");
   graph.addEdge("B", "E");
   graph.addEdge("B", "F");
   graph.addEdge("C", "D");
   graph.addEdge("C", "G");
   graph.addEdge("D", "G");
   graph.addEdge("D", "H");
   graph.addEdge("E", "I");
   

图的遍历
图的遍历本质上是访问图的所有节点，可以用来实现查找某个节点，寻找两个节点间的路径，检查图是否连通，检查图是否有环

有两种遍历图的方法：

• 广度优先遍历（breadth-first search）
• 深度优先遍历 (depth-first search)

两种遍历方法解决思路：

1. 从图的一个节点出发，标记当前节点为被发现的
2. 然后记录当前节点的所有未被发现的邻居节点到一个待访问列表
3. 然后就可把当前节点标记为已访问
4. 再递归地访问待访问列表中的节点

其中涉及到节点的三种状态未被发现``被发现的``已访问 + 待访问列表

两种遍历方法的差别仅在于待访问列表的数据结构，bfs 使用队列而 dfs 使用栈，队列则遵循 FIFO 原则，栈则遵循 LIFO 原则

所以，可以根据上面的解决思路来实现具体的算法。

1. 先定义节点的三种状态

   
   const Vertex_Status = {
    notVisited:0,
    visited:1,
    found:2
   }
   
   // 初始化每个节点都是未访问的
   
   

2. 广度优先遍历

  const BFS = (graph:Graph, topVertex:string) => {
  // 使用队列存储待访问列表
  const queue = [];
  const vertexes = graph.vertices;
  const status = {};
  vertexes.forEach((vertex) => {
    status[vertex] = Vertex_Status.notVisited;
  });
  queue.push(topVertex);
  status[topVertex] = Vertex_Status.found;
  while (queue.length) {
    // 出对，先进先出
    const current = queue.shift();
    const neighbors = graph.neighbors[current];
    for (let i = 0; i < neighbors.length; ++i) {
      if (colors[neighbors[i]] === Colors.white) {
        status[neighbors[i]] = Vertex_Status.found;
        queue.push(neighbors[i]);
      }
    }
    status[current] = Vertex_Status.visited;
    console.log(current);
  }
  };

  BFS(graph,graph.vertices[0])
  // 输出结果 A B C D E F G H I
  

示图：

3. 深度优先遍历

const depthFirstSearch = (graph) => {
  const vertexes = graph.vertexes;
  const neighbors = graph.neighbors;
  const status = {};
  vertexes.forEach((vertex) => {
    status[vertex] = Vertex_Status.notVisited;
  });

  for (let i = 0; i < vertexes.length; ++i) {
    if (status[vertexes[i]] === Vertex_Status.notVisited) {
      dfs(vertexes[i], status, graph);
    }
  }
};

function dfs(u, colors, graph) {
  status[u] = Vertex_Status.found;
  const neighbors = graph.neighbors[u];
  for (let i = 0; i < neighbors.length; i++) {
    if (status[neighbors[i]] === Vertex_Status.notVisited) {
      dfs(neighbors[i], status, graph);
    }
  }
  status[u] = Vertex_Status.visited;
  console.log(u);
}

// depthFirstSearch(graph);
// 输出结果：I E F B G H D C A

示图

如何使用这两个算法原理做更多的事情？下次再讲下 ：）

Reference：
《学习 JavaScript 数据结构与算法（第 3 版）》