图的深度优先遍历和广度优先遍历.doc

华北水利水电学院 数据结构 实验报告
20 10 ～20 11 学年 第 一 学期 2008级 计算机 专业
班级： 107 学号： 200810702 姓名： 王文波
实验四 图的应用
一、 实验目的：
1．掌握图的存储结构及其构造方法
2．掌握图的两种遍历算法及其执行过程
二、 实验内容：
以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。
提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。
三、 实验要求：
1． 各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。
2． C/ C++完成算法设计和程序设计并上机调试通过。
3． 撰写实验报告，提供实验结果和数据。
4． 写出算法设计小结和心得。
四、 程序源代码：
#include<iostream.h>
#define MaxVerNum 50
struct edgenode
{
int endver;
int inform;
edgenode* edgenext;

};
struct vexnode
{
char vertex;
edgenode* edgelink;
};
struct Graph
{
vexnode adjlists[MaxVerNum];
int vexnum;
int arcnum;
};
//队列的定义及相关函数的实现
struct QueueNode
{
int nData;
QueueNode* next;
};
struct QueueList
{
QueueNode* front;
QueueNode* rear;
};
void EnQueue(QueueList* Q,int e)
{
QueueNode *q=new QueueNode;
q->nData=e;
q->next=NULL;
if(Q==NULL)
return;
if(Q->rear==NULL)
Q->front=Q->rear=q;
else
{
Q->rear->next=q;
Q->rear=Q->rear->next;
}
}
void DeQueue(QueueList* Q,int* e)
{
if (Q==NULL)
return;
if (Q->front==Q->rear)
{
*e=Q->front->nData;
Q->front=Q->rear=NULL;
}
else
{
*e=Q->front->nData;
Q->front=Q->front->next;
}
}
//创建图
void CreatAdjList(Graph* G)
{
int i,j,k;
edgenode* p1;
edgenode* p2;
cout<<"请输入顶点数和边数:"<<endl;
cin>>G->vexnum>>G->arcnum;
cout<<"开始输入顶点表:"<<endl;
for (i=0;i<G->vexnum;i++)
{
cin>>G->adjlists[i].vertex;
G->adjlists[i].edgelink=NULL;
}
cout<<"开始输入边表信息:"<<endl;
for (k=0;k<G->arcnum;k++)
{
cout<<"请输入边<Vi,Vj>对应的顶点:";
cin>>i>>j;
p1=new edgenode;
p1->endver=j;
p1->edgenext=G->adjlists[i].edgelink;
G->adjlists[i].edgelink=p1;
p2=new edgenode;
p2->endver=i;
p2->edgenext=G->adjlists[j].edgelink;
G->adjlists[j].edgelink=p2;
//因为是无向图，所以有两次建立边表的过程
}
}

//-------------------------------------------------------------深度优先遍历
void DFS(Graph *G,int i,int visit[])
{
cout<<G->adjlists[i].vertex<<" ";
visit[i]=1;
edgenode *p=new edgenode;
p=G->adjlists[i].edgelink;
if(G->adjlists[i].edgelink&&!visit[p->endver])
{
DFS(G,p->endver,visit);
}
}
void DFStraversal(Graph *G,char c)//深度优先遍历
{
cout<<"该图的深度优先遍历结果为:"<<endl;
int visit[MaxVerNum];
for(int i=0;i<G->vexnum;i++)
{
visit[i]=0;//全部初始化为0，即未访问状态
}
int m;
for (i=0;i<G->vexnum;i++)
{
if (G->adjlists[i].vertex==c)//根据字符查找序号
{
m=i;
DFS(G,i,visit);
break;
}
}
//继续访问未被访问的结点
for(i=0;i<G->vexnum;i++)
{
if(visit[i]==0)
DFS(G,i,visit);
}
cout<<endl;
}
//-------------------------------------------------------------广度优先遍历
void BFS(Graph* G,int v,int visit[])
{
QueueList *Q=new QueueList;
Q->front=Q->rear=NULL;
EnQueue(Q,v);
while(Q->rear!=NULL)
{
int e=0;
DeQueue(Q,&e);
cout<<G->adjlists[e].vertex<<" ";
visit[e]=1;
edgenode* p=new edgenode;
p=G->adjlists[e].edgelink;
if(p)
{
int m=p->endver;
if(m==0)
{
EnQueue(Q,m);
while(visit[m]==0)
{
p=p->edgenext;
if(p==NULL)
break;
m=p->endver;
EnQueue(Q,m);
}
}

}

}
}
void BFStraversal(Graph *G,char c)
{
cout<<"该图的广度优先遍历结果为:"<<endl;
int visited[MaxVerNum];
for (int i=0;i<G->vexnum;i++)
{
visited[i]=0;
}
int m;
for (i=0;i<G->vexnum;i++)
{
if (G->adjlists[i].vertex==c)
{
m=i;
BFS(G,i,visited);
break;
}
}
//继续访问未被访问的结点
for(i=0;i<G->vexnum;i++)
{
if(visited[i]==0)
BFS(G,i,visited);
}
cout<<endl;
}
void main()
{
Graph * G=new Graph;
CreatAdjList(G);
char ch;
cout<<"请输入开始遍历的顶点:";
cin>>ch;
DFStraversal(G,ch);
BFStraversal(G,ch);
}

五、 程序运行情况（写出输入数据及运行结果）

六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
注：内容一律使用宋体五号字，单倍行间距
本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。

第 6 页 共 6 页