图论

一、什么是图？

• 图结构是一种与==树==结构有些==相似==的数据结构.
• 图论是数学的一个分支，在数学的概念上，==树是图的一种==
• 它以图为研究对象，研究==顶点==和==边==组成的图形的数学理论和方法.
• 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系

那么，什么是图呢?

我们会发现，上面的结点(图中叫==顶点 Vertex==)之间的关系是不能使用树来表示使用几叉树都不可以模拟

，这个时候,我们就可以使用图来模拟它们。

图的特点

• ==一组顶点==：通常用 ==V(Vertex)==表示顶点的集合

• ==一组边==∶ 通常用==E(Edge)==表示边的集合

  • 边是顶点和顶点之间的连线

  • 边可以是==有向==的也可以是==无向==的

  • 比如A–B,通常表示无向。A–>B,通常表示有向

二、图的概念

顶点:

• 表示图中的一个==节点==
• 比如地铁站中某个站/ 多个村庄中的某个村庄/ 互联网中的某台主机/人际关系中的人

边:

• 表示顶点和==顶点之间==的==连线==
• 比如地铁站中两个站点之间的直接连线，就是—个边
• 注意: 这里的边不要叫做路径，路径有其他的概念。

相邻顶点

• 由==一条边连接在一起的顶点==称为相邻顶点

度

• 一个顶点的度是==相邻顶点的数量==.

图一

路径

• 路径是顶点V1,V2…,Vn的一个==连续序列==。比如上图中的 0-1-5-9是一条简单的路径
• 简单路径:：简单路径要求==不包含重复==的顶点.
• 回路：==第一个顶点==和==最后一个顶点相同的路径==称为回路。比如0-1-5-6-3-0

无向图:

• 所有的边都==没有方向==（边没有箭头）
• 比如 0 - 1之间有边，那么说明这条边可以保证0 -> 1，也可以保证 1 -> 0

图二

有向图:

• 图中的边是有方向的（边有箭头）
• 比如 0 -> 1，不能保证一定可以 1 -> 0，要根据方向来定

无权图:

• 图一
• 边没有携带权重(边无关长度和时间的长短)
• 边是没有任何意义

带权图：

• 图二
• 边有一定的权重。这里的权重可以是任意你希望表示的数据
• 比如距离或者花费的 时间 或者 票价.

三、图的表示

顶点的表示

• 使用==数组==来储存所有==顶点==

边的表示

1.邻接矩阵（非重点）

• 每个节点和一个整数相关联，该整数作为数组的下标值
• 用一个二维数组来表示顶点之间的连接.
• 在二维数组中，0表示没有连线，1表示有连线
• 通过二维数组,我们可以很快的找到一个顶点和哪些顶点有连线
• 另外,A-A,B-B(也就是顶点到自己的连线)通常使用O表示

2.邻接表（==重点==）

• 邻接表由图中每个顶点以及和==顶点相邻的顶点列表==组成
• 这个列表有很多中方式来存储，==数组/链表/字典(哈希表)==都可以

- 邻接表的问题

• 邻接表计算”出度”是比较简单的(出度:指向别人的数量,入度:指向自己的数量)
• 邻接表如果需要计算有向图的”λ度”,那么是一件非常麻烦的事情.
• 它必须构造一个“逆邻接表”,才能有效的计算“入度”但是开发中“出度”相对用的比较少

四、图的遍历

图的遍历思想

• 图的遍历思想和==树的遍历==思想是一样的.
• 图的遍历意味着需要将图中==毎个顶点访问一遍==，并且==不能有重复==的访问

有两种算法可以对图进行遍历

• ==广度==优先搜索( Breadth-First-search,简称==BFS==)
• ==深度==优先搜索(Depth-First-search,简称==DFS==)
• 两种遍历算法，都需要明确指定 第一个被访问的顶点

广度优先搜索的思路：

广度优先算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层.
换句话说，就是先宽后深的访问顶点

广度优先搜索的实现：

• 创建一个==队列==Q
• 将V标注为被发现的(灰色)，并将v将入队列Q
• 如果Q非空，执行下面的步骤:
  • 将v从Q中取出队列.
  • 将ν标注为被发现的灰色
  • 将ν所有的未被访问过的邻接点(白色)，加入到队列中
  • 将v标志为黑色.

深度优先搜索的思路:

深度优先搜索算法将会从第—个指定的顶点开始遍历图，沿着路径直到这条路径最后被访问了
接着原路回退并探索条路径。

• 深度优先搜索算法的实现
  广度优先搜索算法我们使用的是队列,这里可以使用栈完成,也可以使用递归.
  方便代码书写,我们还是使用递归(递归本质上就是函数栈的调用)

为了记录顶点是否被访问过，我们使用三种颜色来反应它们的状态

• ==白色==：表示该顶点还==没有被访问==.
• ==灰色==：表示该顶点被访问过，但并==未被探索==过
• ==黑色==：表示该顶点被访问过且被==完全探索==过.

五、图结构的封装

属性和方法

属性：

1. vertexes：所有顶点（数组）
2. edges：边（字典）

方法：

1. addVertex（）：添加顶点；
2. addEdge（v1, v2）：添加边, v1,v2表示顶点；
3. toString（）：输出所有顶点
4. bfs（）：广度优先搜索
5. dfs（）：深度优先搜索；

具体代码：

 // 封装图结构
function Graph() {
  // 属性：
  // 定点：数组
  this.vertexes = [];
  // 边：字典
  this.edges = new Dictionay();

  // 添加定点
  Graph.prototype.addVertex = function (v) {
    this.vertexes.push(v);
    this.edges.set(v, []);
  }

  // 添加边, v1,v2表示顶点
  Graph.prototype.addEdge = function (v1, v2) {
    this.edges.get(v1).push(v2);
    this.edges.get(v2).push(v1);
  }

  Graph.prototype.toString = function () {
    // 1.定义字符串，保存最终的结果
    let resultStr = '';

    // 2.遍历所有的顶点，以及顶点对应的边
    for (let i = 0; i < this.vertexes.length; i++) {
      const vertex = this.vertexes[i];

      resultStr += vertex + '->';
      let vEdges = this.edges.get(vertex);

      for (let j = 0; j < vEdges.length; j++) {
        resultStr += vEdges[j] + ' ';
      }

      resultStr += '\n';

    }

    return resultStr;
  }

  Graph.prototype.initializeColor = function () {
    let color = [];
    for (let i = 0; i < this.vertexes.length; i++) {
      const vertex = this.vertexes[i];
      color[vertex] = 'white';
    }

    return color;
  }

  // 广度优先搜索
  // initV: 初始化的顶点
  Graph.prototype.bfs = function (initV, handler) {
    // 1.初始化颜色
    const colors = this.initializeColor();

    // 2.创建队列
    const queue = new Queue();

    // 3.将顶点加入到队列中
    queue.enqueue(initV);

    // 4.循环从队列中取出元素
    while (!queue.isEmpty()) {
      // 4.1 从队列中取出一个顶点
      const v = queue.dequeue();

      // 4.2 获取和顶点相连的另外顶点
      const vList = this.edges.get(v);

      // 4.3 将v的颜色设置成灰色
      colors[v] = 'gray';

      // 4.4 遍历所有的顶点，加入到队列中
      for (let i = 0; i < vList.length; i++) {
        const e = vList[i];
        if (colors[e] === 'white') {
          colors[e] = 'gray';
          queue.enqueue(e);
        }
      }

      // 4.5 访问顶点
      handler(v);

      // 4.6 将顶点设置为黑色
      colors[v] = 'black';
    }

  }

  // 深度优先搜索
  Graph.prototype.dfs = function (initV, handler) {
    // 1.初始化颜色
    const colors = this.initializeColor();

    // 2.从某个顶点开始一次递归访问
    this.dfsVisit(initV, colors, handler);
  }

  Graph.prototype.dfsVisit = function (v, colors, handler) {
    // 1.将颜色设置成灰色
    colors[v] = 'gray';

    // 2.处理v顶点
    handler(v);

    // 3.访问v相连的顶点
    const vList = this.edges.get(v);

    for (let i = 0; i < vList.length; i++) {
      const e = vList[i];
      if (colors[e] === 'white') {
        this.dfsVisit(e, colors, handler);
      }

    }
    // 4.将v设置成黑色
    colors[v] = 'black';
  }

}

测试用例：

const g = new Graph();

// 添加顶点
let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];

for (let i = 0; i < myVertexes.length; i++) {
  const item = myVertexes[i];
  g.addVertex(item)
}

// 添加边
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('A', 'D');
g.addEdge('C', 'D');
g.addEdge('C', 'G');
g.addEdge('D', 'G');
g.addEdge('D', 'H');
g.addEdge('B', 'E');
g.addEdge('B', 'F');
g.addEdge('E', 'I');

console.log(g.toString())

// 广度优先遍历
var bfsResult = '';
g.bfs(g.vertexes[0], function (v) {
  bfsResult += v + ' ';
})
console.log('广度优先搜索：' + bfsResult)

// 深度优先遍历
var dfsResult = '';
g.bfs(g.vertexes[0], function (v) {
  dfsResult += v + ' ';
})
console.log('深度优先搜索：' + dfsResult)

字典结构

// 封装字典结构
function Dictionay() {
  // 字典属性
  this.item = {};

  // 在字典中添加键值对
  Dictionay.prototype.set = function (key, value) {
    this.item[key] = value;
  }

  // 判断字典中是否有某个Key
  Dictionay.prototype.has = function (key) {
    return this.item.hasOwnProperty(key);
  }

  // 从字典中移除元素
  Dictionay.prototype.remove = function (key) {
    // 1.判断字典中是否有这个key
    if (!this.has(key)) return false;

    // 2.从字典中删除key
    delete this.item[key];
    return true;
  }

  Dictionay.prototype.get = function (key) {
    return this.has(key) ? this.item[key] : undefined;
  }

  Dictionay.prototype.gets = function () {
    return Object.keys(this.item);
  }

}

队列结构：

function Queue() {
  this.items = [];

  // 向队列尾部天机一个或多个新的项
  Queue.prototype.enqueue = function (el) {
    this.items.push(el);
  }

  // 移出队列的第一项（排在队列最前面的）项，并返回被移出的元素
  Queue.prototype.dequeue = function () {
    return this.items.shift();
  }

  // 返回队列中第一个元素——最先被添加，也将是最先被移除的元素。
  // 队列不做任何变动，不移除元素，只返回元素
  Queue.prototype.front = function () {
    return this.items[0]
  }

  // 如果队列中不包含任何元素，返回true，否则返回false
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }

  // 返回队列包含的元素个数，与数组的length属性类似
  Queue.prototype.size = function () {
    return this.items.length;
  }

  // 将队列中的内容，转换成字符串形式
  Queue.prototype.toString = function () {
    return this.items.toString();
  }
}