隨筆 - 251  文章 - 504  trackbacks - 0
          <2006年11月>
          2930311234
          567891011
          12131415161718
          19202122232425
          262728293012
          3456789

          本博客系個(gè)人收集材料及學(xué)習(xí)記錄之用,各類“大俠”勿擾!

          留言簿(14)

          隨筆分類

          收藏夾

          My Favorite Web Sites

          名Bloger

          非著名Bloger

          搜索

          •  

          積分與排名

          • 積分 - 204284
          • 排名 - 283

          最新評(píng)論

          若要在n個(gè)城市之間建設(shè)通訊網(wǎng)絡(luò),只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通訊網(wǎng)絡(luò),是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題。本單元的實(shí)驗(yàn)內(nèi)容主要是利用克魯斯卡爾算法求出網(wǎng)的最小生成樹(shù),并且以文本形式輸出樹(shù)中的各條邊以及他們的權(quán)值。

          #include<iostream>
          #include<stdlib.h>//產(chǎn)生隨機(jī)數(shù)組用
          #include<time.h> //同上
          ?#include<list>

          ?// 1) 帶權(quán)邊的類MyArc:

          class MyArc
          {
          public:
          ??? int m_beginVex;
          ??? int m_endVex;
          ??? int m_weight;
          ??? MyArc(int beginVex,int endVex,int weight);
          ??? MyArc(){}
          ??? bool operator < (const MyArc& arc)
          ??? {
          ??????? return m_weight<arc.m_weight;
          ??? }
          ??? bool operator == (const MyArc& arc)
          ??? {
          ??????? return m_weight==arc.m_weight;
          ??? }
          ??? bool operator > (const MyArc& arc)
          ??? {
          ??????? return m_weight>arc.m_weight;
          ??? }
          }? ;

          MyArc::MyArc(int beginVex,int endVex,int weight):m_beginVex(beginVex),m_endVex(endVex),m_weight(weight)
          {}
          //2) 表示圖的鄰接矩陣類Graph:
          class Graph
          {
          public:
          ??? int m_vexnum;
          ??? int m_arcnum;
          ??? int *m_pmatrix;
          public:
          ??? ~Graph();
          ??? Graph(int vexnum);
          ??? Graph(int vexnum,int *pmatrix);
          ??? void insert(MyArc arc);//按權(quán)值大小排序插入
          ??? bool bound(int x);?? //判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通
          };
          //構(gòu)造函數(shù)
          Graph::Graph(int vexnum)
          {
          ??? m_pmatrix=new int[vexnum*vexnum];
          ??? m_vexnum=vexnum;m_arcnum=0;
          ??? for(int i=0;i<vexnum*vexnum;++i)
          ??? m_pmatrix[i]=0;

          }

          //構(gòu)造函數(shù)
          Graph::Graph(int vexnum,int *pmatrix)
          {
          ??? m_vexnum=vexnum;
          ??? // m_arcnum=arcnum;
          ??? m_pmatrix=new int[m_vexnum*m_vexnum];
          ??? for(int i=0;i<m_vexnum*m_vexnum;++i)
          ??????? m_pmatrix[i]=pmatrix[i];
          }

          //測(cè)試 頂點(diǎn)x是否已與其他點(diǎn)連通
          bool Graph::bound(int x)
          {
          ??? for(int i=0;i<m_vexnum;++i) if(m_pmatrix[x+i*m_vexnum]!=0) return true;
          ??? return false;
          }

          //在鄰接表中連通 arc表示的邊,并且設(shè)置權(quán)
          void Graph::insert(MyArc arc)
          {
          ??? m_pmatrix[arc.m_beginVex*m_vexnum+arc.m_endVex]=arc.m_weight;
          ??? m_pmatrix[arc.m_endVex*m_vexnum+arc.m_beginVex]=arc.m_weight;
          ??? ++m_arcnum;
          }
          //析構(gòu)
          Graph::~Graph()
          {
          ??? delete[] m_pmatrix;
          }
          //3) 按權(quán)存儲(chǔ)邊的有序隊(duì)列類MyQueues:

          //邊按權(quán)值插入隊(duì)列中合適位置,
          class MyQueues
          {
          public:
          ??? list<MyArc> m_list;
          ??? MyQueues(){}
          ??? void insert(const MyArc& arc);//邊按權(quán)值插入隊(duì)列中合適位置,
          ??? void InsertGraph(const Graph &graph);//將圖的連通分量插入隊(duì)列
          ??? MyArc pop();
          };
          //邊出隊(duì)
          MyArc MyQueues::pop()
          {
          ??? MyArc arc=m_list.front();
          ??? m_list.pop_front();
          ??? return arc;
          }
          //邊按權(quán)值插入隊(duì)列中合適位置,
          void MyQueues::insert(const MyArc& arc)
          {
          ??? list<MyArc>::iterator pos;
          ??? pos=m_list.begin();
          ??? while(pos!=m_list.end())
          ??? {
          ??????? if(*pos>arc) break;
          ??????? else ++pos;
          ??? }
          ??? m_list.insert(pos,arc);
          }
          //將圖的連通分量插入隊(duì)列
          void MyQueues::InsertGraph(const Graph &graph)
          {
          ??? for(int i=0;i<graph.m_vexnum;++i)
          ??? {
          ??????? for(int j=i+1;j<graph.m_vexnum;++j)
          ????????????? if(graph.m_pmatrix[i*graph.m_vexnum+j]) insert(MyArc(i,j,graph.m_pmatrix[i*graph.m_vexnum+j]));
          ??? }
          }

          ?//5)判斷是否有回路的IsCycle函數(shù):
          bool IsCycle(Graph& graph, MyArc& arc)
          {
          ??? list<int> my_list;
          ??? my_list.push_back(arc.m_beginVex);
          ??? int *ps=new int[graph.m_vexnum];
          ??? for(int i=0;i<graph.m_vexnum;++i)
          ??????? ps[i]=0;
          ??? while(!my_list.empty())
          ??? {
          ??????? int x=my_list.front();
          ??????? ps[x]=1;
          ??????? my_list.pop_front();
          ??????? for(int i=0;i<graph.m_vexnum;++i)
          ??????? {
          ????????????? if(graph.m_pmatrix[i+x*graph.m_vexnum]!=0)
          ????????????? {
          ????????????????? if(i==arc.m_endVex) return true;
          ????????????????? if(ps[i]!=1) my_list.push_back(i);
          ????????????? }
          ??????? }
          ??? }
          ??? delete[] ps;
          ??? return false;
          }
          //4) kruskal算法:
          void kruskal(const Graph& graph,Graph& smtree)
          {
          ??? MyQueues arcqueues;//保存從小到大排列的邊
          ??? arcqueues.InsertGraph(graph);
          ??? MyArc myarc;//Arc表示邊的類型
          ??? int arcnum=0; //邊的個(gè)數(shù)
          ??? while(arcnum<graph.m_vexnum-1)
          ??? {
          ??????? myarc=arcqueues.pop();
          ??????? if(!IsCycle(smtree,myarc))
          ??????? {
          ????????????? smtree.insert(myarc);
          ????????????? ++arcnum;
          ??????? }
          ??? }
          }


          void SetMatrix(int vexnum,int *pmatrix)
          {
          ??? srand((unsigned)time(NULL));
          ??? for(int i=0;i<vexnum;++i)//產(chǎn)生隨機(jī)權(quán)值矩陣
          ??? {
          ??????? for(int j=i;j<vexnum;++j)
          ??????? {
          ????????????? if(j==i)
          ????????????? {
          ????????????????? pmatrix[i*vexnum+j]=0;
          ????????????????? continue;
          ????????????? }
          ????????????? int rnum=rand();rnum%=99;rnum++;//產(chǎn)生1~99的隨機(jī)整數(shù)作為邊的權(quán)值
          ????????????? pmatrix[i*vexnum+j]=rnum;
          ????????????? pmatrix[j*vexnum+i]=rnum;
          ??????? }
          ??? }
          ??? cout<<"***隨機(jī)產(chǎn)生的各邊權(quán)值矩陣 [頂點(diǎn)數(shù)為 "<<vexnum<<"] ****\n";
          ? for(int i=0;i<vexnum;++i)//輸出隨機(jī)權(quán)值矩陣
          ??? {
          ??????? for(int j=0;j<vexnum;++j)
          ??????? {
          ????????????? cout<<pmatrix[i*vexnum+j]<<"\t";
          ??????? }
          ??????? cout<<endl;
          ??? }

          }

          void SmallestTreeOutput(const Graph& smtree)
          {
          ??? cout<<"最小生成樹(shù):"<<endl;
          ??? for(int i=0;i<smtree.m_vexnum;++i)//輸出最小樹(shù)
          ??????? for(int j=i+1;j<smtree.m_vexnum;++j)
          ????????????? if(smtree.m_pmatrix[i*smtree.m_vexnum+j])
          ????????????????? cout<<'('<<i<<','<<j<<','<<smtree.m_pmatrix[i*smtree.m_vexnum+j]<<')'<<endl;
          }

          ?

          void main()
          {
          ??? char i;
          ??? cout<<"請(qǐng)輸入頂點(diǎn)數(shù)目:";
          ??? cin>>i;
          ? int vex=i-'0';
          ??? int *matrix=new int[vex*vex];
          ??? cout<<endl;
          ??? SetMatrix(vex,matrix);
          ??? Graph graph(vex,matrix),smtree(vex);
          ??? kruskal(graph,smtree);
          ??? SmallestTreeOutput(smtree);
          ??? delete []matrix;
          }


          結(jié)果輸出:
          請(qǐng)輸入頂點(diǎn)數(shù)目:6

          ***隨機(jī)產(chǎn)生的各邊權(quán)值矩陣 [頂點(diǎn)數(shù)為 6] ****
          0?????? 64????? 7?????? 15????? 22????? 43
          64????? 0?????? 72????? 86????? 53????? 40
          7?????? 72????? 0?????? 53????? 37????? 22
          15????? 86????? 53????? 0?????? 87????? 82
          22????? 53????? 37????? 87????? 0?????? 9
          43????? 40????? 22????? 82????? 9?????? 0
          最小生成樹(shù):
          (0,2,7)
          (0,3,15)
          (0,4,22)
          (1,5,40)
          (4,5,9)


          FeedBack:
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù)  2006-12-30 14:38 jdf
          好像有點(diǎn)問(wèn)題,我用vc++6.0編譯不過(guò)  回復(fù)  更多評(píng)論
            
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù)  2006-12-30 18:41 matthew[匿名]
          我試過(guò)了,能夠編譯運(yùn)行。編譯環(huán)境:C-Free3.5  回復(fù)  更多評(píng)論
            
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù)  2007-04-13 08:53 45655
          請(qǐng)教用java 怎么編寫————最小生成樹(shù)的應(yīng)用。
          【例】網(wǎng)絡(luò)G表示n個(gè)城市之間的通信線路網(wǎng)(其中頂點(diǎn)表示城市,邊表示兩個(gè)城市之間的通信線路,邊上的權(quán)值表示線路的長(zhǎng)度或造價(jià)。可通過(guò)求該網(wǎng)絡(luò)的最小生成樹(shù)達(dá)到求解通信線路或總代價(jià)最小的最佳方案。

          問(wèn)題的實(shí)現(xiàn):
          要求用java語(yǔ)言動(dòng)態(tài)實(shí)現(xiàn)此過(guò)程,步驟:
          (1)首先在文本框內(nèi)輸入城市的個(gè)數(shù),即頂點(diǎn)數(shù);
          (2)根據(jù)輸入的頂點(diǎn)個(gè)數(shù)點(diǎn)擊鼠標(biāo)分別顯示出①②③④⑤;
          (3)在文本框內(nèi)分別輸入兩個(gè)城市的名字以及權(quán)值,與此同時(shí),在圖中自動(dòng)畫出兩點(diǎn)之間的連線,并在線的中央顯示其權(quán)值。

            回復(fù)  更多評(píng)論
            
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù)  2007-04-13 08:53 45655
          謝謝拉
            回復(fù)  更多評(píng)論
            
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù)  2007-06-01 13:21 wyx860216@sina.com
          請(qǐng)教下面這題的C語(yǔ)言源程序:

          網(wǎng)絡(luò)G表示n個(gè)城市之間的通信線路網(wǎng)(其中頂點(diǎn)表示城市,邊表示兩個(gè)城市之間的通信線路,邊上的權(quán)值表示線路的長(zhǎng)度或造價(jià)。可通過(guò)求該網(wǎng)絡(luò)的最小生成樹(shù)達(dá)到求解通信線路或總代價(jià)最小的最佳方案。

          要求用visual C++編寫..

          謝謝!
            回復(fù)  更多評(píng)論
            
          # re: 數(shù)據(jù)結(jié)構(gòu)之圖及其應(yīng)用—網(wǎng)的最小生成樹(shù) [未登錄](méi) 2008-12-22 20:37 ZY
          萬(wàn)分感謝,寫的很精彩,無(wú)私的博主!  回復(fù)  更多評(píng)論
            
          主站蜘蛛池模板: 疏勒县| 隆尧县| 乐安县| 武胜县| 张掖市| 海盐县| 巫溪县| 定远县| 西宁市| 吉林省| 天全县| 禄丰县| 阳泉市| 德钦县| 鄂伦春自治旗| 当雄县| 洛南县| 吕梁市| 怀仁县| 乡宁县| 南投市| 广河县| 长顺县| 郧西县| 如皋市| 积石山| 万源市| 霍林郭勒市| 广昌县| 永安市| 武川县| 文山县| 浦江县| 海丰县| 本溪| 霍山县| 屏山县| 静宁县| 台东市| 锡林郭勒盟| 沙洋县|