圖優(yōu)秀公開課課件

數(shù)據(jù)結構算法VisualC++6.0程序集侯識忠等編著中國水利水電出版社第六章圖6、0 圖的類定義和實現(xiàn)//圖的相關數(shù)據(jù)類型的定義graph.h//最多頂點數(shù)constintMaxV=10;//最大權值constintMaxValue=99;//定義鄰接表中的邊結點類型structedgenode{intadjvex;//鄰接點域intweight;//權值域edgenode*next;//指向下一個邊結點的鏈域};//定義鄰接表類型typedefedgenode**adjlist;//鄰接矩陣類定義classAdjMatrix{private:charg[MaxV];//頂點信息數(shù)組intsize;//當前頂點數(shù)intGA[MaxV][MaxV];//定義鄰接矩陣GAintnumE;//當前邊數(shù)public://構造函數(shù),初始化圖的鄰接矩陣AdjMatrix(intn,intk2);//判斷圖空否boolGraphEmpty(){returnsize==0;}//取當前頂點數(shù)intNumV(){returnsize;}//取當前邊數(shù)intNumEdges(){returnnumE;}//取頂點i的值charGetValue(constinti);//取弧<v1,v2>的權intGetWeight(constintv1,constintv2);//在位置pos處插入頂點VvoidInsertV(constchar&V,intpos);//對非連通圖進行深度優(yōu)先搜索voiddfsMatrix(intn,intk2);//對非連通圖進行廣度優(yōu)先搜索voidbfsMatrix(intn,intk2);};//圖的相關運算的實現(xiàn)graph.cpp#include"graph.h"http://構造函數(shù),初始化圖的鄰接矩陣AdjMatrix::AdjMatrix(intn,intk2){inti,j;if(k2==0){//初始化無(有)向無權圖for(i=0;i<n;i++)for(j=0;j<n;j++)GA[i][j]=0;}else{//初始化無(有)向有權圖for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)GA[i][j]=0;elseGA[i][j]=MaxValue;}size=numE=0;}//建立圖的鄰接矩陣voidAdjMatrix::CreateMatrix(intn,intk1,intk2)//k1為0則無向否則為有向,k2為0則無權否則為有權{inti,j,k,e,w;cout<<"輸入圖的總邊數(shù):";cin>>e;if(k1==0&&k2==0){//建立無向無權圖cout<<"輸入"<<e<<"條無向無權邊的起點和終點序號!"<<endl;for(k=1;k<=e;k++){cin>>i>>j;Check(n,i,j);GA[i][j]=GA[j][i]=1;}}elseif(k1==0&&k2!=0){//建立無向有權圖cout<<"輸入"<<e<<"條無向帶權邊的起點和終點序號及權值!"<<endl;for(k=1;k<=e;k++){cin>>i>>j>>w;Check(n,i,j);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0){//建立有向無權圖cout<<"輸入"<<e<<"條有向無權邊的起點和終點序號!"<<endl;for(k=1;k<=e;k++){cin>>i>>j;Check(n,i,j);GA[i][j]=1;}}elseif(k1!=0&&k2!=0){//建立有向有權圖cout<<"輸入"<<e<<"條有向有權邊的起點和終點序號及權值!"<<endl;for(k=1;k<=e;k++){cin>>i>>j>>w;Check(n,i,j);GA[i][j]=w;}}numE=e;cout<<"創(chuàng)建后的鄰接矩陣:\n";for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(4)<<GA[i][j];cout<<endl;}}//訪問初始點vicout<<g[i]<<':'<<i<<"";//標記初始點vi已訪問過visited[i]=true;//將已訪問過的初始點序號i入隊q[++rear]=i;//當隊列非空時進行循環(huán)處理while(front!=rear){//刪除隊首元素,第一次執(zhí)行時k的值為ifront=(front+1)%MaxLength;intk=q[front];//依次搜索vk的每一個可能的鄰接點for(intj=0;j<n;j++)if(k2==0){if(k!=j&&GA[k][j]!=0&&!visited[j]){//訪問一個未被訪問過的鄰接點vjcout<<g[j]<<':'<<j<<"";visited[j]=true;//標記vj已訪問過rear=(rear+1)%MaxLength;//頂點序號j入隊q[rear]=j;}}elseif(k!=j&&GA[k][j]!=MaxValue&&!visited[j]){//訪問一個未被訪問過的鄰接點vjcout<<g[j]<<':'<<j<<"";visited[j]=true;//標記vj已訪問過rear=(rear+1)%MaxLength;//頂點序號j入隊q[rear]=j;}}}//檢查輸入的邊序號是否越界,若越界則重輸voidAdjMatrix::Check(intn,int&i,int&j){while(1){if(i<0||i>=n||j<0||j>=n)cout<<"輸入有誤,請重輸!";elsereturn;cin>>i>>j;}}//由圖的鄰接矩陣得到圖的鄰接表voidAdjMatrix::graphChange(adjlist&GL,intn,intk2){inti,j;if(k2==0){for(i=0;i<n;i++){for(j=0;j<n;j++)if(GA[i][j]!=0){edgenode*p=newedgenode;p->adjvex=j;p->next=GL[i];GL[i]=p;cout<<'('<<i<<','<<p->adjvex<<")";}cout<<endl;}}else{for(i=0;i<n;i++){for(j=0;j<n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue){edgenode*p=newedgenode;p->adjvex=j;p->weight=GA[i][j];p->next=GL[i];GL[i]=p;cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<")";}cout<<endl;}}}if(k==i&&m<n){g[m]='A'+m;size++;cout<<g[m]<<'('<<i<<','<<j<<','<<GA[i][j]<<")";m++;}}cout<<endl;}g[n]='\0';}//取頂點i的值charAdjMatrix::GetValue(constinti){if(i<0||i>size){cerr<<"參數(shù)i越界!\n";exit(1);}returng[i];}//取弧<v1,v2>的權intAdjMatrix::GetWeight(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}returnGA[v1][v2];}//在位置pos處插入頂點VvoidAdjMatrix::InsertV(constchar&V,intpos){inti;if(size==MaxV){cerr<<"表已滿,無法插入!\n";exit(1);}if(pos<0||pos>size){cerr<<"參數(shù)pos越界!\n";exit(1);}for(i=size;i>pos;i--)g[i]=g[i-1];g[pos]=V;size++;}//插入弧<v1,v2>,權為weightvoidAdjMatrix::InsertEdge(constintv1,constintv2,intweight){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}GA[v1][v2]=weight;numE++;}//刪除頂點v與頂點v相關的所有邊charAdjMatrix::DeleteVE(constintv){for(inti=0;i<size;i++)for(intj=0;j<size;j++)if((i==v||j==v)&&GA[i][j]>0&&GA[i][j]<MaxValue){GA[i][j]=MaxValue;numE--;}if(size==0){cerr<<"表已空,無元素可刪!\n";exit(1);}if(v<0||v>size-1){cerr<<"參數(shù)v越界!\n";exit(1);}chartemp=g[v];for(i=v;i<size-1;i++)g[i]=g[i+1];size--;g[size]='\0';returntemp;}//刪除弧<v1,v2>voidAdjMatrix::DeleteEdge(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size||v1==v2){cerr<<"參數(shù)v1或v2出錯!\n";exit(1);}//圖的相關運算的測試graphM.cpp#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include"graph.cpp"voidmain(){cout<<"graphM.cpp運行結果:\n";//定義圖的點數(shù)及搜索起始點序號等intn,k,i;//k1為0則無向否則為有向,k2為0則無權否則為有權intk1,k2;//標記已訪問過的點bool*vis;//定義鄰接表adjlistAL;cout<<"輸入圖的點數(shù)n=";cin>>n;AL=newedgenode*[n];vis=newbool[n];if(!vis){cout<<"申請堆內(nèi)存失敗!\n";exit(1);}for(i=0;i<n;i++)vis[i]=false;cout<<"輸入選擇無向(權)與有向(權)圖的值k1,k2:";cin>>k1>>k2;//定義鄰接矩陣AdjMatrixA(n,k2);A.CreateMatrix(n,k1,k2);cout<<"出發(fā)點Vk的序號=";cin>>k;cout<<"\n輸出鄰接矩陣相應圖的每個頂點:\n";A.Creatgraph(n,k2);cout<<"當前的頂點數(shù)為:"<<A.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<A.NumEdges()<<endl;cout<<"圖的深度優(yōu)先搜索順序:\n";A.dfsMatrix(vis,k,n,k2);for(i=0;i<n;i++)vis[i]=false;cout<<"\n圖的廣度優(yōu)先搜索順序:\n";A.bfsMatrix(vis,k,n,k2);cout<<"\n輸出鄰接表的每個鄰接點:\n";for(i=0;i<n;i++)vis[i]=false;A.graphChange(AL,n,k2);單擊此處運行程序delete[]vis;A.DeleteEdge(0,2);A.DeleteEdge(2,0);cout<<"當前的頂點數(shù)為:"<<A.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<A.NumEdges()<<endl;cout<<"圖的深度優(yōu)先搜索順序:\n";A.dfsMatrix(n,k2);cout<<"\n圖的廣度優(yōu)先搜索順序:\n";A.bfsMatrix(n,k2);cin.get();cin.get();}//鄰接矩陣類定義classAdjMatrix{private:charg[MaxV];//頂點信息數(shù)組intsize;//當前頂點數(shù)intGA[MaxV][MaxV];//定義鄰接矩陣GAintnumE;//當前邊數(shù)public://構造函數(shù),初始化圖的鄰接矩陣AdjMatrix(intn,intk2);//判斷圖空否boolGraphEmpty(){returnsize==0;}//取當前頂點數(shù)intNumV(){returnsize;}//取當前邊數(shù)intNumEdges(){returnnumE;}//取頂點i的值charGetValue(constinti);//取弧<v1,v2>的權intGetWeight(constintv1,constintv2);//在位置pos處插入頂點VvoidInsertV(constchar&V,intpos);//插入弧<v1,v2>,權為weightvoidInsertEdge(constintv1,constintv2,intweight);//刪除頂點i與頂點i相關的所有邊charDeleteVE(constinti);//刪除弧<v1,v2>voidDeleteEdge(constintv1,constintv2);//建立圖的鄰接矩陣voidCreateMatrix(intn,intk1,intk2,RCWr[]);//k1為0則無向否則為有向,k2為0則無權否則為有權//從初始點vi出發(fā)深度優(yōu)先搜索由鄰接矩陣表示的圖voiddfsMatrix(bool*&visited,inti,intn,intk2);//從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接矩陣表示的圖voidbfsMatrix(bool*&visited,inti,intn,intk2);//由圖的鄰接矩陣得到圖的鄰接表voidgraphChange(adjlist&GL,intn,intk2);//檢查輸入的邊序號是否越界,若越界則重輸voidCheck(intn,int&i,int&j);//創(chuàng)建圖voidCreatgraph(intn,inte,RCWr[]);//對非連通圖進行深度優(yōu)先搜索voiddfsMatrix(intn,intk2);//對非連通圖進行廣度優(yōu)先搜索voidbfsMatrix(intn,intk2);};//圖的相關運算的實現(xiàn)graph0.cpp#include"graph0.h"http://構造函數(shù),初始化圖的鄰接矩陣AdjMatrix::AdjMatrix(intn,intk2){inti,j;if(k2==0){//初始化無(有)向無權圖for(i=0;i<n;i++)for(j=0;j<n;j++)GA[i][j]=0;}else{//初始化無(有)向有權圖for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)GA[i][j]=0;//cin>>i>>j>>w;Check(n,i,j);GA[i][j]=GA[j][i]=w;}}elseif(k1!=0&&k2==0){//建立有向無權圖cout<<"輸入"<<e<<"條有向無權邊的起點和終點序號!"<<endl;for(k=1;k<=e;k++){cin>>i>>j;Check(n,i,j);GA[i][j]=1;}}elseif(k1!=0&&k2!=0){//建立有向有權圖cout<<"輸入"<<e<<"條有向有權邊的起點和終點序號及權值!"<<endl;for(k=1;k<=e;k++){cin>>i>>j>>w;Check(n,i,j);GA[i][j]=w;}}cout<<"創(chuàng)建后的鄰接矩陣:\n";for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(4)<<GA[i][j];cout<<endl;}}//從初始點vi出發(fā)深度優(yōu)先搜索由鄰接矩陣表示的圖voidAdjMatrix::dfsMatrix(bool*&visited,inti,intn,intk2){cout<<g[i]<<':'<<i<<"";visited[i]=true;//標記vi已被訪問過for(intj=0;j<n;j++)//依次搜索vi的每個鄰接點if(k2==0){if(i!=j&&GA[i][j]!=0&&!visited[j])dfsMatrix(visited,j,n,k2);}elseif(i!=j&&GA[i][j]!=MaxValue&&!visited[j])dfsMatrix(visited,j,n,k2);}//從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接矩陣表示的圖voidAdjMatrix::bfsMatrix(bool*&visited,inti,intn,intk2){constintMaxLength=30;//定義一個隊列q,其元素類型應為整型intq[MaxLength]={0};//由圖的鄰接矩陣得到圖的鄰接表voidAdjMatrix::graphChange(adjlist&GL,intn,intk2){inti,j;if(k2==0){for(i=0;i<n;i++){for(j=0;j<n;j++)if(GA[i][j]!=0){edgenode*p=newedgenode;p->adjvex=j;p->next=GL[i];GL[i]=p;cout<<'('<<i<<','<<p->adjvex<<")";}cout<<endl;}}else{for(i=0;i<n;i++){for(j=0;j<n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue){edgenode*p=newedgenode;p->adjvex=j;p->weight=GA[i][j];p->next=GL[i];GL[i]=p;cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<")";}cout<<endl;}}}//創(chuàng)建圖voidAdjMatrix::Creatgraph(intn,inte,RCWr[]){inti,k;for(i=0;i<n;i++)InsertV('A'+i,i);for(k=0;k<e;k++)InsertEdge(r[k].row,r[k].col,r[k].weight);}//取頂點i的值charAdjMatrix::GetValue(constinti){if(i<0||i>size){cerr<<"參數(shù)i越界!\n";exit(1);}returng[i];}//取弧<v1,v2>的權intAdjMatrix::GetWeight(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}returnGA[v1][v2];}//在位置pos處插入頂點VvoidAdjMatrix::InsertV(constchar&V,intpos){inti;if(size==MaxV){cerr<<"表已滿,無法插入!\n";exit(1);}if(pos<0||pos>size){cerr<<"參數(shù)pos越界!\n";exit(1);}for(i=size;i>pos;i--)g[i]=g[i-1];g[pos]=V;size++;}//插入弧<v1,v2>,權為weightvoidAdjMatrix::InsertEdge(constintv1,constintv2,intweight){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}GA[v1][v2]=weight;numE++;}//刪除頂點v與頂點v相關的所有邊charAdjMatrix::DeleteVE(constintv){for(inti=0;i<size;i++)for(intj=0;j<size;j++)if((i==v||j==v)&&GA[i][j]>0&&GA[i][j]<MaxValue){GA[i][j]=MaxValue;numE--;}if(size==0){cerr<<"表已空,無元素可刪!\n";exit(1);}if(v<0||v>size-1){cerr<<"參數(shù)v越界!\n";exit(1);}chartemp=g[v];for(i=v;i<size-1;i++)g[i]=g[i+1];size--;g[size]='\0';returntemp;}//刪除弧<v1,v2>voidAdjMatrix::DeleteEdge(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size||v1==v2){cerr<<"參數(shù)v1或v2出錯!\n";exit(1);}GA[v1][v2]=MaxValue;numE--;}//對非連通圖進行深度優(yōu)先搜索voidAdjMatrix::dfsMatrix(intn,intk2){bool*vis=newbool[NumV()];inti;for(i=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])dfsMatrix(vis,i,n,k2);delete[]vis;}//對非連通圖進行廣度優(yōu)先搜索voidAdjMatrix::bfsMatrix(intn,intk2){bool*vis=newbool[NumV()];inti;for(i=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])bfsMatrix(vis,i,n,k2);delete[]vis;}//圖的相關運算的測試graph0M.cpp#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include"graph0.cpp"voidmain(){cout<<"graph0M.cpp運行結果:\n";RCWrcw[]={{0,1,1},{0,2,1},{1,3,1},{1,4,1},{2,5,1},{2,6,1},{1,0,1},{2,0,1},{3,1,1},{4,1,1},{5,2,1},{6,2,1}};//定義圖的點數(shù)及搜索起始點序號等intn,k,i,e=12;//k1為0則無向否則為有向,k2為0則無權否則為有權intk1,k2;//標記已訪問過的點bool*vis;//定義鄰接表adjlistAL;cout<<"輸入圖的點數(shù)n=";cin>>n;AL=newedgenode*[n];vis=newbool[n];if(!vis){cout<<"申請堆內(nèi)存失敗!\n";exit(1);}for(i=0;i<n;i++)vis[i]=false;cout<<"輸入選擇無向(權)與有向(權)圖的值k1,k2:";cin>>k1>>k2;//定義鄰接矩陣AdjMatrixA(n,k2);A.CreateMatrix(n,k1,k2,rcw);cout<<"出發(fā)點Vk的序號=";cin>>k;cout<<"\n輸出鄰接矩陣相應圖的每個頂點:\n";A.Creatgraph(n,e,rcw);cout<<"當前的頂點數(shù)為:"<<A.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<A.NumEdges()<<endl;cout<<"圖的深度優(yōu)先搜索順序:\n";A.dfsMatrix(vis,k,n,k2);for(i=0;i<n;i++)vis[i]=false;cout<<"\n圖的廣度優(yōu)先搜索順序:\n";A.bfsMatrix(vis,k,n,k2);cout<<"\n輸出鄰接表的每個鄰接點:\n";單擊此處運行程序for(i=0;i<n;i++)vis[i]=false;A.graphChange(AL,n,k2);delete[]vis;A.DeleteEdge(0,2);A.DeleteEdge(2,0);cout<<"當前的頂點數(shù)為:"<<A.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<A.NumEdges()<<endl;cout<<"圖的深度優(yōu)先搜索順序:\n";A.dfsMatrix(n,k2);cout<<"\n圖的廣度優(yōu)先搜索順序:\n";A.bfsMatrix(n,k2);cin.get();cin.get();}6、2圖的類定義和實現(xiàn)//圖的相關數(shù)據(jù)類型的定義graph1.h//最多頂點數(shù)constintMaxV=10;//定義鄰接表中的邊結點類型structedgenode{intadjvex;//鄰接點域intweight;//權值域edgenode*next;//指向下一個邊結點的鏈域edgenode(){}edgenode(intd,intw):adjvex(d),weight(w),next(NULL){}};structTop//頂點數(shù)組的元素類型{chardata;//頂點數(shù)據(jù)edgenode*adj;//鄰接表指針};structRCW{introw;intcol;intweight;};//鄰接表的類定義classAdjAdjoin{private:Topg[MaxV];//頂點數(shù)組intsize;//頂點個數(shù)intnumE;//當前邊的條數(shù)public:edgenode**GL;//定義鄰接表//構造函數(shù)AdjAdjoin(){}//構造函數(shù),初始化圖的鄰接表AdjAdjoin(edgenode**gl,intn);//判斷圖空否boolGraphEmpty(){returnsize==0;}//取當前頂點數(shù)intNumV(){returnsize;}//取當前邊數(shù)intNumEdges(){returnnumE;}//取頂點i的值charGetValue(constinti);//取弧<v1,v2>的權intGetWeight(constintv1,constintv2);//在位置pos處插入頂點VvoidInsertV(constchar&V);//插入弧<v1,v2>,權為weightvoidInsertEdge(constintv1,constintv2,intweight);//刪除頂點i與頂點i相關的所有邊voidDeleteVE(constintv);//刪除弧<v1,v2>voidDeleteEdge(constintv1,constintv2);//刪除圖的鄰接表voidDeleteAdjoin(intn);//建立圖voidCreatGraph(charV[],intn,RCWE[],inte);//建立圖的鄰接表voidCreateAdjoin(intn,intk1,intk2,RCWrcw[]);//從初始點vi出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖voiddfsAdjoin(bool*&visited,inti,intn);//從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖voidbfsAdjoin(bool*&visited,inti,intn);//檢查輸入的邊序號是否越界,若越界則重輸voidCheck(intn,int&i,int&j);//對非連通圖進行深度優(yōu)先搜索voiddfsAdjoin(intn);//對非連通圖進行廣度優(yōu)先搜索voidbfsAdjoin(intn);};//圖的相關運算的實現(xiàn)graph1.cpp#include"graph1.h"http://構造函數(shù),初始化圖的鄰接表AdjAdjoin::AdjAdjoin(edgenode**gL,intn){GL=gL;for(inti=0;i<n;i++){g[i].adj=GL[i]=NULL;}size=numE=0;}//建立圖的鄰接表voidAdjAdjoin::CreateAdjoin(intn,intk1,intk2,RCWrcw[]){inti,j,k,e,w;cout<<"輸入圖的總邊數(shù):";cin>>e;if(k1==0&&k2==0){//建立無向無權圖cout<<"輸入"<<e<<"條無向無權邊的起點和終點序號!"<<endl;for(k=1;k<=e;k++){cin>>i>>j;Check(n,i,j);//向序號i的單鏈表的表頭插入一個邊結點edgenode*p=newedgenode;p->adjvex=j;p->weight=1;p->next=GL[i];GL[i]=p;//向序號j的單鏈表的表頭插入一個邊結點p=newedgenode;p->adjvex=i;p->weight=1;cout<<'('<<p->adjvex<<','<<j<<','<<p->weight<<")\n";p->next=GL[j];GL[j]=p;}}elseif(k1==0&&k2!=0){//建立無向有權圖cout<<"輸入"<<e<<"條無向帶權邊的起點和終點序號及權值!"<<endl;for(k=0;k<e;k++){i=rcw[k].row;j=rcw[k].col;w=rcw[k].weight;//cin>>i>>j>>w;Check(n,i,j);//向序號i的單鏈表的表頭插入一個邊結點edgenode*p=newedgenode;p->adjvex=j;p->weight=w;p->next=GL[i];GL[i]=p;//向序號j的單鏈表的表頭插入一個邊結點p=newedgenode;p->adjvex=i;p->weight=w;p->next=GL[j];GL[j]=p;}}elseif(k1!=0&&k2==0){//建立有向無權圖cout<<"輸入"<<e<<"條有向無權邊的起點和終點序號!"<<endl;for(k=1;k<=e;k++){cin>>i>>j;Check(n,i,j);//向序號i的單鏈表的表頭插入一個邊結點edgenode*p=newedgenode;p->adjvex=j;p->weight=1;p->next=GL[i];GL[i]=p;}}elseif(k1!=0&&k2!=0){//建立有向有權圖cout<<"輸入"<<e<<"條有向有權邊的起點和終點序號及權值!"<<endl;for(k=1;k<=e;k++){cin>>i>>j>>w;Check(n,i,j);edgenode*p=newedgenode;p->adjvex=j;p->weight=w;p->next=GL[i];GL[i]=p;}}numE=e;size=n;}//從初始點vi出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖voidAdjAdjoin::dfsAdjoin(bool*&visited,inti,intn){cout<<g[i].data<<':'<<i<<"";visited[i]=true;//取vi鄰接表的表頭指針edgenode*p=GL[i];//依次搜索vi的每個鄰接點while(p!=NULL){intj=p->adjvex;//j為vi的一個鄰接點序號if(!visited[j])dfsAdjoin(visited,j,n);p=p->next;//使p指向vi單鏈表的下一個邊結點}}//從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖voidAdjAdjoin::bfsAdjoin(bool*&visited,inti,intn){constintMaxLength=30;//定義一個隊列q,其元素類型應為整型intq[MaxLength]={0};//定義隊首和隊尾指針intfront=0,rear=0;//訪問初始點vicout<<g[i].data<<':'<<i<<"";//標記初始點vi已訪問過visited[i]=true;//將已訪問過的初始點序號i入隊q[++rear]=i;//當隊列非空時進行循環(huán)處理while(front!=rear){//刪除隊首元素，第一次執(zhí)行時k的值為ifront=(front+1)%MaxLength;intk=q[front];//取vk鄰接表的表頭指針edgenode*p=GL[k];while(p!=NULL){//依次搜索vk的每一個鄰接點intj=p->adjvex;//vj為vk的一個鄰接點if(!visited[j]){//若vj沒有被訪問過則進行處理cout<<g[j].data<<':'<<j<<"";visited[j]=true;rear=(rear+1)%MaxLength;//頂點序號j入隊q[rear]=j;}p=p->next;//使p指向vk鄰接表的下一個邊結點}}}//檢查輸入的邊序號是否越界,若越界則重輸voidAdjAdjoin::Check(intn,int&i,int&j){while(1){if(i<0||i>=n||j<0||j>=n)cout<<"輸入有誤,請重輸!";elsereturn;cin>>i>>j;}}//取頂點i的值charAdjAdjoin::GetValue(constinti){if(i<0||i>size){cerr<<"參數(shù)i越界!\n";exit(1);}returng[i].data;}//取弧<v1,v2>的權intAdjAdjoin::GetWeight(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}edgenode*p=g[v1].adj;while(p!=NULL&&p->adjvex<v2)p=p->next;if(v2!=p->adjvex){cerr<<"邊<v1,v2>不存在!\n";exit(1);}returnp->weight;}//在位置pos處插入頂點VvoidAdjAdjoin::InsertV(constchar&V){g[size].data=V;size++;}//插入弧<v1,v2>,權為weightvoidAdjAdjoin::InsertEdge(constintv1,constintv2,intweight){if(v1<0||v1>size||v2<0||v2>size){cerr<<"參數(shù)v1或v2越界!\n";exit(1);}edgenode*q=newedgenode(v2,weight);//q->adjvex=v2;q->weight=weight;if(g[v1].adj==NULL)//第一次插入g[v1].adj=q;else//非第一次插入{edgenode*curr=g[v1].adj,*pre=NULL;while(curr!=NULL&&curr->adjvex<v2){pre=curr;curr=curr->next;}if(pre==NULL)//在第一個結點前插入{q->next=g[v1].adj;g[v1].adj=q;}else//在其他位置插入{q->next=pre->next;pre->next=q;}}numE++;}//刪除頂點v與頂點v相關的所有邊voidAdjAdjoin::DeleteVE(constintv){edgenode*pre,*curr;for(inti=0;i<size;i++){pre=NULL;//刪除頂點v的入邊curr=g[i].adj;while(curr!=NULL&&curr->adjvex<v){pre=curr;curr=curr->next;}if(pre==NULL&&curr->adjvex==v){g[i].adj=curr->next;//該出邊結點是鏈表的第一結點時deletecurr;numE--;}elseif(curr!=NULL&&curr->adjvex==v){pre->next=curr->next;//該出邊結點是鏈表的其他結點時deletecurr;numE--;}}edgenode*p=g[v].adj,*q;for(i=v;i<size-1;i++)g[i]=g[i+1];//刪除數(shù)組的頂點v元素numE--;while(p!=NULL)//刪除頂點v的所有出邊{q=p->next;deletep;//釋放空間p=q;numE--;}}//刪除弧<v1,v2>voidAdjAdjoin::DeleteEdge(constintv1,constintv2){if(v1<0||v1>size||v2<0||v2>size||v1==v2){cerr<<"參數(shù)v1或v2出錯!\n";exit(1);}edgenode*curr=g[v1].adj,*pre=NULL;while(curr!=NULL&&curr->adjvex<v2){pre=curr;curr=curr->next;}if(pre==NULL&&curr->adjvex==v2)//要刪除的結點是鏈表的第一結點{g[v1].adj=curr->next;deletecurr;numE--;}elseif(curr!=NULL&&curr->adjvex==v2)//不是鏈表的第一結點{pre->next=curr->next;deletecurr;numE--;}else{cerr<<"邊<v1,v2>不存在!\n";exit(1);}}//刪除圖的鄰接表voidAdjAdjoin::DeleteAdjoin(intn){inti;edgenode*p;for(i=0;i<n;i++){p=GL[i];while(p!=NULL){GL[i]=p->next;deletep;p=GL[i];}}delete[]GL;}//對非連通圖進行深度優(yōu)先搜索voidAdjAdjoin::dfsAdjoin(intn){bool*vis=newbool[NumV()];for(inti=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])dfsAdjoin(vis,i,n);delete[]vis;}//對非連通圖進行廣度優(yōu)先搜索voidAdjAdjoin::bfsAdjoin(intn){bool*vis=newbool[NumV()];for(inti=0;i<NumV();i++)vis[i]=false;for(i=0;i<NumV();i++)if(!vis[i])bfsAdjoin(vis,i,n);delete[]vis;}voidAdjAdjoin::CreatGraph(charV[],intn,RCWE[],inte){for(inti=0;i<n;i++)InsertV(V[i]);for(intk=0;k<e;k++)InsertEdge(E[k].row,E[k].col,E[k].weight);cout<<"輸出建立的圖:\n";for(i=0;i<n;i++)cout<<g[i].data<<"";cout<<endl;}//圖的相關運算的測試graph1M.cpp#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include"graph1.cpp"voidmain(){cout<<"graph1M.cpp運行結果:\n";chara[]={'A','B','C','D','E','F','G'};RCWrcw[]={{0,1,1},{0,2,1},{1,3,1},{1,4,1},{2,5,1},{2,6,1},{1,0,1},{2,0,1},{3,1,1},{4,1,1},{5,2,1},{6,2,1}};//定義圖的點數(shù)及搜索起始點序號等intn,k,i;//k1為0則無向否則為有向,k2為0則無權否則為有權intk1,k2;//標記已訪問過的點bool*vis;cout<<"輸入圖的點數(shù)n=";cin>>n;vis=newbool[n];if(!vis){cout<<"申請堆內(nèi)存失敗!\n";exit(1);}for(i=0;i<n;i++)vis[i]=false;cout<<"輸入選擇無向(權)與有向(權)圖的值k1,k2:";cin>>k1>>k2;edgenode**gl=newedgenode*[n];AdjAdjoinB(gl,n);B.CreatGraph(a,n,rcw,12);cout<<"創(chuàng)建鄰接表:\n";B.CreateAdjoin(n,k1,k2,rcw);cout<<"出發(fā)點Vk的序號=";cin>>k;cout<<"當前的頂點數(shù)為:"<<B.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<B.NumEdges()<<endl;cout<<"表的深度優(yōu)先搜索順序:\n";單擊此處運行程序B.dfsAdjoin(vis,k,n);cout<<endl;cout<<"表的廣度優(yōu)先搜索順序:\n";for(i=0;i<n;i++)vis[i]=false;B.bfsAdjoin(vis,k,n);cout<<endl;B.DeleteEdge(0,2);B.DeleteEdge(2,0);cout<<"當前的頂點數(shù)為:"<<B.NumV()<<endl;cout<<"當前的邊數(shù)為:"<<B.NumEdges()<<endl;cout<<"表的深度優(yōu)先搜索順序:\n";B.dfsAdjoin(n);cout<<endl;cout<<"表的廣度優(yōu)先搜索順序:\n";for(i=0;i<n;i++)vis[i]=false;B.bfsAdjoin(n);cout<<endl;B.DeleteAdjoin(n);cin.get();cin.get();}6、3利用普里姆算法求出用鄰接矩陣表示的圖的最小生成樹//利用普里姆算法求出用鄰接//矩陣表示的圖的最小生成樹//圖的相關數(shù)據(jù)類型的定義graph2.h//最多頂點數(shù)constintMaxV=10;//最大權值constintMaxValue=99;//定義邊集數(shù)組中的元素類型structedge{intfromvex;//起點域intendvex;//終點域intweight;//權域};structRCW{introw,col;intweight;};//類定義classadjMList{private:intnumE;//當前邊數(shù)intGA[MaxV][MaxV];//定義鄰接矩陣public://構造函數(shù),初始化圖的鄰接矩陣與邊集數(shù)組adjMList(edgeGE[],intn,inte);//建立無向帶權圖的鄰接矩陣voidCreateMatrix(intn,int&e,RCWr[]);//輸出邊集數(shù)組中的每條邊voidOutputEdgeSet(edgege[],inte);//根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組voidChangeEdgeSet(edgeGE[],intn,inte);//按升序排列圖的邊集數(shù)組voidSortEdgeSet(edgeGE[],inte);//利用普里姆算法從頂點v0出發(fā)求出用鄰接矩陣GA表//示的圖的最小生成樹,最小生成樹的邊集存于數(shù)組CT中voidPrim(edgeCT[],intn);//檢查輸入的邊序號是否越界,若越界則重輸voidCheck(intn,int&i,int&j);};//圖的運算的實現(xiàn)文件graph2.cpp#include"graph2.h"http://構造函數(shù),初始化圖的鄰接矩陣與邊集數(shù)組adjMList::adjMList(edgeGE[],intn,inte){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)GA[i][j]=0;elseGA[i][j]=MaxValue;for(i=0;i<e;i++)GE[i].weight=0;numE=0;}//輸出邊集數(shù)組中的每條邊voidadjMList::OutputEdgeSet(edgege[],inte){inti,k=0;cout<<"{";for(i=0;i<=e-2;i++)if(ge[i].weight>0){k++;cout<<'('<<ge[i].fromvex<<','<<ge[i].endvex;cout<<','<<ge[i].weight<<")";if(k%5==0)cout<<endl;}if(e>0&&ge[i].weight>0){cout<<'('<<ge[e-1].fromvex<<','<<ge[e-1].endvex;cout<<','<<ge[e-1].weight<<')';}cout<<'}'<<endl;}//建立無向帶權圖的鄰接矩陣voidadjMList::CreateMatrix(intn,int&e,RCWr[]){inti,j,k=0,w;cout<<"依次輸入無向帶權圖的每條邊的起點和終點"<<endl;cout<<"序號及權值!直到輸入權值為0的邊為止!"<<endl;do{i=r[k].row;j=r[k].col;w=r[k].weight;//cin>>i>>j>>w;Check(n,i,j);if(k==e-1)break;GA[i][j]=GA[j][i]=w;k++;}while(1);numE=e=k;cout<<"鄰接矩陣:\n";for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(4)<<GA[i][j];cout<<endl;}}//檢查輸入的邊序號是否越界,若越界則重輸voidadjMList::Check(intn,int&i,int&j){while(1){if(i<0||i>=n||j<0||j>=n)cout<<"輸入有誤,請重輸!";elsereturn;cin>>i>>j;}}//根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組voidadjMList::ChangeEdgeSet(edgeGE[],intn,inte){//假定只考慮無向圖的情況inti,j,k=0;for(i=0;i<n;i++)for(j=i+1;j<n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue){if(k==e){cout<<"數(shù)組GE下標越界!\n";exit(1);}GE[k].fromvex=i;GE[k].endvex=j;GE[k].weight=GA[i][j];k++;}}//按升序排列圖的邊集數(shù)組voidadjMList::SortEdgeSet(edgeGE[],inte){inti,j;edgex;for(i=1;i<=e-1;i++){x=GE[i];for(j=i-1;j>=0;j--)if(x.weight<GE[j].weight)GE[j+1]=GE[j];elsebreak;GE[j+1]=x;}}//利用普里姆算法從頂點v0出發(fā)求出用鄰接矩陣GA表示//的圖的最小生成樹,最小生成樹的邊集存于數(shù)組CT中voidadjMList::Prim(edgeCT[],intn){inti,j,k,min,t,m,w;//給CT賦初值，對應為v0依次到其余各頂點的邊f(xié)or(i=0;i<n-1;i++){CT[i].fromvex=0;CT[i].endvex=i+1;CT[i].weight=GA[0][i+1];}//進行n-1次循環(huán)，每次求出最小生成樹中的第k條邊f(xié)or(k=1;k<n;k++){//從CT[k-1]~CT[n-2]中查找最短邊CT[m]min=MaxValue;m=k-1;for(j=k-1;j<n-1;j++)if(CT[j].weight<min){min=CT[j].weight;m=j;}//把最短邊對調(diào)到第k-1下標位置edgetemp=CT[k-1];CT[k-1]=CT[m];CT[m]=temp;//把新并入最小生成樹T中的頂點序號賦給jj=CT[k-1].endvex;//修改有關邊，使T中到T外的每一個頂點各保持//一條到目前為止最短的邊f(xié)or(i=k;i<n-1;i++){t=CT[i].endvex;w=GA[j][t];if(w<CT[i].weight){CT[i].weight=w;CT[i].fromvex=j;}}}}//圖的相關運算的測試graph2M.cpp#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include"graph2.cpp"voidmain(){cout<<"graph2M.cpp運行結果:\n";單擊此處運行程序RCWrcw[20]={{0,1,50},{1,0,50},{0,2,60},{2,0,60},{1,3,65},{3,1,65},{1,4,40},{4,1,40},{2,3,52},{3,2,52},{2,6,45},{6,2,45},{3,4,50},{4,3,50},{3,5,30},{5,3,30},{3,6,42},{6,3,42},{4,5,70},{5,4,70}};intn,k;//定義圖的點數(shù)及邊數(shù)等cout<<"輸入圖的點數(shù)n=";cin>>n;cout<<"輸入圖的邊數(shù)k=";cin>>k;staticedgeAE[30],BE[30];//定義邊集數(shù)組adjMListA(AE,n,k);A.CreateMatrix(n,k,rcw);cout<<"輸出邊集數(shù)組中的每條邊:\n";A.ChangeEdgeSet(AE,n,k);A.OutputEdgeSet(AE,k);cout<<"輸出按升序排列的圖的邊集數(shù)組:\n";A.SortEdgeSet(AE,k);A.OutputEdgeSet(AE,k);A.Prim(BE,n);cout<<"輸出最小生成樹的邊集數(shù)組:\n";A.OutputEdgeSet(BE,k);cin.get();cin.get();}6、4利用克魯斯卡爾方法求邊集數(shù)組所示圖的最小生成樹//利用克魯斯卡爾方法求邊集//數(shù)組所示圖的最小生成樹//圖的相關數(shù)據(jù)類型的定義graph3.h//最多頂點數(shù)constintMaxV=10;//最大權值constintMaxValue=99;//定義鄰接表中的邊結點類型structedgenode{intadjvex;//鄰接點域intweight;//權值域edgenode*next;//指向下一個邊結點的鏈域};//定義鄰接表類型typedefedgenode**adjlist;//定義邊集數(shù)組中的元素類型structedge{intfromvex;//起點域intendvex;//終點域intweight;//權域};structRCW{introw,col;intweight;};//類定義classadjMList{private:intnumE;//當前邊數(shù)intGA[MaxV][MaxV];//定義鄰接矩陣public://構造函數(shù),初始化圖的鄰接矩陣與邊集數(shù)組adjMList(edgeGE[],intn,inte);//初始化圖的鄰接表voidInitGAdjoin(adjlist&GL,intn);//刪除圖的鄰接表voidDeleteAdjoin(adjlistGL,intn);//建立帶權圖的鄰接矩陣voidCreateMatrix(intn,int&e,RCWr[]);//輸出邊集數(shù)組中的每條邊voidOutputEdgeSet(edgege[],inte);//根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組voidChangeEdgeSet(edgeGE[],intn,inte);//利用克魯斯卡爾方法求邊集數(shù)組GE所示圖//的最小生成樹,樹中每條邊依次存于數(shù)組C中voidKruskal(edgeGE[],edgeC[],intn);//檢查輸入的邊序號是否越界,若越界則重輸voidCheck(intn,int&i,int&j);};//圖的運算的實現(xiàn)文件graph3.cpp#include"graph3.h"http://構造函數(shù),初始化圖的鄰接矩陣與邊集數(shù)組adjMList::adjMList(edgeGE[],intn,inte){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)GA[i][j]=0;elseGA[i][j]=MaxValue;for(i=0;i<e;i++)GE[i].weight=0;numE=0;}//初始化圖的鄰接表voidadjMList::InitGAdjoin(adjlist&GL,intn){GL=newedgenode*[n];for(inti=0;i<n;i++)GL[i]=NULL;}//刪除圖的鄰接表voidadjMList::DeleteAdjoin(adjlistGL,intn){inti;edgenode*p;for(i=0;i<n;i++){p=GL[i];while(p!=NULL){GL[i]=p->next;deletep;p=GL[i];}}delete[]GL;}//輸出邊集數(shù)組中的每條邊voidadjMList::OutputEdgeSet(edgege[],inte){inti,k=0;cout<<"{";for(i=0;i<=e-2;i++)if(ge[i].weight>0){k++;cout<<'('<<ge[i].fromvex<<','<<ge[i].endvex;cout<<','<<ge[i].weight<<")";if(k%5==0)cout<<endl;}if(e>0&&ge[i].weight>0){cout<<'('<<ge[e-1].fromvex<<','<<ge[e-1].endvex;cout<<','<<ge[e-1].weight<<')';}cout<<'}'<<endl;}//建立帶權圖的鄰接矩陣voidadjMList::CreateMatrix(intn,int&e,RCWr[]){inti,j,k=0,w;cout<<"依次輸入帶權圖的每條邊的起點和終點"<<endl;cout<<"序號及權值!直到輸入權值為0的邊為止!"<<endl;do{i=r[k].row;j=r[k].col;w=r[k].weight;//cin>>i>>j>>w;Check(n,i,j);if(k==e-1)break;GA[i][j]=GA[j][i]=w;k++;}while(1);numE=e=k;cout<<"鄰接矩陣:\n";for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(4)<<GA[i]