序
旅行商问题（Traveling Salesman Problem，简称TSP）是组合优化中的一个经典问题，就是给定一组城市和城市之间的距离，找到一条最短路径使得每个城市只被访问一次后返回到起点。
一些传统的解法都是基于完全图的，我在网上也很少找到非完全图的解法，非完全图应该在实际应用中会更实用，这里我简单实现一个算法。
算法细节
与完全图的差异
非完全图意味着某些节点之间不相连，这样求解时就需要考虑这样情况，不能直接假设两个节点直连。
图的预处理
最开始要对图进行预处理，这里我们针对于该图使用Kruskal算法构建一颗最小生成树，之后针对该树进行分支删减，以达到最终路线是一个环路。
我这里使用的输入的形式是邻接矩阵，假设路线图是这样的：
对应的邻接矩阵则是
using GraphVec = std::vector<std::vector<int>>;
GraphVec graph_8 = {{0, 3, 1, 1, 1, 0, 0, 0},{3, 0, 1, 0, 0, 1, 0, 0},{1, 1, 0, 1, 0, 0, 2, 0},{1, 0, 1, 0, 0, 0, 0, 1},{1, 0, 0, 0, 0, 1, 1, 1},{0, 1, 0, 0, 1, 0, 0, 1},{0, 0, 2, 0, 1, 0, 0, 1},{0, 0, 0, 1, 1, 1, 1, 0},};
最开始我们先来看下使用到的数据结构：
struct Edge{Edge() = default;Edge(int s, int e, int w) :start(s),end(e),weight(w) {}int start = -1;int end = -1;int weight = -1;
};
这里很简单，我就是将两个节点的边做了一下抽象
然后简单看一下最小生成树的构建过程：
using TreeDeque = std::deque<Edge>;
TreeDeque makeMSTByKruskal(const GraphVec& graph) {std::priority_queue<Edge, std::vector<Edge>, decltype(compare)> queue(compare);for (int i = 0; i < graph.size(); ++i) {for (int j = 0; j < graph[0].size(); ++j) {if (i < j && graph[i][j] > 0) {queue.emplace(i, j, graph[i][j]);}}}std::set<int> visited;TreeDeque tree;while (!queue.empty()) {auto edge = queue.top();queue.pop();if (visited.find(edge.start) != visited.end() && visited.find(edge.end) != visited.end()) {continue;}visited.insert(edge.start);visited.insert(edge.end);tree.push_back(edge);}return tree;
}
这里使
