图的基本操作 实验报告

一、实验目的

1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。

二、实验内容

[问题描述]

对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优

先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】

由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。

五、算法设计

1、程序所需头文件已经预处理宏定义和结构体定义如下

#include #define MaxVerNum 100 struct edgenode {

int endver; int inform;

edgenode* edgenext; };

struct vexnode {

char vertex;

edgenode* edgelink; };

struct Graph {

vexnode adjlists[MaxVerNum]; int vexnum; int arcnum; };

2、创建无向图

void CreatAdjList(Graph* G) {

int i,j,k;

edgenode* p1; edgenode* p2;

cout<<\"请输入顶点数和边数:\"<>G->vexnum>>G->arcnum; cout<<\"开始输入顶点表:\"<vexnum;i++) { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; }

cout<<\"开始输入边表信息:\"<arcnum;k++) { cout<<\"请输入边对应的顶点:\"; 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;

//因为是无向图，所以有两次建立边表的过程

3、深度优先遍历

void DFS(Graph *G,int i,int visit[]) {

cout<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<<\"该图的深度优先遍历结果为:\"<for(int i=0;ivexnum;i++) { visit[i]=0;//全部初始化为0，即未访问状态 }

int m;

for (i=0;ivexnum;i++) { if (G->adjlists[i].vertex==c)//根据字符查找序号 { m=i; DFS(G,i,visit); break; } }

//继续访问未被访问的结点 for(i=0;ivexnum;i++) { if(visit[i]==0) DFS(G,i,visit); }

cout<4、广度优先遍历

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<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<<\"该图的广度优先遍历结果为:\"<for (int i=0;ivexnum;i++) {

visited[i]=0; }

int m;

for (i=0;ivexnum;i++) {

if (G->adjlists[i].vertex==c) { m=i;

BFS(G,i,visited);

break; } }

//继续访问未被访问的结点 for(i=0;ivexnum;i++) {

if(visited[i]==0) BFS(G,i,visited); }

cout<六、调试与测试 测试数据，如图：

七、总结

通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用。C++没有掌握好，所以这次做本次实验还是吃力，刚开始完全没有思路，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验，此次实验发现的自己的不足，在以后的学习中，我会更加的努力。

八、源代码

#include #define MaxVerNum 100 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<<\"请输入顶点数和边数:\"<>G->vexnum>>G->arcnum; cout<<\"开始输入顶点表:\"<vexnum;i++) { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; }

cout<<\"开始输入边表信息:\"<arcnum;k++) { cout<<\"请输入边对应的顶点:\"; 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<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<<\"该图的深度优先遍历结果为:\"<for(int i=0;ivexnum;i++) { visit[i]=0;//全部初始化为0，即未访问状态 }

int m;

for (i=0;ivexnum;i++) { if (G->adjlists[i].vertex==c)//根据字符查找序号 { m=i; DFS(G,i,visit); break; } }

//继续访问未被访问的结点 for(i=0;ivexnum;i++) { if(visit[i]==0) DFS(G,i,visit); }

cout<//广度优先遍历

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<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<<\"该图的广度优先遍历结果为:\"<for (int i=0;ivexnum;i++) { visited[i]=0; }

int m;

for (i=0;ivexnum;i++) { if (G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } }

//继续访问未被访问的结点 for(i=0;ivexnum;i++) { if(visited[i]==0) BFS(G,i,visited); }

cout<void main() {

Graph * G=new Graph; CreatAdjList(G); char ch;

cout<<\"请输入开始遍历的顶点:\"; cin>>ch;

DFStraversal(G,ch); BFStraversal(G,ch); }