哈密尔顿回路

首先我们了解下什么是哈密尔顿回路，简单解释就是，有一个无向连通图G（具有顶点和边的图），他有N个顶点，从任意一个顶点出发，所有的顶点有且只经过一次，如果最后可以回到起点则我们称这个连通图G拥有哈密尔顿回路。网上大多都能搜索到通过Java，.Net语言实现的查找哈密尔顿回路的代码，今天我将带大家一起通过javascript实现查找哈密尔顿的方法。

无向连通图

graph LR
A --> B
B --> C
B --> D
B --> E
C --> D
D --> E
E --> F
F --> A

如上图所示，是一个简单的无向（忽略箭头，没找到不带箭头的连接线…）连通图，它拥有A,B,C,D,E,F共6个顶点，同时顶点之间还有边将两个顶点连接起来。那如何证明这个图拥有哈密尔顿回路并正确的返回这个回路的顶点路径集合呢?

实现寻找哈密尔顿回路

创建GraphG类

首先我们创建一个js文件，然后在文件内部创建一个类GraphG.我们设想一下，这个类应该有哪些方法？

• 可以添加一个顶点
• 可以将两个顶点连接起来
• 可以判断两个顶点之间有没有边（是否关联）

class GraphG {
  constructor() {
    this.vertices = []; //顶点集合
    this.adjList = new Map(); //顶点关联集合
  }
  
  //添加一个顶点
  addVertex(v) {
    this.vertices.push(v);   
    this.adjList.set(v, []); //初始化关联顶点为空
  }

  //把两个顶点相关联
  linkVertex(v, w) {
    // 如果两个顶点不存在，则返回
    if (!this.vertices.includes(v) || !this.vertices.includes(w)) {
      return;
    }
    // 把两个顶点分别放到彼此的Map集合里
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }

  //顶点v，w是否关联(是否存在边)
  hasEdge(v, w) {
    return this.adjList.get(v).includes(w);
  }
}

编写实现函数

接下来我们需要这样一个函数，它接受一个无向连通图，然后经过一系列计算判断这个图是否存在哈密尔顿回路，如果存在则返回这个回路的顶点路径集合，如果不存在则返回空。

class Hamilton {
  constructor(graph) {
    this.hamiltonPath = [];
    this.graph = graph;
  }
  findHamiltonPath() {
    const firstVertex = this.graph.vertices[0];
    this.hamiltonPath.push(firstVertex); //把第一个顶点放到回路里
    if (this.getPath(firstVertex, firstVertex)) {
      return this.hamiltonPath;
    }
    return [];
  }
  getPath(vertex, originalVertex) {
    if (this.hamiltonPath.length === this.graph.vertices.length) {
      //回路包含所有的路径
      if (this.graph.hasEdge(vertex, originalVertex)) {
        //并且最后两个顶点之间有边
        this.hamiltonPath.push(originalVertex);
        return true;
      }
      return false;
    }

    for (let i = 0; i < this.graph.adjList.get(vertex).length; i++) {
      const nextVertex = this.graph.adjList.get(vertex)[i]; // 取出一个关联的顶点；
      if (this.hamiltonPath.includes(nextVertex)) {
        continue; //如果这个顶点已经放到回路路径集合里了则直接跳过
      }
      this.hamiltonPath.push(nextVertex); //添加到回路集合里
      if (this.getPath(nextVertex, this.graph.vertices[0])) {
        //查看有没有结束
        return true;
      }
      this.hamiltonPath.pop(); //不符合哈密尔顿回路把最新的一个取出来
    }
    return false;
  }
}

通过分析上面代码我们可以看出，首先声明一个哈密尔顿回路的集合数组hamiltonPath,然后取第一个顶点作为起始点，通过方法getPath去比较，首先判断当前哈密尔顿回路是否把所有的顶点都放进来了，如果是则可以最后判断这个传进来的顶点（第一个参数vertex）跟第一个顶点是否有边，如果有说明此图拥有无向连通图，将路径的数组集合返回即可。如果这个路径集合还没有包含所有顶点则需要继续往下找。思路大致如下：

• 循环当前的顶点，找到所有它关联的顶点
• 取出一个关联的顶点，查看它是否已经在回路集合里了，如果有就跳过 （见26~29行代码）
• 如果不存在回路集合里，则把它添加到路径集合里 this.hamiltonPath.push(nextVertex);
• 重点来了，这时候再拿这个顶点去跟第一个顶点比较，看是否满足条件（这里会又进入getPath方法内去递推），如果不满足则把这个顶点从回路集合里拿出来（回溯）this.hamiltonPath.pop(); //不符合哈密尔顿回路把最新的一个取出来。如果满足则说明找到哈密尔顿回路。
• 如果所有循环都走完了也没有发现，就返回false（第37行代码）

光说不练假把式，我们实际测一下，就拿上面的图来做个测试吧。

const graph1 = new GraphG();
graph1.addVertex("A");
graph1.addVertex("B");
graph1.addVertex("C");
graph1.addVertex("D");
graph1.addVertex("E");
graph1.addVertex("F");
graph1.linkVertex("A", "B");
graph1.linkVertex("C", "B");
graph1.linkVertex("D", "B");
graph1.linkVertex("C", "D");
graph1.linkVertex("D", "E");
graph1.linkVertex("E", "F");
graph1.linkVertex("A", "F");

const hamilton = new Hamilton(graph1);
const result = hamilton.findHamiltonPath(); // [ 'A', 'B', 'C', 'D', 'E', 'F', 'A']

通过测试验证代码是运行成功的。其实这个哈密尔顿回路是一个很经典的用到递推和回溯思想的案例，如果下一层不满足就往上回溯一层。直到递推到最底层。然后把最底层得到返回结果再一层一层地传递上去，最终会得到想要的结果。

小小尝试，如果对你有帮助的话，欢迎点赞收藏哦！！！

原文链接：https://juejin.cn/post/7341304374756311067 作者：NoBuuug