《数据结构实验报告TSP问题.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告TSP问题.docx（2页珍藏版）》请在三一办公上搜索。
1、数据结构实验报告TSP问题 TSP问题 一，实验目的 熟悉图的数据结构，学会解决实际问题 二，实验内容 旅行商问题，即TSP问题又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制 是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 三，设计与编码 #include using namespace std; const int MaxSize = 10; const int Max = 100; int Min(int arr,int n); class MG
2、raph public: MGraph(char city, int n, int e); MGraph void TSP(int v); private: char vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum, arcNum; ; int visitedMaxSize = 0; int main char city = A,B,C,D,E; MGraph MG(city, 5, 10); MG.TSP(0); return 0; void MGraph:TSP(int v) cout vertexv; visitedv = 1; i
3、nt i = 0,j = 0, s = 0; int log = 0; for(;log vertexNum;log+) j = Min(arci,vertexNum); visitedj = 1; cout vertexj; i = j; int Min(int *p,int n) int start = 0, min = p0, k = 0; while(visitedstart = 1) start+; min = pstart; for(;start = pstart) k = start; min = pk; return k; /构造函数 MGraph:MGraph(char ci
4、ty, int n, int e) vertexNum = n; arcNum = e; /存储顶点信息 for(int i = 0; i vertexNum; i+) vertexi = cityi; /初始化图的邻接矩阵 for(int i = 0; i vertexNum; i+) for(int j = 0; j vertexNum; j+) arcij = 100; /存储图的边信息 int i,j,weight; for(int k = 0; k arcNum; k+) cout i j weight; arcij = weight; arcji = weight; 四，运行与测试 五，总结与心得 通过对实际问题的解决，巩固了课本知识，提高了编写代码的能力
