图基本操作的实现
一、【实验内容】
【问题描述】
（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,否则返回true
Clear();
初始条件： 队列已存在
操作结果： 队列为空
}
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,否则返回true
first(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,否则返回false
bool 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
// 参数返回值：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;
}
// 程序名：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