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

◎实验题目: 数据结构课程设计（无向连通网的问题求解）

◎实验目的：通过本次课程设计，掌握无向连通网的性质，熟悉其关于最短哈密尔顿回路以及最短路径的求解。

◎实验内容：对于具有n(n>=10)个顶点的无向连通网，设计一个算法

（1）找出网中最短的哈密尔顿回路；

（2）找出任意两个顶点之间的最短路径，须经过指定1个或2个顶点。

一、需求分析

1.本演示程序中，输入的无向连通网为任意给定的，输入时应该给定无向连通网的大小、范围，即顶点数以及边数，而输出有三个问题的求解答案，分别输出其路径及权值大小。

2.本演示程序为人机对话，用户可以按照提示进行输入，然后选择需要求解的问题，则有结果输出。

3.程序执行的命令包括：

（1）构建无向连通网（2）选择求解问题序号（3）第一个为求解最短哈密顿回路（3）第二个为求解任意两点之间的最短路径，须经过指定1个顶点（4）第三个为求解任意两点之间的最短路径，须经过指定2个顶点（5）结束

4.测试数据：

（1）请输入顶点数和边数(输入格式为:顶点数,边数):11,17

(2) 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10

(3) 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):

0,6,5

0,7,4

0,4,3

1,4,1

1,6,8

1,3,2

2,4,6

2,3,3

2,10,7

3,5,8

5,10,3

5,9,8

6,7,1

7,8,4

7,9,6

8,9,2

9,10,6

(4) 请选择操作:

<1>如果选择输入为1，结果为：

最短哈密尔顿回路为：0->6->7->8->9->5->10->2->3->1->4->0

权值为：5+1+4+2+8+3+7+3+2+1+3=39

<2>如果选择输入为2，结果为：

请输入指定起始点：0

请输入指定终点：6

请输入路径经过指定的顶点：10

输出路径是：0->4->2->10->9->7->6

起始点为0终点为6的经过指定点10的最短路径为：29

<3>如果选择输入为3，结果为:

请输入指定起始点：4

请输入指定终点：1

请输入路径经过指定的顶点一：8

请输入路径经过指定的顶点二：3

输出路径是：4->1->3->1->6->7->8->7->6->1

起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31

<4>如果选择输入为0，结果为:

结束.

二 概要设计

  为了实现上述操作，无向连通网用邻接矩阵存储结构，解决哈密顿回路问题时应用栈。

1.基本操作：

void hamidun(mgraph &g)

求解最短哈密尔顿回路

int lujing(mgraph g,int v0,int vn,int dist[],int prev[])

求解指定两点之间的最短路径

void ShowPath(mgraph g,int v0,int u,int *dist,int *prev)

输出所求最短路径所经过的顶点

void zhiding1(mgraph g,int v0,int vn,int vx)

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

void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)

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

2.本程序包含六个模块：

(1)主程序模块

（2）求解最短哈密尔顿回路模块

（3）求解指定两点之间的最短路径模块

（4）输出所求最短路径所经过的顶点模块

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

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

（7）模块调用图

三 详细设计

1.元素类型，结点类型和指针类型：

//图中的节点数

#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];

//记忆最短路径

Node aShortNode[M];

//记忆当前路径

Node aNode[M];

Node node;

2.每个模块的分析：

(1)主程序模块

int main()

{

    int i,j,k,w,v0,vn,vx,vx1,vx2,m;

    mgraph g;

    printf("请输入顶点数和边数(输入格式为:顶点数,边数):\\n");

    scanf("%d,%d",&(g.N),&(g.e));

    getchar();

    printf("请输入顶点信息(输入格式为:顶点号):\\n");

    for(i=0;i    {

        scanf("%d",&(g.vexs[i]));

        getchar();

    }

for(i=0;i     for(j=0;j            g.edge[i][j]=999;  //认为999时两顶点之间无边

        printf("请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):\\n");

        for(k=0;k        {

            scanf("%d,%d,%d",&i,&j,&w);

            g.edge[i][j]=g.edge[j][i]=w;

        }

        while(1)

        {

            printf("******************************************************************\\n");

            printf("\1.求解最短哈密尔顿回路.\n");

            printf("\2.求解任意两个顶点之间的经过指定一顶点的最短路径.\n");

            printf("\3.求解任意两个顶点之间的经过指定两顶点的最短路径.\n");

            printf("\0.结束操作.\n");

            printf("******************************************************************\\n");

            printf("请选择操作:");

            scanf("%d",&m);

            switch(m)

            {

            case 1:

                printf("最短哈密尔顿回路为:");

                hamidun(g);

                break;

            case 2:

                printf("***************经过指定一点最短路径:****************\\n");

                printf("请输入指定起始点:\\n");

                scanf("%d",&v0);

                printf("请输入指定终点:\\n");

                scanf("%d",&vn);

                printf("请输入路径经过指定的顶点:\\n");

                scanf("%d",&vx);

                zhiding1(g,v0,vn,vx);

                printf("\\n");

                break;

            case 3:

                printf("***************经过指定两点最短路径:****************\\n");

                printf("请输入指定起始点:\\n");

                scanf("%d",&v0);

                printf("请输入指定终点:\\n");

                scanf("%d",&vn);

                printf("请输入路径经过指定的顶点一:\\n");

                scanf("%d",&vx1);

                printf("请输入路径经过指定的顶点二:\\n");

                scanf("%d",&vx2);

                zhiding2(g,v0,vn,vx1,vx2);

                printf("\\n");

                break;

            case 0:

                exit(0); 

            default: printf("输出出错！\n");

            }

        }

        getchar();

        getchar();

        return 0;

}

（2）求解最短哈密尔顿回路模块

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                {

                    length=len;

                    //更改当前最短路径

                    for(i=0;i                        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;

                }

                //更新当前层

                po=node.level;

            }

        }

        else

        {

            po++; //下一层

            //将下一层节点入栈

            for(i=0;i            {

                //判断下一个压栈的节点在不在当前路径

                bool isIn=false;

             for(j=0;j                {

                    if(i==aNode[j].dot)

                    {

                        isIn=true;

                        break;

                    }

                }

                //不在当前路径

                if(!isIn)

                {

                    node.dot=i;

                    node.level=po;

                    top++;

                    s[top]=node;

                }

            }

        }

    }

     for(i=0;i         printf("%d->",aShortNode[i].dot);

        printf("%d",aShortNode[0].dot);

        printf("\\n");

        printf("权值为:");

     for(i=1;i            printf("%d+",g.edge[aShortNode[i-1].dot][aShortNode[i].dot]);

        printf("%d=%d",g.edge[0][aShortNode[g.N-1].dot],length);

        printf("\\n");

}

（3）求解指定两点之间的最短路径模块

int lujing(mgraph g,int v0,int vn,int dist[],int prev[])

{

    int i;

    int j;

    int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值

    int *s ;//定义具有最短路径的节点子集s

    s = (int *)malloc(sizeof(int) *g.N);

    //初始化最小路径代价和前一跳节点值

for (i= 0; i     {

        dist[i] = g.edge[v0][i];

        s[i] = 0;

        if (dist[i] == maxint)

        {

            prev[i] = 0;

        }

        else

        {

            prev[i] = v0;

        }

    }

    dist[v0] = 0;

    s[v0] = 1;//源节点作为最初的s子集

for (i = 1; i < g.N; i++)

    {

        int temp = maxint;

        int u = v0;

        //加入具有最小代价的邻居节点到s子集

for (j = 1; j <=g.N; j++)

        {

if ((!s[j]) && (dist[j] < temp))

            {

                u = j;

                temp = dist[j];

            }

        }

        s[u] = 1;

        //计算加入新的节点后，更新路径使得其产生代价最短

for (j = 1; j <=g.N; j++)

        {

if ((!s[j]) && (g.edge[u][j] < maxint))

            {

                int newdist = dist[u] + g.edge[u][j];

if (newdist < dist[j])

                {

                    dist[j] = newdist;

                    prev[j] = u;

                }

            }

        }

    }

    return dist[vn];

}

（4）输出所求最短路径所经过的顶点模块

void ShowPath(mgraph g,int v0,int u,int *dist,int *prev)

{

    int j= 0;

    int y=u;

    int count = 0;

    int *way ;

    way=(int *)malloc(sizeof(int)*(g.N+1));

    //回溯路径

    while (y!= v0)

    {

        count++;

        way[count] = prev[y];

        y= prev[y];

    }

    //输出路径

    for (j=count;j>=1;j--)

    {

     printf("%d->",way[j]);

    }

}

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

void zhiding1(mgraph g,int v0,int vn,int vx)

{

    int s1,s2,distance;

    int *dist;//最短路径代价

    int *prev;//前一跳节点空间

    dist = (int *)malloc(sizeof(int)*g.N);

    prev = (int *)malloc(sizeof(int)*g.N);

    printf("输出路径是:");

    s1=lujing(g,v0,vx,dist,prev);  //计算v0到vx的最短路径

    ShowPath(g,v0,vx,dist,prev);

    s2=lujing(g,vx,vn,dist,prev);  //计算vx到vn的最短路径

    ShowPath(g,vx,vn,dist,prev);

    printf("%d",vn);

    printf("\\n");

    distance=s1+s2;     //合起来便是v0到vn的最短路径

    printf("起始点为%d终点为%d的经过指定点%d的最短路径为:%d",v0,vn,vx,distance);

}

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

void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)

{

    int s11,s12,s13,s21,s22,s23,distance1,distance2,distance;

    int *dist;//最短路径代价

    int *prev;//前一跳节点空间

    dist = (int *)malloc(sizeof(int)*g.N);

    prev = (int *)malloc(sizeof(int)*g.N);

    printf("输出路径是:");

    s11=lujing(g,v0,vx1,dist,prev);

    s12=lujing(g,vx1,vx2,dist,prev);

    s13=lujing(g,vx2,vn,dist,prev);

    distance1=s11+s12+s13;    //计算从v0经vx1经vx2到vn的最短路径

    s21=lujing(g,v0,vx2,dist,prev);

    s22=lujing(g,vx2,vx1,dist,prev);

    s23=lujing(g,vx1,vn,dist,prev);

    distance2=s21+s22+s23;     //计算从v0经vx2经vx1到vn的最短路径

    if(distance1    {

        distance=distance1;

        s11=lujing(g,v0,vx1,dist,prev);

        ShowPath(g,v0,vx1,dist,prev);

        s12=lujing(g,vx1,vx2,dist,prev);

        ShowPath(g,vx1,vx2,dist,prev);

        s13=lujing(g,vx2,vn,dist,prev);

        ShowPath(g,vx2,vn,dist,prev);

        printf("%d",vn);

        printf("\\n");

    }

    else

    {

        distance=distance2;

        s21=lujing(g,v0,vx2,dist,prev);

        ShowPath(g,v0,vx2,dist,prev);

        s22=lujing(g,vx2,vx1,dist,prev);

        ShowPath(g,vx2,vx1,dist,prev);

        s23=lujing(g,vx1,vn,dist,prev);

        ShowPath(g,vx1,vn,dist,prev);

        printf("%d",vn);

        printf("\\n");

    }

    printf("起始点为%d终点为%d的经过指定点一%d以及指定点二%d的最短路径为:%d",v0,vn,vx1,vx2,distance);

}

3.函数调用关系图：

4．完整的程序：(见源文件).

四 使用说明、测试分析及结果

1．程序使用说明

（1）本程序的运行环境为VC6.0。

（2）进入演示程序后即显示提示信息：

<1>请输入顶点数和边数(输入格式为:顶点数,边数):11,17

<2> 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10

<3> 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):

0,6,5

0,7,4

0,4,3

1,4,1

1,6,8

1,3,2

2,4,6

2,3,3

2,10,7

3,5,8

5,10,3

5,9,8

6,7,1

7,8,4

7,9,6

8,9,2

9,10,6

2.测试结果：

请选择操作:

<1>如果选择输入为1，结果为：

最短哈密尔顿回路为：0->6->7->8->9->5->10->2->3->1->4->0

权值为：5+1+4+2+8+3+7+3+2+1+3=39

<2>如果选择输入为2，结果为：

请输入指定起始点：0

请输入指定终点：6

请输入路径经过指定的顶点：10

输出路径是：0->4->2->10->9->7->6

起始点为0终点为6的经过指定点10的最短路径为：29

<3>如果选择输入为3，结果为:

请输入指定起始点：4

请输入指定终点：1

请输入路径经过指定的顶点一：8

请输入路径经过指定的顶点二：3

输出路径是：4->1->3->1->6->7->8->7->6->1

起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31

<4>如果选择输入为0，结果为:

结束.

3．运行界面

构建无向连通网

选择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                {

                    length=len;

                    //更改当前最短路径

                    for(i=0;i                        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;

                }

                //更新当前层

                po=node.level;

            }

        }

        else

        {

            po++; //下一层

            //将下一层节点入栈

            for(i=0;i            {

                //判断下一个压栈的节点在不在当前路径

                bool isIn=false;

             for(j=0;j                {

                    if(i==aNode[j].dot)

                    {

                        isIn=true;

                        break;

                    }

                }

                //不在当前路径

                if(!isIn)

                {

                    node.dot=i;

                    node.level=po;

                    top++;

                    s[top]=node;

                }

            }

        }

    }

     for(i=0;i         printf("%d->",aShortNode[i].dot);

        printf("%d",aShortNode[0].dot);

        printf("\\n");

        printf("权值为:");

     for(i=1;i            printf("%d+",g.edge[aShortNode[i-1].dot][aShortNode[i].dot]);

        printf("%d=%d",g.edge[0][aShortNode[g.N-1].dot],length);

        printf("\\n");

}

int lujing(mgraph g,int v0,int vn,int dist[],int prev[])

{

    int i;

    int j;

    int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值

    int *s ;//定义具有最短路径的节点子集s

    s = (int *)malloc(sizeof(int) *g.N);

    //初始化最小路径代价和前一跳节点值

for (i= 0; i     {

        dist[i] = g.edge[v0][i];

        s[i] = 0;

        if (dist[i] == maxint)

        {

            prev[i] = 0;

        }

        else

        {

            prev[i] = v0;

        }

    }

    dist[v0] = 0;

    s[v0] = 1;//源节点作为最初的s子集

for (i = 1; i < g.N; i++)

    {

        int temp = maxint;

        int u = v0;

        //加入具有最小代价的邻居节点到s子集

for (j = 1; j <=g.N; j++)

        {

if ((!s[j]) && (dist[j] < temp))

            {

                u = j;

                temp = dist[j];

            }

        }

        s[u] = 1;

        //计算加入新的节点后，更新路径使得其产生代价最短

for (j = 1; j <=g.N; j++)

        {

if ((!s[j]) && (g.edge[u][j] < maxint))

            {

                int newdist = dist[u] + g.edge[u][j];

if (newdist < dist[j])

                {

                    dist[j] = newdist;

                    prev[j] = u;

                }

            }

        }

    }

    return dist[vn];

}

void ShowPath(mgraph g,int v0,int u,int *dist,int *prev)

{

    int j= 0;

    int y=u;

    int count = 0;

    int *way ;

    way=(int *)malloc(sizeof(int)*(g.N+1));

    //回溯路径

    while (y!= v0)

    {

        count++;

        way[count] = prev[y];

        y= prev[y];

    }

    //输出路径

    for (j=count;j>=1;j--)

    {

     printf("%d->",way[j]);

    }

}

//求解任意两个顶点之间的经过指定一顶点的最短路径

void zhiding1(mgraph g,int v0,int vn,int vx)

{

    int s1,s2,distance;

    int *dist;//最短路径代价

    int *prev;//前一跳节点空间

    dist = (int *)malloc(sizeof(int)*g.N);

    prev = (int *)malloc(sizeof(int)*g.N);

    printf("输出路径是:");

    s1=lujing(g,v0,vx,dist,prev);  //计算v0到vx的最短路径

    ShowPath(g,v0,vx,dist,prev);

    s2=lujing(g,vx,vn,dist,prev);  //计算vx到vn的最短路径

    ShowPath(g,vx,vn,dist,prev);

    printf("%d",vn);

    printf("\\n");

    distance=s1+s2;     //合起来便是v0到vn的最短路径

    printf("起始点为%d终点为%d的经过指定点%d的最短路径为:%d",v0,vn,vx,distance);

}

//求解任意两个顶点之间的经过指定两顶点的最短路径

void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2)

{

    int s11,s12,s13,s21,s22,s23,distance1,distance2,distance;

    int *dist;//最短路径代价

    int *prev;//前一跳节点空间

    dist = (int *)malloc(sizeof(int)*g.N);

    prev = (int *)malloc(sizeof(int)*g.N);

    printf("输出路径是:");

    s11=lujing(g,v0,vx1,dist,prev);

    s12=lujing(g,vx1,vx2,dist,prev);

    s13=lujing(g,vx2,vn,dist,prev);

    distance1=s11+s12+s13;    //计算从v0经vx1经vx2到vn的最短路径

    s21=lujing(g,v0,vx2,dist,prev);

    s22=lujing(g,vx2,vx1,dist,prev);

    s23=lujing(g,vx1,vn,dist,prev);

    distance2=s21+s22+s23;     //计算从v0经vx2经vx1到vn的最短路径

    if(distance1    {

        distance=distance1;

        s11=lujing(g,v0,vx1,dist,prev);

        ShowPath(g,v0,vx1,dist,prev);

        s12=lujing(g,vx1,vx2,dist,prev);

        ShowPath(g,vx1,vx2,dist,prev);

        s13=lujing(g,vx2,vn,dist,prev);

        ShowPath(g,vx2,vn,dist,prev);

        printf("%d",vn);

        printf("\\n");

    }

    else

    {

        distance=distance2;

        s21=lujing(g,v0,vx2,dist,prev);

        ShowPath(g,v0,vx2,dist,prev);

        s22=lujing(g,vx2,vx1,dist,prev);

        ShowPath(g,vx2,vx1,dist,prev);

        s23=lujing(g,vx1,vn,dist,prev);

        ShowPath(g,vx1,vn,dist,prev);

        printf("%d",vn);

        printf("\\n");

    }

    printf("起始点为%d终点为%d的经过指定点一%d以及指定点二%d的最短路径为:%d",v0,vn,vx1,vx2,distance);

}

int main()

{

    int i,j,k,w,v0,vn,vx,vx1,vx2,m;

    mgraph g;

    printf("请输入顶点数和边数(输入格式为:顶点数,边数):\\n");

    scanf("%d,%d",&(g.N),&(g.e));

    getchar();

    printf("请输入顶点信息(输入格式为:顶点号):\\n");

    for(i=0;i    {

        scanf("%d",&(g.vexs[i]));

        getchar();

    }

for(i=0;i     for(j=0;j            g.edge[i][j]=999;  //认为999时两顶点之间无边

        printf("请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:):\\n");

        for(k=0;k        {

            scanf("%d,%d,%d",&i,&j,&w);

            g.edge[i][j]=g.edge[j][i]=w;

        }

        while(1)

        {

            printf("******************************************************************\\n");

            printf("\1.求解最短哈密尔顿回路.\n");

            printf("\2.求解任意两个顶点之间的经过指定一顶点的最短路径.\n");

            printf("\3.求解任意两个顶点之间的经过指定两顶点的最短路径.\n");

            printf("\0.结束操作.\n");

            printf("******************************************************************\\n");

            printf("请选择操作:");

            scanf("%d",&m);

            switch(m)

            {

            case 1:

                printf("最短哈密尔顿回路为:");

                hamidun(g);

                break;

            case 2:

                printf("***************经过指定一点最短路径:****************\\n");

                printf("请输入指定起始点:\\n");

                scanf("%d",&v0);

                printf("请输入指定终点:\\n");

                scanf("%d",&vn);

                printf("请输入路径经过指定的顶点:\\n");

                scanf("%d",&vx);

                zhiding1(g,v0,vn,vx);

                printf("\\n");

                break;

            case 3:

                printf("***************经过指定两点最短路径:****************\\n");

                printf("请输入指定起始点:\\n");

                scanf("%d",&v0);

                printf("请输入指定终点:\\n");

                scanf("%d",&vn);

                printf("请输入路径经过指定的顶点一:\\n");

                scanf("%d",&vx1);

                printf("请输入路径经过指定的顶点二:\\n");

                scanf("%d",&vx2);

                zhiding2(g,v0,vn,vx1,vx2);

                printf("\\n");

                break;

            case 0:

                exit(0); 

            default: printf("输出出错！\n");

            }

        }

        getchar();

        getchar();

        return 0;

}