graph.cpp

数据结构课程设计用C++实现图的遍历等！

#include "GRAPH.h"
#include<iomanip.h>

//////////////////////////////////////////////////////////////////////////////
//  构造函数
//  函数功能：初始化图
//  函数参数：无
//  参数返回值：无
Graph::Graph()
{
 T=new Tree[maxSize];            //申请空间
// matrix=new int[maxSize];
 list=new Node[maxSize];
 numVertex=0;
 numEdge=0;
 Mark=new bool[maxSize];  
 for(int i=0;i<maxSize;i++)
 {
  list[i].head=NULL;
 }
}

//////////////////////////////////////////////////////////////////////////////
// 析构函数
// 函数功能：将所有结点的空间释放
// 函数参数：无
// 参数返回值：无
Graph::~Graph()
{
 if(T)
  delete [] T;
// if(matrix)
//  delete [] matrix;
 if(Mark)
  delete [] Mark;
 if(list){
  for(int v=0;v<n();v++) 
  {
   while(list[v].head)    //释放单链表空间
   {
    Edge temp=list[v].head;   
    list[v].head=list[v].head->next;   
    delete temp;
   }
  }
     delete [] list;        //释放list空间
 }
}

//////////////////////////////////////////////////////////////////////////////
// 获取边函数
// 函数功能：返回顶点的第一条边
// 函数参数：int v
// 参数返回值：Edge
Edge Graph::first(int v)
{
 if(list[v].head!=NULL)
    return list[v].head;
 else cerr<<"此顶点无关联边!\n";
 return NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 获取边函数
// 函数功能：返回顶点的第一条边
// 函数参数：int v
// 参数返回值：Edge
int Graph::first2(int v)
{
 for(int pos=0;pos<numVertex;pos++)
  if(matrix[v][pos]!=INFINITY) 
   return pos;
 return NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 判边函数
// 函数功能：判定是否为图中的一条边
// 函数参数：Edge w
// 参数返回值：如果是图里的边，返回true;否则返回false
bool Graph::IsEdge(Edge w)
{
 return w!=NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 判图函数
// 函数功能：判定图是否为空
// 函数参数：无
// 参数返回值：如果图空，返回true;否则返回false
bool Graph::IsEmpty()
{
 if(numVertex==0)
 {
  cerr<<"图中没有顶点!\n";
  return false;
 }
 return true;
}


//////////////////////////////////////////////////////////////////////////////
// 获取边函数
// 函数功能：返回顶点的下一条边
// 函数参数：Edge w
// 参数返回值：Edge
Edge Graph::next(Edge w)
{
 if(w->next!=NULL)  
  return w->next;
 return NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 获取权值函数
// 函数功能：获取边(u,v)的权值
// 函数参数：int u,int v
// 参数返回值：返回边的权值
int Graph::weight(int u,int v)
{
 return matrix[u][v];
/* Edge temp=list[u].head;
 while(temp->v2!=v)            //查找边(u,v)
 {
  if(temp==NULL)
  {
   cerr<<"此两点没有边关联!\n";
   return INFINITY;
  }
  temp=temp->next;
 }
 return temp->weight;
*/
}

//////////////////////////////////////////////////////////////////////////////
// 获取权值函数
// 函数功能：获取边w的权值
// 函数参数：Edge w
// 参数返回值：返回边的权值
int Graph::weight(Edge w)
{
 return w->weight;
}

//////////////////////////////////////////////////////////////////////////////
// 建图函数
// 函数功能：建立一个图
// 函数参数：无
// 参数返回值：无
void Graph::CreateGraph()
{
 int i;
 cout<<"请输入图的顶点数:";
 cin>>numVertex;
// matrix=new int [numVertex*numVertex];
 for(i=0;i<n();i++)
     for(int j=0;j<n();j++)
    matrix[i][j]=INFINITY;
 cout<<"请输入图中边的条数:";
    cin>>numEdge;
 cout<<"建立无向(0)还是有向图(1):";
 char ChooseXiang;
 cin>>ChooseXiang;
 cout<<"建立不带权(0)还是带权图(1):";
 char ChooseWeight;
 cin>>ChooseWeight;
 cout<<"请输入各顶点信息:\n";
 for(i=0;i<numVertex;i++)
 {
  cout<<"第"<<i+1<<"点信息为:";
  cin>>list[i].Vertex;
 }
 if(ChooseWeight=='0')
 { 
  cout<<"请输入无权图关联边的起点和终点:\n"; 
  int start,end;
  for(i=0;i<numEdge;i++)
  {
   cout<<"第"<<i+1<<"条边起点和终点为:";
   cin>>start>>end;
         Edge Temp1;
            Temp1=new EdgeLink;         
         Temp1->v2=end;
   Temp1->weight=INFINITY;
          Temp1->next=list[start].head;
            list[start].head=Temp1;
        
   if(ChooseXiang=='0')             //建立有向图
   {
    Edge Temp2;           
    Temp2=new EdgeLink;         
    Temp2->v2=start;   
    Temp2->weight=INFINITY;        
    Temp2->next=list[end].head;      
    list[end].head=Temp2;
   }
  }
 }
 else               //if(ChooseWeight=='1') //建立带权图
 {
  cout<<"请输入有权图关联边的起点和终点:\n";
  int start,end;
  for(i=0;i<numEdge;i++)
  {
   cout<<"第"<<i+1<<"条边起点和终点为:";
   cin>>start>>end;
   cout<<"第"<<i+1<<"条边权为:";
   int weight;
   cin>>weight;
         Edge Temp1;
            Temp1=new EdgeLink;         
         Temp1->v2=end;
   Temp1->weight=weight;
          Temp1->next=list[start].head;
            list[start].head=Temp1;
   matrix[start][end]=weight;
        
   if(ChooseXiang=='0')             //建立有向图
   {
    Edge Temp2;           
    Temp2=new EdgeLink;         
    Temp2->v2=start;   
    Temp2->weight=weight;        
    Temp2->next=list[end].head;      
    list[end].head=Temp2;
    matrix[end][start]=weight;
   }
  }
 }
 cout<<"图的邻接矩阵为:\n";
 for(i=0;i<n();i++)
 {
  for(int j=0;j<n();j++)
  {
      if(matrix[i][j]==INFINITY)
    cout<<"∞   ";
   else cout<<matrix[i][j]<<"   ";
  }
  cout<<endl;
 }
}

//////////////////////////////////////////////////////////////////////////////
// 初始化函数
// 函数功能：对图进行初始化
// 函数参数：无
// 参数返回值：无
void Graph::initializtion()
{
 for(int v=0;v<n();v++)
  Mark[v]=false;
}

//////////////////////////////////////////////////////////////////////////////
// 遍历函数
// 函数功能：对图进行遍历
// 函数参数：char ch,int start
// 参数返回值：无
void Graph::Graph_traverse(char ch,int start)
{
 if(!IsEmpty())
 {
  cout<<" 请先建图!\n";
  CreateGraph();
  return;
 }
 initializtion();         //初始化
 switch(ch)
 {
 case 'D':
 case 'd':
     cout<<"深度优先遍历如下:\n";
  DFS(start);            //深度优先遍历
  cout<<endl;
  break;
 case 'B':
 case 'b':
  cout<<"广度优先遍历如下:\n";
  BFS(start);           //深度优先遍历
  break;
 } 
}

//////////////////////////////////////////////////////////////////////////////
// 深度优先遍历函数
// 函数功能：对图进行深度优先遍历
// 函数参数：int v
// 参数返回值：无
void Graph::DFS(int v)
{
 if(Mark[v]==false)
 {   
   //显示遍历信息
  cout<<setw(5)<<list[v].Vertex;  
 }
 Mark[v]=true;         //标记点v已访问过
 for(Edge w=first(v);IsEdge(w);w=next(w))       //访问下一条边
  if(Mark[w->v2]==false)       //未访问
   DFS(w->v2);     //深度优先遍历
}

//////////////////////////////////////////////////////////////////////////////
// 广度优先遍历函数
// 函数功能：对图进行广度优先遍历
// 函数参数：int start
// 参数返回值：无
void Graph::BFS(int start)
{ 
 Queue Q(n());           //定义n()长度的队列
 Q.EnQueue(start);        //起始位置入队
 Mark[start]=true;        //标记已访问过
 while(!Q.IsEmpty())       //队列不空
 {
  int v=Q.DelQueue();       //出对
     cout<<setw(5)<<list[v].Vertex;      //显示信息 
  for(Edge w=first(v);IsEdge(w);w=next(w))        //访问下一条边
   if(Mark[w->v2]==false)        //未访问
   {               
    Mark[w->v2]=true;            //标记访问
    Q.EnQueue(w->v2);           //入队
   }
 }
 cout<<endl;
}

//////////////////////////////////////////////////////////////////////////////
// 最小生成树函数
// 函数功能：生成一颗最小生成树
// 函数参数：int s
// 参数返回值：无
void Graph::Prim(int s)
{
 if(!IsEmpty())
 {
  cout<<" 请先建图!\n";
  CreateGraph();
  return;
 }
 initializtion();         //标记都未被访问过
 int *dist;
 dist=new int[numVertex];       //dist[i]记录V-TV中顶点i到TV中顶点的边的最小权
 int *V;
 V=new int[n()];        //V[i]为TV中的顶点，（V[I],I）为V-TV中的顶点i到TV中顶点的权最小的边
 for(int i=0;i<n();i++)      //初始化dist数组，所有顶点都属于V-TV集合
  dist[i]=INFINITY;
 dist[s]=0;               //为了将s加入生成树中作为“种子”，把s的dist值设为最小
 for(i=0;i<n();i++)          //循环n次，每次往T中加入一个新顶点
 {
  int v=minVertex(dist);      //选择V-TV中dist值最小的顶点v
     if(dist[v]==INFINITY) 
       return;              //有无法到达的顶点
     Mark[v]=true;           //将v加入生成树T中
     if(v!=s)             //如果v不是第一个顶点，则把连接到v的边加入生成树T中
      AddEdgetoT(V[v],v);
     for(int w=first2(v);w<numVertex;w++)        //重新计算V-TV中的顶点到
  {
         if(dist[w]>weight(v,w))                 //TV中的顶点的边的最小权
   {
       dist[w]=weight(v,w);
       V[w]=v;
   }
  }
 }
 for(i=0;i<n();i++)
 {
  if(i!=s)
  {
      cout<<"("<<T[i].x<<","<<T[i].y<<")\n";       //显示树中各边信息
       cout<<list[T[i].x].Vertex<<"-->"<<list[T[i].y].Vertex<<endl;
  }
 }
}

//////////////////////////////////////////////////////////////////////////////
// 选择最小权值的顶点函数
// 函数功能：选择最小权值的顶点
// 函数参数：int *D
// 参数返回值：选择最小权值的顶点
int Graph::minVertex(int *D)
{
 int v;
 for(int i=0;i<n();i++)    //查找v中第一个在V-TV中的顶点
  if(Mark[i]==false)
  {
   v=i;
   break;
  }
 for(i=v+1;i<n();i++)
  if((Mark[i]==false)&&(D[i]<D[v]))
   v=i;
  return v;
}

//////////////////////////////////////////////////////////////////////////////
// 连接边函数
// 函数功能：连接边(x,y)
// 函数参数：int x,int y
// 参数返回值：选择最小权值的顶点
void Graph::AddEdgetoT(int x,int y)
{
 T[y].x=x;
 T[y].y=y;
}