相邻顶点 ：由一条边来连接在一起的顶点称为相邻顶点。
如上图里，a 与 b是相邻的，a 与 c 是相邻的，但 a 与 d 不是相邻的。
度：一个顶点度是其相邻顶点的数量。
如上图里 a 与两个顶点相邻，那么其度为2。b 与三个顶点相邻，那么其度为3。
路径：路径是顶点 v1，v2，…，vk的一个连续序列，其中 vi 和 vi + 1 是相邻的。
如上图所示，a,b,d,f 是一条简单的路径。
环：如果路径的最后一个顶点能重新回到该路径的第一个顶点，那么该路径称之为环。
如果图中不存在环，那么该图是无环的。如果图中每两个顶点都存在路径，则该图是联通的。

1、有向图与无向图

图可以是无向的（边没有方向，即无向图），也可以是有向的（即有向图，有向图的边至少有一个方向）。

我们可以观察一下下图。

在这个图里我们可以看见，A 与 E点是双向链接的，则证明此图是强连通的。

例如，A 与 E 是强连通的，A 与 B不是强连通的。

2、加权图与未加权图

图片也还可以是未加权的（上面的两个图都是未加权的）或是加权的（加权图的边被赋予了值）。

三、图的表示

从数据结构的角度来说，我们有很多方式来表示，在所有的表示法中，不存在绝对正确的方法。

图的正确表示法取决于待解决的问题和其类型。

1、邻接矩阵

图最常见的表示方法就是邻接矩阵。

这里我们可以参考下图。

不是强连通的图如果用邻接矩阵来表示，则矩阵中会有很多0，这意味着我们浪费了计算机的存储空间来表示根本不存在的边。

同样的，如果图中的顶点数里改变了，那么我们也不太好修改矩阵（二维数组不太灵活）。

2、邻接表

我们也可以使用 邻接表 来表示图。

邻接表由图中每个顶点的相邻点列表组成。

而这种数据结构存在好几种的实现方法。

我们可以用数组，链表，字典或是散列表来实现。

下图展示了邻接表的数据结构。

四、创建图类

照例声明一个类。

class Graph {
    constructor(isDirected = false) {
        this.isDirected =isDirected;
        this.vertices = [];
        this.adjList = new Dictionary();
    }
}

在 Graph 类的构造函数里，我们声明了三个变量。

isDirected 变量来表示图是否存在向，默认情况下图是无向的。

vertices 变量用来存储图中所欲顶点的名字。

adjList 字典（该字典我们在本系列第七篇中以实现）用来存储邻接表。

adjList 字典会使用顶点的名字作为键，邻接顶点列表作为值。

声明完后，我们来实现这么几个方法。

1、addVertex 方法

addVertex(v) {
    if ( this.vertices.includes(v) ) return;

    this.vertices.push(v);
    this.adjList.set(v,[]);
}

该方法用于创建一个顶点。

如果该值存在于图中，那么则不进行任何操作。‘

如果不存在，那么我们将这个值放入图中，并且为其对应的字典值设为一个空数组。

2、addEdge 方法

addEdge(v,w) {
    if ( !this.adjList.get(v) ) this.addVertex(v);
    if ( !this.adjList.get(w) ) this.addVertex(w);

    this.adjList.get(v).push(w);
    if ( !this.isDirected ) this.adjList.get(w).push(v);
}

该方法接收两个顶点作为参数，也就是说我们要建立链接的两个顶点。

在连接前，我们先要判定这两个顶点是否全部存在于图中，如若不存在，则去创建。

如若存在，则为第一个顶点对应的字典值放入第二个顶点。

并且如果图是无向的，那么第二个顶点对应的字典纸同样放入第一个顶点。

3、getVertices、getAdjList 与 toString 方法

如果要完成创建 Graph 类，那么我们还需要声明两个取值的方法：一个返回顶点列表，一个返回邻接表。

getVertices() { return this.vertices; }

getAdjList() { return this.adjList; }

toString() {
    let string = "";

    for ( let i = 0; i < this.vertices.length; i++ ) {
        string += `${this.vertices[i]} -> `;
        let neighbors = this.adjList.get(this.vertices[i]);
        for ( let j = 0; j < neighbors.length; j++ ) s += `${neighbors[j]}`;
        string += '\n';
    }

    return string;
}

当然了，还有一个方便我们查看的方法。

完成了这三个方法后让我们来测试一下以下的代码吧。

const graph = new Graph();
const vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];

for (let i = 0; i < vertices.length; i++) graph.addVertex(vertices[i]);

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I'); 

console.log(graph.toString());

其输出结果如下。

五、图的遍历

同树数据结构类似，我们可以访问图的所有节点。

其中，有两种算法可以对图进行遍历：广度优先搜索（Breadth-first Search，BFS） 和 深度优先搜索（Depth-first Search，DFS）。

图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。

完全探索一个顶点要求我们查看该顶点的每一条边，对于每一条没有被访问过的，需将对其进行标记住待访问，并将其加入待访问的列表中。

为了保证算法的效率，每个顶点的访问次数尽量最多两次。连通图中每条边和顶点都会被访问到。

接下来，我们来创建一个常量，作为标记顶点状态的常量。

const Status = {
	toBeVisited : 0,// 未访问
	incompleteAccess : 1,// 未完全访问
	fullAccess ： 2// 完全访问
}

其次还需要一个函数来初始化每个顶点的状态。

const initializeStatus = vertices => {
    const statu = {};
    for ( let i = 0; i < vertices.length; i++ ) statu[vertices[i]] = Status.toBeVisited;
    return statu;
}

1、广度优先搜索

广度优先搜索算法会先宽后深的访问顶点。

理解了这个概念后，我们来实现广度优先搜索算法。

const breadthFirstSearch = (graph,starVertex,callback) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices),
        queue = new Queue();

    queue.enqueue(starVertex);

    while ( !queue.isEmpty() ) {
        let u = queue.dequeue(),
            neighbors = adjList.get(u);
            
        statu[u] = Status.incompleteAccess;

        for ( let i = 0; i < neighbors.length; i++ ) {
            let w = neighbors[i];
            if ( statu[w] === Status.toBeVisited ) {
                statu[w] = Status.incompleteAccess;
                queue.enqueue(w);
            }
        }
        statu[u] = Status.fullAccess;
        if ( callback ) callback(u);
    }
}

breadthFirstSearch 方法接收一个图实例和顶点作为算法的起始点。其起始点是必要的，我们需要将他加入队列，其次就是遍历。

不过在遍历前，我们需要用 initializeStatusv 函数来将 statu 数组初始化为未访问状态。

与此同时我们还需要声明一个 Queue 实例来存储待访问和待探索的顶点。

声明完这两个变量后，我们就可以开始进行遍历了。

如果队列非空，那么我们将通过队列操作从队列中移除一个顶点，并取得一个包含其所有邻接点的表。再将该顶点标注为未完全访问，表示我们已经访问了，但未完全探索完。

当对该店全部探索完后，我们将该点标注为完全访问。

之后为了查看结果，我们为 breadthFirstSearch 方法还填充了一个可以接收回调函数的功能，方便我们来进行测试。

（1）、使用 BFS 寻找最短路径

上例中，我们展示了 BSF 算法的工作原理，那么接下来我们尝试用它做更多的事情。

例如，我们给定一个图 G 和源顶点 v，找出每个顶点 u 和 v 之间的最短路径的距离（以边的数里计算）。

对于给定顶点 v，广度优先算法会访问所有其距离为 1 的顶点，接着是距离为 2 的顶点，以此类推。

我们可以修改 breadthFirstSearch 方法返回给我们的信息：

从 v 到 u 的距离
前溯点 predecessors[u]。

让我们来看看改进后的广度优先方法的实现。

const BFS = (graph,starVertex) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices),
        queue = new Queue(),
        distances = {},
        predecessors = {};

    queue.enqueue(starVertex);

    for ( let i = 0; i < vertices.length; i++ ) {
        distances[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    while ( !queue.isEmpty() ) {
        let u = queue.dequeue(),
            neighbors = adjList.get(u);

        statu[u] = Status.incompleteAccess;

        for ( let i = 0; i < neighbors.length; i++ ) {
            let w = neighbors[i];
            if ( statu[w] === Status.toBeVisited ) {
                statu[w] = Status.incompleteAccess;
                distances[w] = distances[u] + 1;
                predecessors[w] = u;
                queue.enqueue(w);
            }
        }
        statu[u] = Status.fullAccess;
    }

    return {
        distances,
        predecessors
    }
}

改进后的 BFS 方法有什么改变呢？

首先是我们还需要声明数组 distances 来表示距离，以及 predecessors 数组来表示前溯点。

下一步则是对于图中的每个顶点的循环初始化。

用 0 来初始化数组 destances ，用 null 来初始化数组 predecessor。

之后当我们发现顶点 u 的邻点 w是，则设置 w 的前溯点为 u。并且我们通过给 distances[u] 加 1来增加 v 和 w 之间的距离。

最后返回一个包含 distances 和 predecessor 的对象。

2、深度优先搜索

深度优先搜索算法会先深后广的访问顶点。

理解了这个概念后，我们来实现深度优先搜索算法。

const depthFirstSearch = (graph,callback) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices);

    for ( let i = 0; i < vertices.length; i++ ) {
        if ( statu[vertices[i]] === Status.toBeVisited ) {
            depthFirstSearchVisit(vertices[i],statu,adjList,callback);
        }
    }
}

const depthFirstSearchVisit = (u,statu,adjList,callback) => {
    statu[u] = Status.incompleteAccess;
    if ( callback ) callback(u);
    let neighbors = adjList.get(u);
    for ( let i = 0; i < Status.length; i++ ) {
        let w = neighbors[i];
        if ( statu[w] === Status.toBeVisited ) {
            depthFirstSearchVisit(w,color,adjList,callback);
        }
    }
    statu[u] = Status.fullAccess;
}

depthFirstSearch 方法接收一个图实例和回调函数作为参数。

在初始化每个顶点的颜色后，对于图实例中每一个违背访问过的顶点，我们调用私有的递归函数 depthFirstSearchVisit ，传递的参数为要访问的顶点 u、状态数组、邻接表与回调函数。

当访问顶点 u 时，我们标注其为未完全访问后，提取包含顶点 u 所有邻点的列表。

对于顶点 u 的每一个未被访问过的邻点 w。

我们将再次调用这个函数。

最后在该顶点和邻点按深度访问后，我们回退，并将该顶点标注为完全访问。

鉴于图的知识实在是太多了，这篇文章还需要好好整理一下再完善

码农公寓

JavaScript 数据结构系列目录

文章目录

一、图的概述

二、图的相关术语