12、图

这里学习另一种非线性数据结构—图。这是在学习数据结构里面学习的最后一种数据结构

12.1 图的相关术语

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。学习图还是比较重要的，任何的二元关系都可以用图来表示。
任何社交网络，例如 weixin、qi e、dingding、脸书 等… ，都可以使用图来表示。
还可以使用图来表示道路、航班、通信等等（脑补想象）
先了解下图在数学及技术上的概念
一个图 G=(V, E) 由以下元素组成

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

画个图来表示图：

在写代码之前，还是先了解下图中的一些术语。

• 有一条边连接在一起的顶点称为相邻顶点。比如，af 是相邻的， ab 是相邻的，bc 是相邻的 ，a 和 e 不是相邻的
• 一个顶点的度是其相邻顶点的数量。比如 A 和其他两个顶点相连接，因此 a 的度为 2；h 和三个顶点相连，因此 h 的度 为 3
• 路径是顶点 v1,v2,v3,…,vk 的一个连续序列，其中 vi 和 vi+1 是相邻的。以上一示意图中的图为例，其中包含路径 abcd 和 afgi
• 简单路径要求不包含重复的顶点。（afgi 是一条简单路径。）除去最后一个顶点（因为它和第一个顶点是同一顶点），环也是一个简单路径，比如 fghf（最后一个顶点重新回到 f）
• 如果图中不存在环，则称该图为 无环的。如果图中每两个顶点间都存在路径，则该图是 连通的。

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

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。 gh 是强连通，ab 不是强连通。
图还可以是 未加权的或是加权的。

该图 加权图的边被赋予了权值。
图可以用来解决计算机科学世界中的很多问题，比如搜索图中的一个特定顶点或搜索一条特定边，寻找图中的一条路径（从一个顶点到另一个顶点），寻找两个顶点之间的最短路径，以及环检测。

12.2 图的表示

从数据结构的角度来说，我们有多种方式来表示图。在所有的表示法中，不存在绝对正确的方式。图的正确表示法取决于待解决的问题和图的类型。

12.2.1 邻接矩阵

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

不是强连通的图（稀疏图），如果用邻接矩阵来表示，则矩阵中将会有很多 0 ，这意味着我们浪费了计算机存储空间来表示根本不存在的边。例如，找给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。邻接矩阵表示法不够好的另一个理由是，图中顶点的数量可能会改变，而二维数组不太灵活。

12.2.2 邻接表

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

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

12.2.3 关联矩阵

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

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

12.3 创建 Graph 类

/*
* @author: zhangning
* @date: 2022/5/9 23:22
* @Description: Graph 类
**/
import Dictionary from '../八、字典和散列表/1.字典/Dictionary.js';
class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected;
    this.vertices = [];
    // 实现一个字典，在 学习 字典和散列表的时候已经实现
    // 用于存储邻接表。字典使用顶点的名字作为键，邻接顶点列表作为值。
    this.adjList = new Dictionary();
  }
}