基于PRIM的TSP问题的近似算法求解完整C++代码
时间: 2023-12-15 07:05:38 浏览: 36
以下是基于PRIM的TSP问题的近似算法求解完整C++代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
int tsp_prim(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
vector<int> route(n, -1);
// 选择起点为节点0
route[0] = 0;
visited[0] = true;
// 构建最小生成树
for (int i = 1; i < n; i++) {
int last = route[i - 1];
int nearest = -1;
int minDist = INF;
// 找到距离最近的未访问节点
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[last][j] < minDist) {
nearest = j;
minDist = graph[last][j];
}
}
// 将节点加入路径中
route[i] = nearest;
visited[nearest] = true;
}
// 将路径首尾相接形成环
route[n] = 0;
// 计算路径长度
int totalDist = 0;
for (int i = 0; i < n; i++) {
totalDist += graph[route[i]][route[i + 1]];
}
return totalDist;
}
int main() {
// 示例图的邻接矩阵表示
vector<vector<int>> graph = {
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 }
};
int dist = tsp_prim(graph);
cout << "The total distance is: " << dist << endl;
return 0;
}
```
该代码中,我们定义了一个`tsp_prim`函数来求解TSP问题。该函数接收一个邻接矩阵表示的图作为输入,返回一个整数表示路径长度。在函数中,我们首先选择起点为节点0,并构建最小生成树。最后将路径首尾相接形成环,并计算路径长度。