数据结构与算法实验——图的基本操作.doc

图的基本操作
实验报告

图的基本操作实验报告

实验名称
图的基本操作

实验目的
1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；
2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；
3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；

实验内容
编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。

问题描述
用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）。

问题分析
该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。

实验步骤
1．需求分析 
   本演示程序用VC++编写，完成图的邻接表的生成、遍历基本操作。 
① 输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。 
②  输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。 
③  程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。 

④  测试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。 

2．概要设计 
  1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：   
ADT Graph { 
 数据对象：顶点的有穷非空集合和边的集合
数据关系：结点具有相同的数据类型及层次结构 
基本操作： 
Void InitGraph(ALGraph *G)
   初始条件：无 
   操作结果：初始化图  
Void DFSTraverse(ALGraph *G)  
   初始条件：图Graph已存在 
   操作结果：按深度优先遍历图的邻接表
Void BFSTraverse(ALGraph *G)  
   初始条件：图Graph已存在 
   操作结果：按广度优先遍历图的邻接表
2）本程序包含7个函数：   
①主函数main() ② 建立一个图的邻接表函数CreateGraphAL () ③深度优先遍历图 DFS ()④广度优先遍历 BFS()

函数说明
#include
#include
#define MaxVertexNum 100
#define QueueSize 30
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxVertexNum];
typedef char VertexType;
typedef int EdgeType;
typedef struct node //边表结点
{
int adjvex; //邻接点域
struct node *next; //域链
//若是要表示边上的权,则应增加一个数据域
}EdgeNode;
typedef struct vnode //顶点边结点
{
VertexType vertex; //顶点域
EdgeNode *firstedge;//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
}ALGraph;

void CreateGraphAL (ALGraph *G)
{
int i,j,k;
EdgeNode * s;
printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n")
scanf("%d,%d",&(G->n),&(G->e)); // 读入顶点数和边数
printf("请输入顶点信息(输入格式为:顶点号)每个顶点以回车作为结束:\n");
for (i=0;in;i++) // 立有n个顶点的顶点表
{
scanf("\n%c",&(G->adjlist[i].vertex)); // 读入顶点信息
G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空
}
printf("请输入边的信息(输入格式为:i,j)：\n");
for (k=0;ke;k++) // 建立边表
{
scanf("\n%d,%d",&i,&j); // 读入边的顶点对应序号
s=new EdgeNode; // 生成新边表结点s
s->adjvex=j; // 邻接点序号为j
s->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部
G->adjlist[i].firstedge=s;
s=new EdgeNode;
s->adjvex=i;
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;
}
}
/************************************************************************/
/* 深度优先遍历 */
/************************************************************************/
void DFS(ALGraph *G,int i)
{
//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode *p;
printf("visit vertex:%c\n",G->adjlist[i].vertex); // 访问顶点vi
visited[i]=TRUE; //标记vi已访问
p=G->adjlist[i].firstedge; //取vi边表的头指针
while(p)
{ //依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex]) //若vi尚未被访问
DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索
p=p->next; //找vi的下一邻接点
}
}
void DFSTraverseM(ALGraph *G)
{
int i;
for(i=0;in;i++)
visited[i]=FALSE;
for(i=0;in;i++)
if(!visited[i])
DFS(G,i);
}
/************************************************************************/
/* 广度优先遍历 */
/********************************************/
typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q)
{
return Q->front==Q->rear;
}
int QueueFull(CirQueue *Q)
{
return (Q->rear+1)%QueueSize==Q->front;
}
void EnQueue(CirQueue *Q,int x)
{
if (QueueFull(Q))
printf("Queue overflow");
else
{
Q->count++;
Q->data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;
}
}
int DeQueue(CirQueue *Q)
{
int temp;
if(QueueEmpty(Q))
{
printf("Queue underflow");
return false;
}
else
{
temp=Q->data[Q->front];
Q->count-
Q->front=(Q->front+1)%QueueSize;
return temp;
}
}
void BFS(ALGraph*G,int k)
{ // 以vk为源点对用邻接表表示的图G进行广度优先搜索
int i;
CirQueue Q; //须将队列定义中DataType改为int
EdgeNode *p;
InitQueue(&Q); //队列初始化
printf("visit vertex:%c\n",G->adjlist[k].vertex); //访问源点vk
visited[k]=TRUE;
EnQueue(&Q,k); //vk已访问，将其人队。（实际上是将其序号人队）
while(!QueueEmpty(&Q))
{ //队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->adjlist[i].firstedge; //取vi的边表头指针
while(p)
{ //依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex])
{ //若vj未访问过
printf("visit vertex:%c\n",G->adjlist[p->adjvex].vertex); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex); //访问过的vj人队
}
p=p->next; //找vi的下一邻接点
}
}
}
void BFSTraverseM(ALGraph *G)
{
int i;
for (i=0;in;i++)
visited[i]=FALSE;

for (i=0;in;i++)
if (!visited[i])
BFS(G,i);
}
/************************************************************************/
/* 主函数调用 */
/************************************************************/
int main()
{
int n;
ALGraph G;
CreateGraphAL(&G);
printf("深度优先遍历：\n");
DFSTraverseM(&G);
printf("广度优先遍历：\n");
BFSTraverseM(&G);
return 0;
}
程序流程图

开始
访问V,置标志
求V邻接点
有邻接点w？
求下一邻接点
w→V
W访问过？
返回
N
Y
N
Y
深度优先遍历流程图

开始
结束
初始化visit[v]
V入队列
对头元素出队，
W= FirstAdjVex(G,,u)
初始化visited[v]
V入队列
w=NextAdjVex(G,u,w)
!IsEmptyQueue(Q)
w!=-1
Y
Y
N
N
广度优先遍历流程图

调试报告
发现问题：
1. 在创建图的邻接表以后，得到的深度优先遍历和自己在草稿纸上演算得到的序列不符。
2. 在创建图的邻接表以后，得到的广度优先遍历和自己在草稿纸上演算得到的序列不符。
调试：
1. 仔细检查程序后，发现是因为创建邻接表的方法是头插法；
2. 检查程序，发现依据队列的长度而判断队满和队空的条件不能实现。
解决方案：
1. 我重新在草稿纸上对用头插法建立的邻接表进行深度遍历；
2. 将队满的条件修改为：(rear+1)%QueueSize==front;将队空的条件修改为：rear==front
结果：结果运行正确！

使用说明

建立邻接表

深度优先遍历

广度优先遍历
心得体会
数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。 
图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅仅是创建图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优先和广度优先是两种算法，其算法思想并不依赖与元素的存储方式，也就是说算法思想不会因为存储结构的改变而发生改变，当然对于不同的存储结构仅仅是代码的表现形式不同而已，正所谓一同百通，只要熟悉存储结构的特点又对算法思想烂熟于心便可无往不胜。以下是存在的问题：
1. 程序编写时，必须要细心。有时候问题出现了，可能会一直查不出来，自己也不容易发现。在编写这个程序时，我就出现了这个问题，之后一定要尽量避免此类问题出现。 
2. 加强练习，提高能力。这几个子函数的名称都是我边看着书边写的，还没有完全脱离书本，把这个程序真正变成自己建的东西，所以我还要加强记忆，加强练习。