医院选址问题--这是中南大学计算机系数据结构课程设计里面的一道题
1. 问题描述
n个村庄之间的交通图可以用有向网图来表示，图中边
2. 基本要求
(1) 建立模型，设计存储结构
(2) 设计算法完成问题求解
(3) 分析算法的时间复杂度
3.实现代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include <stdio.h> #include <stdlib.h> #define MaxInt 10000//最大数 const int MaxNumEdges=50; const int MaxNumVertices=10; //最大顶点数 class Graph { private: int vNum;//当前顶点数 int eNum;//当前边数 int Vertex[MaxNumVertices];//顶点数组 int Edge[MaxNumVertices][MaxNumVertices];//边数组 bool GetVertexPos(const int &vertex,int &i);//给出顶点vertex在图中的位置 public: Graph(const int sz= MaxNumEdges);//构造函数 bool FindVertex(const int &vertex); bool InsertVertex(const int & vertex);//插入一个顶点vertex bool InsertEdge(const int v1,const int v2,const int weight);//插入一条边(v1,v2),该边上的权值为weight void Hospital();//医院选址函数 }; Graph::Graph(const int sz): vNum(0), eNum(0) //构造函数 { int n,e; int name,tail,head; int weight; for(int i=0;i<sz;i++) for(int j=0;j<sz;j++) { if(i==j) Edge[i][j]=0;//顶点到自身权值为0 else Edge[i][j]=10000;//邻接矩阵初始化为最大值 } printf("请输入村庄个数★不多于10个★：\n"); scanf("%d",&n); printf("\n请依次输入各个村庄的名称（用数字表示）:\n"); for(int i=0;i<n;i++)//依次输入顶点，插入图中 { scanf("%d",&name); InsertVertex(name); vNum++; } printf("\n请输入边数:\n"); scanf("%d",&e); printf("\n以下输入边信息:\n"); for(int i=0;i<e;i++) { printf("请输入第%d边头顶点:\n",i+1); scanf("%d",&head); printf("请输入该边尾顶点：\n"); scanf("%d",&tail); printf("请输入该边权值：\n"); scanf("%d",&weight); if(!InsertEdge(head,tail,weight)) { printf("不存在该边，请重新输入！\n"); continue; } } } bool Graph::FindVertex(const int& vertex) //给出顶点vertex在图中的位置 { for (int i = 0; i < vNum; i++) if (vertex == Vertex[i]) return true; return false; } bool Graph:: GetVertexPos(const int &vertex,int &i) //给出顶点vertex在图中的位置 { for (i = 0; i < vNum; i++) if (vertex == Vertex[i]) return true; return false; } bool Graph::InsertVertex(const int & vertex) //插入一个顶点vertex { if (FindVertex(vertex)) return false; Vertex[vNum] = vertex; return true; } bool Graph::InsertEdge(const int v1,const int v2,const int weight) //插入一条边(v1,v2),该边上的权值为weight { int k=0,j=0; if(GetVertexPos(v1,k) && GetVertexPos(v2,j)) { Edge[k][j]=weight; eNum++; Edge[j][k]=weight; eNum++; return true; } else return false; } void Graph::Hospital() //在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 { int k,i,j,s; for (k=0;k<vNum;k++) //求任意两顶点间的最短路径 for (i=0;i<vNum;i++) for (j=0;j<vNum;j++) if (Edge[i][k]+Edge[k][j]<Edge[i][j]) Edge[i][j]=Edge[i][k]+Edge[k][j]; int m=MaxInt; //设定m为机器内最大整数。 printf("********************************************\n"); //以下为求各村离医院最近的医院选址 int min=MaxInt ; //设定机器最大数作村庄间距离之和的初值。 k=0; //k设医院位置。 for (j=0;j<vNum;j++) { m=0 ; for (i=0;i<vNum;i++) m=m+Edge[i][j]; //顶点到其它顶点最短距离的距离之和 if (min>m) { min=m; k=j; } //取顶点间的距离之和的最小值。 }//for printf("要建医院的村庄号为:%d\n",k+1); //输出要建医院的村庄号 //输出要建医院的村庄号及离医院最远的村庄到医院的距离 for(j=0;j<vNum;j++) if(j!=k) printf("该村庄离%d村庄最短距离为:%d\n",j+1,Edge[k][j]); }//算法结束 int main() { printf(" \t 中 南 大 学 \n"); printf(" \t --------------------------------- \n"); printf(" \t | 医 院 选 址 | \n"); printf(" \t --------------------------------- \n"); printf(" \t 班级:物联网***班 \n"); printf(" \t --------------------------------- \n"); printf(" \t 姓名: ** 学号: *** \n"); printf(" \t --------------------------------- \n"); system("color 3E"); Graph Town(MaxNumVertices); Town.Hospital(); return 0; } |
文章评论