数据结构实验报告-TSP问题

TSP问题一，实验目的熟悉图的数据结构，学会解决实际问题二，实验内容旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。三，设计与编码#includeiostreamusingnamespacestd;constintMaxSize=10;constintMax=100;intMin(intarr[],intn);classMGraph{public:MGraph(charcity[],intn,inte);~MGraph(){}voidTSP(intv);private:charvertex[MaxSize];intarc[MaxSize][MaxSize];intvertexNum,arcNum;};intvisited[MaxSize]={0};intmain(){charcity[]={'A','B','C','D','E'};MGraphMG(city,5,10);MG.TSP(0);return0;}voidMGraph::TSP(intv){coutvertex[v];visited[v]=1;inti=0,j=0,s=0;intlog=0;for(;logvertexNum;log++){j=Min(arc[i],vertexNum);visited[j]=1;cout-vertex[j];i=j;}}intMin(int*p,intn){intstart=0,min=p[0],k=0;while(visited[start]==1){start++;min=p[start];}for(;startn;start++){if((visited[start]==0)&&(min=p[start])){k=start;min=p[k];}}returnk;}//构造函数MGraph::MGraph(charcity[],intn,inte){vertexNum=n;arcNum=e;//存储顶点信息for(inti=0;ivertexNum;i++)vertex[i]=city[i];//初始化图的邻接矩阵for(inti=0;ivertexNum;i++)for(intj=0;jvertexNum;j++)arc[i][j]=100;//存储图的边信息inti,j,weight;for(intk=0;karcNum;k++){cout请输入边的两个顶点的序号及其权值：;cinijweight;arc[i][j]=weight;arc[j][i]=weight;}}四，运行与测试五，总结与心得通过对实际问题的解决，巩固了课本知识，提高了编写代码的能力