实验六图的应用

——城市间道路网建设最经济方案的选择

一、实验目的与要求

1．理解图的邻接矩阵、邻接表等存储表示方法；

2．熟悉图的深度优秀搜索遍历和广度优先搜索遍历算法；

3．能利用图的基本知识解决最小生成树、最短路径等实际问题。

二、实验内容

用图实现城市间道路网建设最经济方案的选择。

三、实验指导

1、问题描述

有6个城市(A、B、C、D、E、F)如图6.1所示，己知每对城市间交通线的建造费用，要求建造一个连接6个城市的交通网，使得任意两个城市之间都可以直接或间接互达，要求使总的建造费用最小。问：如何建造6个城市间的道路交通网?

2、问题分析

该问题要求建立连接6个城市的道路交通网，给出如图6.1所示的连接6个城市的道路建设方案。要使建造费用最低，可将图中连接各城市的道路建设费用视为距离长度，就可用带权无向图的最小生成树来求解。得出的最小生成树即为建设连接各城市道路网的最经济方案。可采用普里姆算法求解。

图6.1 连接6个城市的道路交通网

3、解决方案

(I)类型定义

typedef char VexType;  /*顶点数据类型*/

typedef int EdgeType;/*边数据类型*/

typedef struct

{ VexType vexs[VexNum];

  EdgeType arcs[VexNum][VexNum];

  int vexnum,arcnum;  /* 顶点数和边数 */

}Mgraph;  /* 图的邻接矩阵表示结构定义 */

typedef struct

{int adjvex;/*集合U中的顶点(始点)*/

 int value;/*集合u中顶点到非U中的某个顶点的最小距离值*/

}InterEdge;

(2)主要算法

void Min_SpanTree(Mgraph G,int u) 

{/*最小至成树的普里姆算法,以u为起始点,求用邻接矩阵表示的图G的最小生成树,然后输出*/

    InterEdge ee[VexNum];

    int  cc=0,pp[VexNum*2];

    int k=0,i,j,s1,in;

    for(i=0;i    {  

        ee[i].adjvex=u;

        ee[i].value=G.arcs[u][i];

    }

    ee[u].value=0;

    for(i=1;i    {  

        k=MinValue(ee,G.vexnum);

        s1=ee[k].adjvex;  /*在一个顶点在U中,另一个顶点不在U中的边中,边(s1,k)是一条权值最小的边*/

        ee[k].value=0;  /*将顶点k加入到U中*/

        pp[cc]=s1;

        cc++;pp[cc]=k;cc++;  /*将最小生成树的一条边(sl,k)记录到数组PP中*/

        for(j=0;j            if(G.arcs[k][j]            {/*调整最短路径,并保存下标*/

                ee[j].value=G.arcs[k][j];  ee[j].adjvex=k;

            }

    }

    printf("\\n The minimum spantree Solution is:\\n");

    for(i=0;i<2*(G.vexnum-1);i=i+2)

        printf("(%2c,%2c);",G.vexs[pp[i]],G.vexs[pp[i+1]]);/*最小生成树组成边输出*/

} 

(3)程序

#include

#include

#define VexNum 20    /*图的最多顶点个数*/

#define MAXINT 30000  /*极大值*/

typedef char VexType;  /* 顶点数据类型 */

typedef int EdgeType; /* 边数据类型 */

typedef struct

{ VexType vexs[VexNum];

  EdgeType arcs[VexNum][VexNum];

  int vexnum,arcnum;  /* 顶点数和边数 */

}Mgraph;  /* 图的邻接矩阵表示结构定义 */

typedef struct

{int adjvex;/*集合U中的顶点(始点)*/

 int value;/*集合u中顶点到非U中的某个顶点的最小距离值*/

}InterEdge;

void Min_SpanTree(Mgraph G,int u);

Mgraph Create_MgraphN();

int MinValue(InterEdge ee[],int n);

void main()

{

    Mgraph G;

    G=Create_MgraphN( );

    Min_SpanTree(G,0);

}

Mgraph Create_MgraphN()

{  /* 创建无向带权图的邻接矩阵算法 */

    int i,j,k;

    EdgeType v;  /* 边的权值 */

    Mgraph G;

    printf("Input Vex number：");

    scanf("%d",&G.vexnum);  /*顶点个数*/

    printf("Input Edge number：");

    scanf("%d",&G.arcnum);  /*边条数*/

    printf("Input %d vexs information such as ABCD：\\n",G.vexnum);

    scanf("%s",G.vexs);    /*顶点字符表示符*/

    for(i=0;i    {

        for(j=0;j                      ①          ；/*置初始距离值为MAXINT*/

                ②          ； /*顶点到本身的距离值为0*/

    }

    for(k=1;k<=G.arcnum;k++)

    {

printf("Input %dth Edge i,j：",k);

            ③           ；  /*输入对应边起点序号和终点序号*/

    while(i<1|| i>G.vexnum || j<1 || j>G.vexnum)

    {

        printf("Error Vex Number,Retry,i,j;");

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

    }

    printf("Input Edge Value：");

    scanf("%d",&v);  /*输入边的权值*/

           ④           ；

           ⑤           ； /*④⑤为无向图存储边权值*/

    }

    return G;

}

int MinValue(InterEdge ee[],int n)  /*比较求最小距离值,并返回对应下标*/

{

    int i,j,k;

    for(j=0;j    if(ee[j].value>0)

    {

        k=j;  break;

    }

    for(j=1;j        if(ee[j].value>0 && ee[j].value            k=j;

    return k;

}

 (4)测试数据及运行结果

 ：6

 ：9

 ：

 ：1，2

 ：5

 ，j：1，3

 ：6

 ：2，3

 ：1

 ：2，4

 ：2

 ，j：2，5

 ：7

 ，j：3，5

 ：5

 ：4，5

 ：3

 ：4，6

 ：4

 ，j：5，6

 ：4

程序运行结果为：

                                                           （请记录）

4、结果分析与讨论

本例用普里姆算法根据输入的无向带权图的数据，输出组成最小生成树的边。根据这些边，可以画出最小生成树。最小生成树不是唯一的，输入的顺序不同，输出结果可能会不同。

5、思考与练习

若用邻接表作为图的存储结构创建图，完成求邻接表表示的图的最小生成树算法。

代码：

#include

#include

#图的最多顶点个数*/

#define MAXINT 30000  /*极大值*/

typedef char VexType;  /* 顶点数据类型 */

typedef int EdgeType; /* 边数据类型 */

typedef struct

{ VexType vexs[VexNum];

  EdgeType arcs[VexNum][VexNum];

  int vexnum,arcnum;  /* 顶点数和边数 */

}Mgraph;  /* 图的邻接矩阵表示结构定义 */

typedef struct

{int adjvex;/*集合U中的顶点(始点)*/

 int value;/*集合u中顶点到非U中的某个顶点的最小距离值*/

}InterEdge;

void Min_SpanTree(Mgraph G,int u);

Mgraph Create_MgraphN();

int MinValue(InterEdge ee[],int n);

int main()

{

}

Mgraph Create_MgraphN()

{  /* 创建无向带权图的邻接矩阵算法 */

 边的权值 */

 ：");

 顶点个数*/

 ：");

 边条数*/

 ：\\n",G.vexnum);

    scanf("%s",G.vexs);    /*顶点字符表示符*/

   置初始距离值为MAXINT*/

  顶点到本身的距离值为0*/

 ：",k);

 输入对应边起点序号和终点序号*/

 ：");

 输入边的权值*/

 ④⑤为无向图存储边权值*/

}

int MinValue(InterEdge ee[],int n)  /*比较求最小距离值,并返回对应下标*/

{

}

void Min_SpanTree(Mgraph G,int u) 

{/*最小至成树的普里姆算法,以u为起始点,求用邻接矩阵表示的图G的最小生成树,然后输出*/

 求最小生成树的(n一1)条边,n为顶点数G.vexnum*/

  在一个顶点在U中,另一个顶点不在U中的边中,边(s1,k)是一条权值最小的边*/

  将顶点k加入到U中*/

  将最小生成树的一条边(sl,k)记录到数组PP中*/

   调整最短路径,并保存下标*/

  最小生成树组成边输出*/

}