图遍历的演示.doc

《数据结构》课程实验报告

题目：图遍历的演示
班级：
姓名：
学号：
专业：
学院：
完成日期：

一、 需求分析
（1） 问题描述：
很多涉及图上操作的算法都是以图的遍历操作作为基础的。试写一个程序，演示在连通图的无向图上访问全部结点的操作。
（2） 基本要求：
以邻接多重表（选作内容邻接表）为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集

（3） 输入的形式和输入的范围：先输入顶点数N以及边数M，然后依次输入N个顶点，再按提示输入M条边的信息用（a-b 3）类似的形式

（4） 测试数据：
教科书图7.33部分信息

二、 概要设计
（1） 抽象数据类型图的定义：
ADT Graph{
数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。
数据关系 R:
R=｛VR｝
VR={ <v,w>| v,w є V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 }
基本操作 P：
locatevex(G, mes)；
初始条件：图G存在，mes和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。
createudn( & G)；
初始条件：图G 存在。
操作结果：创建无向图。
createdn( & G)；
初始条件：图G 存在。 操作结果：创建有向图。
createudg( & G)；
初始条件：图G 存在
操作结果：创建无向网。
createdg(& G)；
初始条件：图G 存在。
操作结果：创建有向网。
DFS(G,v)；
初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。
操作结果：深度优先搜索遍历图G，访问顶点时使用函数
visit. BFS(G,v)；
初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。
操作结果：广度优先搜索遍历图G，访问顶点时使用函数
visit. visit( a)；
初始条件：a为图中的某个顶点值。
操作结果：访问顶点a，本程序中作用结果为输出顶点值。 ｝ADT Graph

（2） .邻接表存储结构的图定义：
ADT algraph{
数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。
数据关系 R:
R=｛VR｝
VR={ <v,w>| v,w є V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 }
基本操作 P： locatevex(G, mes)；
初始条件：图G存在，mes和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。
createudn( & G)；
初始条件：图G 存在。
操作结果：创建无向图。
createdn( & G)；
初始条件：图G 存在。
操作结果：创建有向图。
Createudg( & G)；
初始条件：图G 存在。
操作结果：创建无向网。
createdg(& G)；
初始条件：图G 存在。
操作结果：创建有向网。
DFS(G,v)；
初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。
操作结果：深度优先搜索遍历图G，访问顶点时使用函数
visit. BFS(G,v)；
初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。
操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.
visit( a)；
初始条件：a为图中的某个顶点值。
操作结果：访问顶点a，本程序中作用结果为输出顶点值。 ｝ADT algraph

2. （3）设定队列的抽象数据类型定义：
ADT Queue{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }
约定a1为队列头，an为队列尾。
基本操作：
InitQueue( &Q )
操作结果：构造一个空队列Q。
DestroyQueue ( &Q )
初始条件：队列Q已存在。
操作结果：销毁队列Q。
ClearQueue ( &Q )
初始条件：队列Q已存在。
操作结果：将Q清为空队列。
QueueEmpty( Q )
初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
QueueLength( Q )
初始条件：队列Q已存在。
操作结果：返回Q的数据元素个数，即队列的长度。
GetHead( Q, &e )
初始条件：队列Q已存在且非空。
操作结果：用e返回Q的队头元素。
EnQueue( &Q, e )
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue( &Q, &e )
初始条件：队列Q已存在且非空。
操作结果：删除Q的队头元素，并用e返回其值。
QueueTraverse( Q, visit() )
初始条件：队列Q已存在且非空。
操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT Queue

三、 详细设计
（1） 元素类型、结点类型和指针类型
typedef struct{ //图的邻接矩阵存储结构
char *vexs; //顶点向量
int arcs[MAX+1][MAX+1]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;

（2） 队列的具体定义
class Queue{ //队列类
public: void InitQueue()
{ base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){ //插入元素e为新的队尾元素
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE; //rear后移
}

void DeQueue(int &e){ //若队列不空，则删除对头元素，用e返回
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base; int front; int rear;
};

（3） 查找定位函数
int Locate(Graph G,char c){ //图G中查找元素c的位置
for(int i=1;i<=G.vexnum;i++){
if(G.vexs[i]==c)
return i;
}
return -1;
}

（4） 初始化无向图函数
void CreateUDN(Graph &G){ //创建无向图
int i,j,w,s1,s2;
char a,b,temp;
cout<<"输入顶点的总数和边的总数:";
cin>>G.vexnum>>G.arcnum;
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
cout<<"输入"<<G.vexnum<<"个顶点分别为:"<<endl;
for(i=1;i<=G.vexnum;i++){ //初始化顶点
cout<<"顶点:"<<i;
cin>>&G.vexs[i];
temp=getchar();
}
for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=INFINITY; //16int类型，初始化边为无穷大
cout<<"输入"<<G.arcnum<<"条边分别为:"<<endl; //读取边信息并初始化集合
for(i=1;i<=G.arcnum;i++){ //初始化边
cout<<"边"<<i<<endl;
scanf("%c-%c %d",&a,&b,&w); //输入边和权值
temp=getchar(); //接收回车
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w; } //无向
}
int FirstVex(Graph G,int k){ //图G中顶点k的第一个邻接顶点
if(k>=1 && k<=G.vexnum){
for(int i=1;i<=G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY)
return i;
}
return -1;
}
int NextVex(Graph G,int i,int j){ //图G中顶点i的第j个邻接顶点的下一个邻接顶点
if(i>=1 && i<=G.vexnum && j>=1 && j<=G.vexnum){ //i,j合理
for(int k=j+1;k<=G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY)
return k;
}
return -1;
}

（5） 深度优先遍历及广度优先遍历函数
void DFS(Graph G,int k){ //深度优先搜索
int i;
if(k==-1){ //第一次执行DFS时,k为-1
for(i=1;i<=G.vexnum;i++)
if(!visited[i])
DFS(G,i);
} //对尚未访问的顶点调用DFS
else{
visited[k]=true; //访问第k个顶点
cout<<G.vexs[k];
for(i=FirstVex(G,k);i>=1;i=NextVex(G,k,i))
if(!visited[i])
DFS(G,i);
}

}

void BFS(Graph G){ //广度优先搜索
int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<=G.vexnum;i++)
if(!visited[i]){ //i尚未访问
visited[i]=true;
cout<<G.vexs[i];
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true;
cout<<G.vexs[w];
Q.EnQueue(w);
}
}
}

}

（6） 主函数
void main(){ //主函数
int i;
Graph G;
CreateUDN(G); //创建无向图
visited=(bool *)malloc(G.vexnum*sizeof(bool));
cout<<endl<<"深度优先搜索结果为:";
for(i=1;i<=G.vexnum;i++){
visited[i]=false; //标志数组初始化为false
DFS(G,-1); }
cout<<endl<<"广度优先搜索结果为:";
for(i=1;i<=G.vexnum;i++){
visited[i]=false;
BFS(G);}
cout<<endl;
}

四、 调试过程：
做此题比较艰辛，虽说书中有相印的部分代码，但实现起来还是有点差别，最后也只完成题目要求的80%。
五、 测试结果

六、 心得体会：
学到树图这几章以后发现数据结构还是有难度的，对于无向图，任意两个顶点之间都有可能有关系，这就是难点之处，通过此题的编写也扩张了我的思路。