图基本操作的实现 一、【实验内容】【问题描述】（1）、选择邻接表作为无向图的存储结构，设计一个程序实现图的基本操作（包括输出、广度遍历、深度遍历）（2）、选择邻接矩阵作为无向图的存储结构，分别设计用prim求最小生成树和用克鲁斯卡尔求最小生成树的算法。 【基本要求】：程序的菜单功能项如下：1、 初始化（图的邻接表存储为空）//可以不要该选项2、 图邻接表的建立              //针对的图为不带权图3、 深度优先遍历                //针对的存储结构是2所建立起来的邻接表4、 广度优先遍历                //针对的存储结构是2所建立起来的邻接表5、 最小生成树（prim/克鲁斯卡尔）//该项操作要先建立带权图的邻接矩阵，然后才应用prim方法6、 退出                二、实验目的1． 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2． 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。3． 复习类的操作和多文件的实现 三、实验文档：                  图基本操作的实现一、 需求分析1、通过图操作的实现，把一些实际生活中的具体的事物抽象出来。2、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。本演示程序中，用户可以输入键盘中相应的字符，选择相应的功能，然后程序进行对应的操作。3、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。4、程序执行的命令包括：　1) 图邻接表的建立(C)　　　　2) 深度优先遍历（D）　　3) 广度优先遍历(B)　4) 最小生成树（prim）(P)　5) 退出(Q)二、概要设计为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为ADT Queue{数据对象：DataType front,rear;        int *Vec;               //对列        int MaxSize;            //对列最大长度数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}基本操作P：：Queue(int size);          //构造函数~Queue();               //析构函数EnQueue(DataType x);      初始条件： 操作结果：元素x入队DelQueue();             初始条件： 队列已存在操作结果：对头出对GetFront();  初始条件：队列已存在操作结果：获取对头元素IsEmpty();  初始条件： 操作结果： 队列为空，返回false,否则返回trueClear();  初始条件： 队列已存在操作结果： 队列为空}ADT Graph {数据对象：int matrix[maxSize][maxSize];     //邻接矩阵        Node *list;                       //邻接表        int numVertex;                //顶点数        int numEdge;                //边数        bool *Mark;                //        Tree *T;                   //最小生成树数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}Graph();               //构造函数~Graph();              //析构函数n()初始条件：图存在操作结果：获取顶点数e()  初始条件：图存在操作结果：获取边数IsEmpty();                     //判断图是否为空初始条件：操作结果：图为空，返回false,否则返回truefirst(int pos);              初始条件：图存在操作结果：返回顶点的第一条边first2(int pos);             初始条件：图存在操作结果：返回顶点的第一条边next(Edge w);               初始条件：图存在操作结果：返回顶点的下一条边IsEdge(Edge e);              初始条件：图存在操作结果：判断是否为图中的一条边weight(int ,int);初始条件：图存在操作结果：返回边的权weight(Edge); 初始条件：图存在操作结果：返回边的权initializtion();初始条件：图存在操作结果：初始化CreateGraph(); 初始条件： 操作结果：建立图Graph_traverse(char,int);初始条件：图存在操作结果：对图进行遍历DFS(int v);初始条件：图存在操作结果：深度遍历BFS(int start);初始条件：图存在操作结果：广度遍历Prim(int s); 初始条件：图存在操作结果：生成最小生成树minVertex(int *D);初始条件：图存在操作结果：选择最小权值的顶点AddEdgetoT(int,int);初始条件： 操作结果：连接边};2.本程序包含三个模块：1)主程序模块：void main(){    初始化；　　do{　　   接受命令；　　   处理命令；　　}while(“命令”=”退出”)}2)、队列模块——实现定义队列的抽象数据类型和队列的基本操作3)、图模块——实现定义图的抽象数据类型和图的基本操作各模块之间的调用关系如下：                    主程序模块                                                                图模块                                                            　　　　　　　　　　队列模块三、详细设计程序代码如下 //        程序名：Queue.h//      程序功能：对列类的头文件(并用其来实现生成最小生成树)//          作者：刘伟高//          日期：2006.12.12//          版本：1.0 //对应类实现文件: Queue.cpp//对应主程序文件: main.cpp #include<iostream.h>typedef int DataType;        //定义数据类型class Queue{private: DataType front,rear; int *Vec;               //对列 int MaxSize;            //对列最大长度public: Queue(int size);          //构造函数 ~Queue();               //析构函数 void EnQueue(DataType x);      //入队函数 DataType DelQueue();             //出对函数 DataType GetFront();           //获取对头函数 bool IsEmpty();               //判断对列是否为空 void Clear();                 //清对空}; //        程序名：Queue.cpp//      程序功能：实现对列类的源文件(并用其来实现图的各项操作)//          作者：刘伟高//          日期：2006.12.12//          版本：1.0 #include "Queue.h" //////////////////////////////////////////////////////////////////////////////// 构造函数// 函数功能：初始化对列// 函数参数：int size// 参数返回值：无Queue::Queue(int size){ MaxSize=size; front=rear=-1; Vec=new DataType[MaxSize];} //////////////////////////////////////////////////////////////////////////////// 析构函数// 函数功能：释放对列空间// 函数参数：无// 参数返回值：无Queue::~Queue(){ delete [] Vec;} //////////////////////////////////////////////////////////////////////////////// 入队函数// 函数功能：数据x入队// 函数参数：DataType x// 参数返回值：无void Queue::EnQueue(DataType x){ if(rear==MaxSize) {  cerr<<"Overflow!\n";  return; } rear=(rear+1)%MaxSize; Vec[rear]=x;} //////////////////////////////////////////////////////////////////////////////// 出队函数// 函数功能：出队// 函数参数：无// 参数返回值：返回对头元素DataType Queue::DelQueue(){ if(rear==front)  cerr<<"Underflow!\n"; else {  front=(front+1)%MaxSize;  return Vec[front]; }} //////////////////////////////////////////////////////////////////////////////// 取对头函数// 函数功能：从对列中获取对头元素// 函数参数：无// 参数返回值：对头元素DataType Queue::GetFront(){ return Vec[front];} //////////////////////////////////////////////////////////////////////////////// 判空函数// 函数功能：判断队列是否为空// 函数参数：无// 参数返回值：空则返回true,否则返回falsebool Queue::IsEmpty(){ if(front==rear)  return true; return false;} //////////////////////////////////////////////////////////////////////////////// 清对空函数// 函数功能：清空队列// 函数参数：无// 参数返回值：无void Queue::Clear(){ front=rear=-1;} //        程序名：Graph.h//      程序功能：图类的头文件(并用其来实现编/译码)//          作者：刘伟高//          日期：2006.12.12//          版本：1.0 //对应类实现文件: Graph.cpp//对应主程序文件: main.cpp #include "Queue.h"          //引用队列文件 #define maxSize  50          //定义图的最大顶点数#define INFINITY 32767       //定义权值最大值 //定义邻接表中的边结点类型class EdgeLink{                          public: int weight;   //权值域 int v2;       //边的尾结点 EdgeLink* next;//指向下一个边结点的链域}; //定义最小生成树的存储结构struct Tree{ int x;      //起始边 int y;      //尾边}; typedef EdgeLink* Edge;      struct Node     //定义邻接表类型{ char Vertex;      //保存结点的数据 Edge head;         //引出单链表}; //定义图类型class Graph{private: int matrix[maxSize][maxSize];     //邻接矩阵 Node *list;                       //邻接表 int numVertex;                //顶点数 int numEdge;                //边数 bool *Mark;                // Tree *T;                   //最小生成树 public: Graph();               //构造函数 ~Graph();              //析构函数 int n() {return numVertex;}          //获取顶点数 int e() {return numEdge;}    bool IsEmpty();                     //判断图是否为空 Edge first(int pos);              //返回顶点的第一条边 int first2(int pos);             //返回顶点的第一条边 Edge next(Edge w);                //返回顶点的下一条边 bool IsEdge(Edge e);              //判断是否为图中的一条边 int weight(int ,int);                //返回边的权 int weight(Edge);                //返回边的权 void initializtion();            //初始化 void CreateGraph();           //建立图 void Graph_traverse(char,int);       //遍历函数 void DFS(int v);               //深度遍历函数 void BFS(int start);           //广度遍历函数 void Prim(int s);               //生成最小生成树函数 int minVertex(int *D);          //选择最小权值的顶点 void AddEdgetoT(int,int);         //连接边}; //        程序名：Graph.cpp//      程序功能：实现图类的源文件(并用其来实现图的各项操作)//          作者：刘伟高//          日期：2006.12.12//          版本：1.0   #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// 参数返回值：EdgeEdge Graph::first(int v){ if(list[v].head!=NULL)    return list[v].head; else cerr<<"此顶点无关联边!\n"; return NULL;} //////////////////////////////////////////////////////////////////////////////// 获取边函数// 函数功能：返回顶点的第一条边// 函数参数：int v// 参数返回值：Edgeint Graph::first2(int v){ for(int pos=0;pos<numVertex;pos++)  if(matrix[v][pos]!=INFINITY)    return pos; return NULL;} //////////////////////////////////////////////////////////////////////////////// 判边函数// 函数功能：判定是否为图中的一条边// 函数参数：Edge w// 参数返回值：如果是图里的边，返回true;否则返回falsebool Graph::IsEdge(Edge w){ return w!=NULL;} //////////////////////////////////////////////////////////////////////////////// 判图函数// 函数功能：判定图是否为空// 函数参数：无// 参数返回值：如果图空，返回true;否则返回falsebool Graph::IsEmpty(){ if(numVertex==0) {  cerr<<"图中没有顶点!\n";  return false; } return true;} //////////////////////////////////////////////////////////////////////////////// 获取边函数// 函数功能：返回顶点的下一条边// 函数参数：Edge w// 参数返回值：EdgeEdge 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;} //        程序名：main.cpp//      程序功能：主函数源文件//          作者：刘伟高//          日期：2006.12.12//          版本：1.0 #include "GRAPH.h"         //引用图文件int main(){ cout<<"     *************************************\n"; cout<<"     **********欢迎使用图系统*************\n"; cout<<"     ******************刘伟高*************\n"; cout<<"     **在此系统中用户可以进行一下操作:  **\n"; cout<<"     **1、图邻接表的建立(C)             **\n"; cout<<"     **2、深度优先遍历(D)               **\n"; cout<<"     **3、广度优先遍历(B)               **\n"; cout<<"     **4、最小生成树(prim)(P)           **\n"; cout<<"     **5、退出(E)                       **\n"; cout<<"     *************************************\n"; cout<<"            版权所有,盗版必纠\n\n"; cout<<"请选择操作:"; Graph G; int i=0; char ch; while(1){           //重复操作  cin>>ch;        //选择操作        switch(ch)  {   case 'C':         //建图  case 'c':    G.CreateGraph();    break;  case 'D':       //深度优先遍历  case 'd':   cout<<"深度优先遍历:\n";   cout<<"请输入深度优先遍历的起始点:";   cin>>i;   G.Graph_traverse(ch,i);   break;  case 'B':               //广度优先遍历  case 'b':   cout<<"广度优先遍历:\n";   cout<<"请输入广度优先遍历的起始点:";   cin>>i;   G.Graph_traverse(ch,i);   break;  case 'P':             //最小生成树  case 'p':   cout<<"请输入最小生成树的起始点:";   cin>>i;   G.Prim(i);    break;  case 'E':               //退出  case 'e':   cout<<"*************************\n";   cout<<"*****感谢使用本系统!*****\n";   cout<<"*************************\n";   return 0;  }  cout<<"   ************************************************************\n";  cout<<"   **深度优先遍历(D)//广度优先遍历(B)//最小生成树(P)//退出(E)**\n";  cout<<"   ************************************************************\n";  cout<<"请选择操作:"; }}四、调试分析1、由于对图的基本操作的推敲不足，使程序调试时费时不少。2、本程序模块划分比较合理，且利用指针的操作，操作方便。3、算法的时空分析　　在此程序中，存储字符串用了指针，先动态申请空间，然后再存，这样就有效的利用了空间。　　而对于算法本身。用邻接矩阵存储，存储顶点集合的数组变量的大小n应为需要处理的图的可能具有的最多的顶点数。而存储邻接矩阵的二维数组变量的大小一定为n2。所以邻接矩阵存储的空间大小由图的顶点数决定。　　而用邻接表存储，顶点数组的大小自然由图的最多可能有的顶点个数决定。边结点的多少则取决于图的边的条数。所以图的邻接表存储的大小由图的顶点个数和边的条数共同决定。4、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试可以顺利完成，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。五、用户手册1、本程序的运行环境为DOS操作系统2、进入演示程序后即显示文本方式的用户界面   3、进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。六、测试结果    如上图所示。七、附录源程序文件名清单：Graph.h                    //图定义单元Graph.cpp                  //图实现单元Queue.h                   //队列定义单元Queue.cpp                 //队列实现单元main.cpp                  //主程序 四、实验总结（心得体会）１、通过实验更好的掌握了图操作的实现，更深的理解广度优先遍历、深度优先遍历、最小生成树算法2、更进一步掌握有关类的操作3、由于算法推敲不足，使程序调试时费时不少4、更熟悉了文件的操作5、更好的掌握了对程序的调试，并从中感受到调试的巨大的力量，特别是当程序不能实现预想结果时   五、参考文献：1、《数据结构与算法》    黄定  黄煜廉  刘贤兴  编著  　　　　　　　　广东科技出版社  2000年1月第1版2、《〈数据结构与算法〉学习与实验指导》  黄煜廉 编著   2005. 8      

评论