graph1m.txt

数据结构的c++实现,源代码全部在C++builder中运行.第六部分

//图的相关数据类型的定义graph1.h
//最多顶点数
const int MaxV=10;
//定义邻接表中的边结点类型
struct edgenode {
 int adjvex;     //邻接点域
 int weight;     //权值域
 edgenode* next; //指向下一个边结点的链域
 edgenode(){}
 edgenode(int d,int w):adjvex(d),weight(w),next(NULL){}
};
struct Top //顶点数组的元素类型
{char data;//顶点数据
 edgenode *adj;//邻接表指针
};
struct RCW
{int row;
 int col;
 int weight;
};
//邻接表的类定义
class AdjAdjoin
{private:
  Top g[MaxV];//顶点数组
  int size;   //顶点个数
  int numE;   //当前边的条数
 public:
  edgenode **GL;//定义邻接表
  //构造函数
  AdjAdjoin() {}
  //构造函数,初始化图的邻接表
  AdjAdjoin(edgenode **gl,int n);
  //判断图空否
  bool GraphEmpty() {return size==0;}
  //取当前顶点数
  int NumV() {return size;}
  //取当前边数
  int NumEdges() {return numE;}
  //取顶点i的值
  char GetValue(const int i);
  //取弧<v1,v2>的权
  int GetWeight(const int v1,const int v2);
  //在位置pos处插入顶点V
  void InsertV(const char &V);
  //插入弧<v1,v2>,权为weight
  void InsertEdge(const int v1,const int v2,int weight);
  //删除顶点i与顶点i相关的所有边
  void DeleteVE(const int v);
  //删除弧<v1,v2>
  void DeleteEdge(const int v1,const int v2);
  //删除图的邻接表
  void DeleteAdjoin(int n);
  //建立图
  void CreatGraph(char V[],int n,RCW E[],int e);
  //建立图的邻接表
  void CreateAdjoin(int n,int k1,int k2,RCW rcw[]);
  //从初始点vi出发深度优先搜索由邻接表GL表示的图
  void dfsAdjoin(bool*& visited,int i,int n);
  //从初始点vi出发广度优先搜索由邻接表GL表示的图
  void bfsAdjoin(bool*& visited,int i,int n);
  //检查输入的边序号是否越界,若越界则重输
  void Check(int n,int& i,int& j);
   //对非连通图进行深度优先搜索
  void dfsAdjoin(int n);
  //对非连通图进行广度优先搜索
  void bfsAdjoin(int n);
};
//图的相关运算的实现graph1.cpp
#include"graph1.h"
//构造函数,初始化图的邻接表
AdjAdjoin::AdjAdjoin(edgenode **gL,int n)
{GL=gL;
 for(int i=0;i<n;i++)
  {g[i].adj=GL[i]=NULL;}
 size=numE=0;
}
//建立图的邻接表
void AdjAdjoin::CreateAdjoin(int n,int k1,int k2,RCW rcw[])
{int i,j,k,e,w;
 cout<<"输入图的总边数:";
  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=new edgenode;
   p->adjvex=j; p->weight=1;
   p->next=GL[i];
   GL[i]=p;//向序号j的单链表的表头插入一个边结点
   p=new edgenode;
   p->adjvex=i; p->weight=1;
   cout<<'('<<p->adjvex<<','<<j<<','<<p->weight<<")\n";
   p->next=GL[j];
   GL[j]=p;}
 }
 else if(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=new edgenode;
   p->adjvex=j; p->weight=w;
   p->next=GL[i];
   GL[i]=p;
   //向序号j的单链表的表头插入一个边结点
   p=new edgenode;
   p->adjvex=i;p->weight=w;
   p->next=GL[j];
   GL[j]=p;}
 }
 else if(k1!=0&&k2==0) {  //建立有向无权图
   cout<<"输入"<<e<<"条有向无权边的起点和终点序号!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j;
    Check(n,i,j);
    //向序号i的单链表的表头插入一个边结点
    edgenode* p=new edgenode;
    p->adjvex=j; p->weight=1;
    p->next=GL[i];
    GL[i]=p;}
 }
 else if(k1!=0&&k2!=0) {  //建立有向有权图
   cout<<"输入"<<e
       <<"条有向有权边的起点和终点序号及权值!"<<endl;
   for(k=1; k<=e; k++) {
    cin>>i>>j>>w;
    Check(n,i,j);
    edgenode* p=new edgenode;
    p->adjvex=j; p->weight=w;
    p->next=GL[i];
    GL[i]=p;}}
 numE=e;size=n;   
}
//从初始点vi出发深度优先搜索由邻接表GL表示的图
void AdjAdjoin::dfsAdjoin(bool*& visited,int i,int n)
{cout<<g[i].data<<':'<<i<<"  ";
 visited[i]=true;
 //取vi邻接表的表头指针
 edgenode *p=GL[i];
 //依次搜索vi的每个邻接点
 while (p!=NULL) {
   int j=p->adjvex;//j为vi的一个邻接点序号
   if(!visited[j])
   dfsAdjoin(visited,j,n);
   p=p->next;  //使p指向vi单链表的下一个边结点
}}
//从初始点vi出发广度优先搜索由邻接表GL表示的图
void AdjAdjoin::bfsAdjoin(bool*& visited,int i,int n)
{const int  MaxLength=30;
 //定义一个队列q,其元素类型应为整型
 int q[MaxLength]={0};
 //定义队首和队尾指针
 int front=0, rear=0;
 //访问初始点vi
 cout<<g[i].data<<':'<<i<<"  ";
 //标记初始点vi已访问过
 visited[i]=true;
 //将已访问过的初始点序号i入队
 q[++rear]=i;
 //当队列非空时进行循环处理
 while(front!=rear) {
  //删除队首元素，第一次执行时k的值为i
  front=(front+1)%MaxLength;
  int k=q[front];
  //取vk邻接表的表头指针
  edgenode* p=GL[k];
  while(p!=NULL)
    {//依次搜索vk的每一个邻接点
     int j=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邻接表的下一个边结点
}}}
//检查输入的边序号是否越界,若越界则重输
void AdjAdjoin::Check(int n,int& i,int& j)
{while(1) {
  if(i<0||i>=n||j<0||j>=n)
    cout<<"输入有误,请重输!";
  else return;
  cin>>i>>j;
 }
}
//取顶点i的值
char AdjAdjoin::GetValue(const int i)
{if(i<0||i>size)
  {cerr<<"参数i越界!\n";exit(1);}
 return g[i].data;
}
//取弧<v1,v2>的权
int AdjAdjoin::GetWeight(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"参数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);}
 return p->weight; 
}
//在位置pos处插入顶点V
void AdjAdjoin::InsertV(const char &V)
{g[size].data=V;
 size++; 
}
//插入弧<v1,v2>,权为weight
void AdjAdjoin::InsertEdge(const int v1,const int v2,int weight)
{if(v1<0||v1>size||v2<0||v2>size)
  {cerr<<"参数v1或v2越界!\n";exit(1);}
 edgenode *q=new edgenode(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相关的所有边
void AdjAdjoin::DeleteVE(const int v)
{edgenode *pre,*curr;
 for(int i=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; //该出边结点是链表的第一结点时
    delete curr;
    numE--;
   }
  else if(curr!=NULL&&curr->adjvex==v)
   {pre->next=curr->next;//该出边结点是链表的其他结点时
    delete curr;
    numE--;
   }
 }
 edgenode *p=g[v].adj,*q;
 for(int i=v;i<size-1;i++)
  g[i]=g[i+1]; //删除数组的顶点v元素
 numE--;
 while(p!=NULL)//删除顶点v的所有出边
 {q=p->next;
  delete p;    //释放空间
  p=q;
  numE--;
 }
}
//删除弧<v1,v2>
void AdjAdjoin::DeleteEdge(const int v1,const int v2)
{if(v1<0||v1>size||v2<0||v2>size||v1==v2)
  {cerr<<"参数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;
    delete curr;
    numE--;
   }
  else if(curr!=NULL&&curr->adjvex==v2)//不是链表的第一结点
   {pre->next=curr->next;
    delete curr;
    numE--;
   }
  else
   {cerr<<"边<v1,v2>不存在!\n";exit(1);}
}
//删除图的邻接表
void AdjAdjoin::DeleteAdjoin(int n)
{int i;
 edgenode* p;
 for(i=0;i<n;i++)
 {p=GL[i];
  while(p!=NULL)
   {GL[i]=p->next;
    delete p;p=GL[i];
   }
 }
 delete []GL;
}
//对非连通图进行深度优先搜索
void AdjAdjoin::dfsAdjoin(int n)
{bool *vis=new bool[NumV()];
 for(int i=0;i<NumV();i++) vis[i]=false;
 for(int i=0;i<NumV();i++)
  if(!vis[i]) dfsAdjoin(vis,i,n);
 delete []vis;
}
//对非连通图进行广度优先搜索
void AdjAdjoin::bfsAdjoin(int n)
{bool *vis=new bool[NumV()];
 for(int i=0;i<NumV();i++) vis[i]=false;
 for(int i=0;i<NumV();i++)
  if(!vis[i]) bfsAdjoin(vis,i,n);
 delete []vis;
}
void AdjAdjoin::CreatGraph(char V[],int n,RCW E[],int e)
{for(int i=0;i<n;i++) InsertV(V[i]);
 for(int k=0;k<e;k++)
  InsertEdge(E[k].row,E[k].col,E[k].weight);
 cout<<"输出建立的图:\n";
 for(int i=0;i<n;i++)
  cout<<g[i].data<<"  ";
 cout<<endl;  
}  
//图的相关运算的测试graph1M.cpp
#include<iostream.h>
#include<iomanip.h>
#include "graph1.cpp"
void main()
{cout<<"graph1M.cpp运行结果:\n";
 char a[]={'A','B','C','D','E','F','G'};
 RCW rcw[]={{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}};
 //定义图的点数及搜索起始点序号等
 int n,k,i,j;
 //k1为0则无向否则为有向,k2为0则无权否则为有权
 int k1,k2;
 //标记已访问过的点
 bool *vis;
 cout<<"输入图的点数n=";cin>>n;
 vis=new bool[n];
 if(!vis) {cout<<"申请堆内存失败!\n";exit(1);}
 for(i=0;i<n;i++) vis[i]=false;
 cout<<"输入选择无向(权)与有向(权)图的值k1,k2:";
 cin>>k1>>k2;
 edgenode **gl=new edgenode*[n];
 AdjAdjoin B(gl,n);
 B.CreatGraph(a,n,rcw,12);
 cout<<"创建邻接表:\n";
 B.CreateAdjoin(n,k1,k2,rcw);
 cout<<"出发点Vk的序号=";cin>>k;
 cout<<"当前的顶点数为:"<<B.NumV()<<endl;
 cout<<"当前的边数为:"<<B.NumEdges()<<endl;
 cout<<"表的深度优先搜索顺序:\n";
 B.dfsAdjoin(vis,k,n);cout<<endl;
 cout<<"表的广度优先搜索顺序:\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<<"当前的顶点数为:"<<B.NumV()<<endl;
 cout<<"当前的边数为:"<<B.NumEdges()<<endl;
 cout<<"表的深度优先搜索顺序:\n";
 B.dfsAdjoin(n);cout<<endl;
 cout<<"表的广度优先搜索顺序:\n";
 for(i=0;i<n;i++) vis[i]=false;
 B.bfsAdjoin(n);cout<<endl;
 B.DeleteAdjoin(n);
 cin.get();cin.get();}
graph1M.cpp运行结果:
输入图的点数n=7
输入选择无向(权)与有向(权)图的值k1,k2:0  1
输出建立的图:
A  B  C  D  E  F  G  
创建邻接表:
输入图的总边数:12
输入12条无向带权边的起点和终点序号及权值!
出发点Vk的序号=0
当前的顶点数为:7
当前的边数为:12
表的深度优先搜索顺序:
A:0  C:2  G:6  F:5  B:1  E:4  D:3  
表的广度优先搜索顺序:
A:0  C:2  B:1  G:6  F:5  E:4  D:3  
当前的顶点数为:7
当前的边数为:10
表的深度优先搜索顺序:
A:0  C:2  G:6  F:5  B:1  E:4  D:3  
表的广度优先搜索顺序:
A:0  C:2  B:1  G:6  F:5  E:4  D:3