数据结构课程设计实验报告

构建无向连通网

选择1，求解最短哈密尔顿回路

选择2，求解任意两点之间的最短路径，须经过指定1个顶点模块

选择3. 求解任意两点之间的最短路径，须经过指定2个顶点模块

五、实验总结

本次课程设计实验耗费时间比较多，需要准备的内容比较多，前期一直在研究算法，为后期的编写程序做好了准备，通过本次课设，对于无向图的最短路径的求解有了很深的体会，尤其是和离散数学的内容联系在一起，加强了学科之间的联系，在本次试验中，由于前期准备充足，在编写过程中没有遇到太大的问题，一些小问题经仔细检查后都得到了解决，通过本次实验，我更熟悉无向图的问题的求解，对于以后学习帮助很大。 教师评语：

实验成绩：

#include #include //图中的节点数 #define M 50

//哈密顿回路最长值 #define MAX_LENGTH 1024 //单边最大值

#define MAX_SIDE_LENGTH 30 //节点信息结构 struct Node {

int level; //位于生成树的第几层

int dot; //第几个节点 };

typedef struct { int edge[M][M];

int N,e;

int vexs[M];

}mgraph; Node s[99]; int top=-1;

void hamidun(mgraph &g) {

int i,j;

//记忆最短路径

Node aShortNode[M]; //记忆当前路径 Node aNode[M];

for(i=0;i

aNode[i].dot=-1; aNode[i].level=-1;

//最短回路长度

int length=MAX_LENGTH; //压入第一个节点 Node node; node.dot=0; node.level=0; top++;

s[top]=node;

int po=0;

int len=0;

while(top!=-1) { //记录路径节点 aNode[po]=s[top]; top--;

bool isEnd=false; //一条回路是否结束 if(po>=1) {

len=len+g.edge[aNode[po-1].dot][aNode[po].dot];

if(len>length

po==g.N-1||g.edge[aNode[po-1].dot][aNode[po].dot]==999)

isEnd=true;

}

if(isEnd) { //完整回路 if(po==g.N-1) { len=len+g.edge[0][aNode[g.N-1].dot]; if(len

aShortNode[i]=aNode[i];

}

len=len-g.edge[0][aNode[g.N-1].dot];

}

//路径回溯 if(top!=-1) { node=s[top];

for(i=po;i>=node.level;i--) { len=len-g.edge[aNode[i-1].dot][aNode[i].dot];

aNode[i].dot=-1;

aNode[i].level=-1; }

//更新当前层

||