网站建设推广软件,网站价值 批量查询,完成网站建设的心得体会,租赁服务器1)问题描述 n个村庄之间的交通图可以用有向网图来表示#xff0c;图中边vi, vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院#xff0c;问这所医院应建在哪个村庄#xff0c;才能使所有的村庄离医院都比较近#xff1f; 2)… 1)问题描述 n个村庄之间的交通图可以用有向网图来表示图中边vi, vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院问这所医院应建在哪个村庄才能使所有的村庄离医院都比较近 2) 基本要求 (1) 建立模型设计存储结构 (2) 设计算法完成问题求解 (3) 分析算法的时间复杂度。 3) 设计思想 医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。 设图GVE对任一顶点k称E(k)max{d(i, k)}i∈V为顶点k的偏心度。显然偏心度最小的顶点即为图G的中心点。 如图3(a)所示是一个带权有向图其各顶点的偏心度如图(b)所示。 4)医院选址问题的算法用伪代码描述如下 1对加权有向图调用Floyd算法求每对顶点间最短路径长度的矩阵 2对最短路径长度矩阵的每列求大值即得到各顶点的偏心度 3具有最小偏心度的顶点即为所求。 5)代码附录 1 #includestdio.h2 #includestdlib.h3 #includestring.h4 #define INFINITY 10000005 #define MAX_VERTEX_NUM 206 7 //定义弧的权值信息8 typedef struct Arccell9 {10 int adj; //权值11 } Arccell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //图的邻接矩阵12 //定义结点信息13 typedef struct VertexInfo14 {15 char name[20];//结点[村庄]名称16 int position;//定点编号17 } VertexInfo;18 //图的结构19 typedef struct Mgraph20 {21 VertexInfo vexs[MAX_VERTEX_NUM];//顶点数组22 AdjMatrix arcs;//邻接矩阵23 int vernum,arcnum;//分别指定顶点数和边数24 } Mgraph;25 26 27 //对图的初始化28 Mgraph initgraph()29 {30 Mgraph c;31 printf(请输入该图的顶点个数和弧的个数\n);32 printf(顶点个数);33 scanf(%d,c.vernum);34 printf(弧的个数);35 scanf(%d,c.arcnum);36 //依次设置顶点编号37 for(int i0; ic.vernum; i)38 {39 c.vexs[i].positioni;40 }41 //依次输入各顶点信息42 /*43 strcpy(c.vexs[0].name,a);44 strcpy(c.vexs[1].name,b);45 strcpy(c.vexs[2].name,c);46 strcpy(c.vexs[3].name,d);47 strcpy(c.vexs[4].name,e);48 49 */50 printf(\n请依次输入各个村庄的名称\n);51 for(int i0;ic.vernum;i)52 {53 printf(村庄%d:,i);54 scanf(%s,c.vexs[i].name);55 56 }57 58 //依次设置各弧的信息59 for(int i0; ic.vernum; i)60 {61 //先初始化邻接矩阵,相同点设置为0其他全部设置为INFINITY无穷大62 for(int j0; jc.vernum; j)63 {64 c.arcs[i][j].adjINFINITY;65 if(ij)66 {67 c.arcs[i][j].adj0;68 }69 }70 }71 //再依次输入需要设置的权值72 int i,j,k;73 printf(请输入需要设置的弧长及其两端顶点[输入3个0结束]\n);74 while(scanf(%d%d%d,i,j,k))75 {76 if(i0j0k0)77 break;78 c.arcs[i][j].adjk;79 }80 /*81 c.arcs[0][1].adj1;82 c.arcs[1][2].adj2;83 c.arcs[2][3].adj2;84 c.arcs[2][4].adj4;85 c.arcs[3][1].adj1;86 c.arcs[3][2].adj3;87 c.arcs[4][3].adj5;88 */89 return c;90 }91 92 //输出邻接矩阵93 void printMatrix(Mgraph c)94 {95 printf(该图的邻接矩阵如下所示\n);96 int count0;//用于计数97 for(int i0; ic.vernum; i)98 for(int j0; jc.vernum; j)99 {
100 if(c.arcs[i][j].adjINFINITY)
101 printf( #);
102 else
103 printf(%4d,c.arcs[i][j].adj);
104 count;
105 if(count%c.vernum0)
106 printf(\n);
107 }
108 }
109
110 void ShortestPath_Floyd(Mgraph G,int dis[][MAX_VERTEX_NUM])
111 {
112 //用floyd算法求有向网G中各对定点v和w之间的最短路径及其带权长度dis[v][w]
113 for(int v0; vG.vernum; v)
114 for(int w0; wG.vernum; w)
115 {
116 //对各结点之间初始化已知距离
117 dis[v][w]G.arcs[v][w].adj;
118 }
119
120 for(int u0; uG.vernum; u)
121 for(int v0; vG.vernum; v)
122 for(int w0; wG.vernum; w)
123 {
124 if(dis[v][u]dis[u][w]dis[v][w])
125 {
126 //从v经u到w的路径更短
127 dis[v][w]dis[v][u]dis[u][w];
128 }
129 }
130
131 }
132 //输出距离矩阵
133 void printDis(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
134 {
135 printf(\n经过Flyod算法之后各顶点之间的距离如下\n);
136 for(int i0; iG.vernum; i)
137 {
138 for(int j0; jG.vernum; j)
139 {
140 if(dis[i][j]1000000)
141 printf( #);
142 else
143 printf(%4d,dis[i][j]);
144
145 }
146 printf(\n);
147 }
148 }
149
150 //得到偏心度degree[]数组
151 void getDegree(Mgraph G,int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM],int degree[])
152 {
153 for(int i0;iG.vernum;i)
154 {
155 int maxdis[0][i];
156 for(int j0;jG.vernum;j)
157 {
158 if(dis[j][i]max)
159 maxdis[j][i];
160 }
161 degree[i]max;
162 }
163 }
164
165
166
167 int main()
168 {
169 printf(**********欢迎使用医院选址系统*********\n);
170 Mgraph cinitgraph();
171 system(cls);
172
173 //输出邻接矩阵
174 getchar();
175 printMatrix(c);
176
177 //定义距离数组调用Floyd算法得到结果
178 int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
179 ShortestPath_Floyd(c,dis);
180
181 //输出各个顶点之间的距离矩阵
182 getchar();
183 printDis(c,dis);
184
185 //存放偏心度数
186 int degree[c.vernum];
187 getDegree(c,dis,degree);
188
189 //显示各顶点的偏心度
190 getchar();
191 printf(\n各顶点的偏心度如下所示\n);
192 for(int i0;ic.vernum;i)
193 {
194 if(degree[i]1000000)
195 printf( #\n);
196 else
197 printf(%4d\n,degree[i]);
198 }
199
200 //得到最小村庄的编号和名称
201 int num;
202 int mindegree[0];
203 for(int i0;ic.vernum;i)
204 {
205 if(mindegree[i])
206 mindegree[i];
207 }
208
209 for(int i0;ic.vernum;i)
210 {
211 if(mindegree[i])
212 {
213 numi;
214 break;
215 }
216 }
217 getchar();
218 printf(\n偏心度最小的村庄编号%4d\n,num);//输出偏心度最小的村庄编号
219 printf(医院应该建立在村庄: %4s \n,c.vexs[num].name);
220 return 0;
221
222 } 6)测试结果 1.首先运行程序出现如图6.1所示。 图6.1 程序运行开始界面 2.输入顶点个数和边的个数之后会提示输入村庄名称如图6.2所示。 图6.2 提示输入村庄名称界面 3.村庄名称输入结束之后提示输入边的起始点和权值如图6.3所示。 图6.3 提示输入边相关信息的界面 4.输入边的信息以输入0 0 0结束如图6.4所示。 图6.4 输入边相关信息界面 5.边的信息输入完成之后回车得到邻接矩阵如图6.5所示。 图6.5 邻接矩阵表 6.继续回车得到距离矩阵如图6.6所示。 图6.6 距离矩阵表 7.回车得到偏心度表如图6.7所示。 图6.7 各顶点偏心度 8.最后程序输出医院选址结果如图6.8所示。 图6.8 最终结果 转载于:https://www.cnblogs.com/wujiyang/p/4491750.html
