1、1）內容： 需要在某個城市n個居民小區之間鋪設煤氣管道，則在這n個居民小區之間只需要鋪設n-1條管道即可。假設任意兩個小區之間都可以鋪設管道，但由于地理環境不同，所需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小，這個問題即為求無向網的最小生成樹。 2）要求： 在可能假設的m條管道中，選取n-1條管道，使得既能連通n個小區，又能使總投資最小。每條管道的費用以網中該邊的權值形式給出，網的存儲采用鄰接表的結構。 3) 測試數據: 使用下圖給出的無線網數據作為程序的輸入，求出最佳鋪設方案。右側是給出的參考解。 4）輸入輸出: 參考完整代碼：#include iostream#include s
2、tdlib.h#define MAX_VERTEX_NUM 20typedef float WeightType;typedef struct ArcNodeint adjvex;WeightType weight;struct ArcNode *nextarc;ArcNode;typedef struct VertexNodechar data;ArcNode *firstarc;VertexNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum, arcnum;int kind;ALGraph;int Lo
3、cateVex(ALGraph G, char v)int i;for (i = 0; i G.vexnum; i+)if (G.verticesi.data = v)return i;return -1;void CreateGraph(ALGraph &G)int i, j, k;char vi, vj;WeightType weight;ArcNode *p,*q;std:cout G.vexnum G.arcnum G.kind;for ( i = 0; i G.vexnum; i+)std:cout G.verticesi.data;G.verticesi.firstarc = NU
4、LL;for ( k = 0; k G.arcnum; k+)std:cout vi vj weight;i = LocateVex(G, vi);j = LocateVex(G, vj);p = (ArcNode *)malloc(sizeof(ArcNode);p-adjvex = j;p-weight = weight;p-nextarc = G.verticesi.firstarc;G.verticesi.firstarc = p;if (G.kind = 2)q = (ArcNode*)malloc(sizeof(ArcNode);q-adjvex = i;q-weight = p-
5、weight;q-nextarc = G.verticesj.firstarc;G.verticesj.firstarc = q;int MinEdge(WeightType lowcost, int vexmun)int i, k;WeightType j;k = 0;while (lowcostk=0)k+;j = lowcostk;for ( i = k+1; i vexmun; i+)if (lowcosti!=0&lowcosti j)j=lowcosti;k = i;return k;void Prim(ALGraph G, int v0, int adjvex)WeightTyp
6、e lowcostMAX_VERTEX_NUM;int i, k;ArcNode *p;for ( i = 0; i adjvex = p-weight;p = p-nextarc;lowcostv0 = 0;for ( i = 0; i = G.vexnum)return;std:cout ( k , adjvexk ), lowcostkweightadjvex)adjvexp-adjvex = k;lowcostp-adjvex = p-weight;p = p-nextarc;int main()int adjvexMAX_VERTEX_NUM;ALGraph G;G.kind = 2;CreateGraph(G);Prim(G, 0, adjvex);return 0;/*測試數據9 15 2ABCDEFGHIA B 32.8A I 18.2A H 12.1A C 44.6B C 5.9C D 21.3C E 41.1C G 56.4D E 67.3D F 98.7E F 85.6E G 10.5H G 52.5I H 8.7I F 79.2*/
全部分類
標準檢索
招標公告
免費下載資料庫
10000份+資源包
千萬vip文檔暢享下載
下載文檔文件編輯即用
網站精選百萬好案
百萬工程地產工作者都在用
微信掃一掃登錄
