//                           图的建立和深度搜索和广度搜索的实现#include <iostream>#include <queue>using namespace std;const int UNVISITED=1000;const int VISITED=100; class Graph{public: virtual int n()=0; virtual int e()=0; virtual int first(int)=0; virtual int next(int,int)=0; virtual void setEdge(int, int, int)=0; virtual void delEdge(int, int)=0; virtual int weight(int, int)=0; virtual int getMark(int)=0; virtual void setMark(int,int)=0;};class Edge{public: int vertex,weight; Edge() {  vertex=-1;  weight=-1; } Edge(int v,int w) {  vertex=v;  weight=w; }}; class Graphm:public Graph{private: int numVertex,numEdge; int **matrix; int *mark;public: Graphm(int numVert) {  int i,j;  numVertex=numVert;  numEdge=0;  mark=new int[numVert];  for(i=0;i<numVertex;i++)   mark[i]=UNVISITED;  matrix=(int **)new int*[numVertex];  for(i=0;i<numVertex;i++)   matrix[i]=new int[numVertex];  for(i=0;i<numVertex;i++)   for(j=0;j<numVertex;j++)    matrix[i][j]=0; } ~Graphm() {  for(int i=0;i<numVertex;i++)   delete matrix[i];  delete matrix; } int n(); int e(); int first(int v); int next(int v1,int v2); void setEdge(int v,int w,int wgt); void delEdge(int v,int w); int weight(int v,int w); int getMark(int v); void setMark(int v,int w); void DFS(Graphm* G,int v); void graphTraverse(Graphm *G,int DorB); void BFS(Graphm* G,int v); void PreVisit(Graphm* G,int v); void PosVisit(Graphm* G,int V);}; int Graphm::n(){ return numVertex;} int Graphm::e(){ return numEdge;} int Graphm::first(int v){ int i; for(i=0;i<numVertex;i++)  if(matrix[v][i]!=0)   return i; return i;} int Graphm::next(int v1,int v2){ for(int i=v2+1;i<numVertex;i++)  if(matrix[v1][i]!=0)   return i; return i;} //set Edge(v1,v2) to wgtvoid Graphm::setEdge(int v1,int v2,int wgt){ if(wgt>0)  cout<<"Illegal weight value"<<endl; if(matrix[v1][v2]==0)  numEdge++; matrix[v1][v2]=wgt;} void Graphm::delEdge(int v1,int v2){ if(matrix[v1][v2]==0)  numEdge--; matrix[v1][v2]=0;} int Graphm::weight(int v1,int v2){ return matrix[v1][v2];} int Graphm::getMark(int v){ return mark[v];} void Graphm::setMark(int v,int val){ mark[v]=val;} void Graphm::graphTraverse(Graphm* G,int DorB){ for(int v=0;v<G->n();v++)  G->setMark(v,UNVISITED); for(v=0;v<G->n();v++)  if(G->getMark(v)==UNVISITED)   if(DorB>0)     DFS(G,v);   else     BFS(G,v);} void Graphm::DFS(Graphm* G,int v){  G->setMark(v,VISITED);  for(int w=G->first(v);w<G->n();w=G->next(v,w))  if(G->getMark(w)==UNVISITED)   DFS(G,w); cout<<v<<" ";} void Graphm::BFS(Graphm* G,int v){ using std::queue; queue<int> Q; int val; G->PreVisit(G,v); Q.push(v); G->setMark(v,VISITED); while(Q.empty()!=NULL) {  val=Q.front();  Q.pop();  for(int w=G->first(v);w<G->n();w=G->next(v,w))   if(G->getMark(v)==UNVISITED)   {     G->setMark(w,VISITED);      Q.push(w);   } }} void Graphm::PreVisit(Graphm* G,int v){ cout<<v<<" ";} void Graphm::PosVisit(Graphm* G,int v){  cout<<v<<endl;}     int main(){ Graphm G(10); int val,v1,v2,BorD; cout<<"Enter the 10 matrix graph"<<endl; cout<<"If there is a edge you can enter 1:"<<endl; for(int i=0;i<10;i++) {  cin>>v1;  cin>>v2;  cin>>val;  G.setEdge(v1,v2,val); } cout<<"Enter a interge '1' or '0':"<<endl; cout<<"if you Enter 1 will be print by DFS,else BFS"<<endl; cin>>BorD; G.graphTraverse(&G,BorD); return 0;}           对于图的建立我采用设置边的方法.我也是采用矩阵的方法实现.由于对C++的很多语法的 忘记.有的地方都没有很完善的写好C++.这个程序只能在VC6.0中运行.    

评论