C++图的创建与遍历实验报告

实验 五 图的遍历及其应用实现

一、实验目的

1．熟悉图常用的存储结构。

2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。

3．会用图的遍历解决简单的实际问题。

二、需求分析

很多问题都是建立在图的遍历的基础上实现的，所以必须有一个程序能够实现将图进行广度和深度遍历，必须对图的所有节点进行访问。

以无向图为例，以无向图的邻接表和邻接矩阵为存储结构，分别实现对图进行广度和深度遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应的生成树的边集。

三、实验内容

[题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。

提示：

输入示例

上图的顶点和边的信息输入数据为：

5 7 DG

A B C D E

AB AE BC CD DA DB EC

四、结构算法模块：

typedef struct ArcNode//定义邻接表结构

{

int adjvex;//该弧所指向的顶点的位置

struct ArcNode *nextarc;//指向下一条弧的指针

}ArcNode;

typedef struct VNode//定义顶点结构类型

{

char data;//存放顶点信息

ArcNode *firstarc;//指向第一条依附于该定点的指针

}VNode,Adjlist[MAX_VEX_NUM];

typedef struct ALGraph

{

Adjlist vertices;

int vexnum;

int arcnum;

}ALGraph;

五、相关函数设计

Create_DG(ALGraph &G)//创建一个有向图图的邻接链表表示

DFSTraverse(ALGraph G,int vex)//对图G做深度优先遍历

BFSTraverse(ALGraph G)//有向图的广度遍历，从第v个顶点出发，v为顶点下标

locatevex(ALGraph G,char v)//图的基本操作，寻找顶点位置的下标 DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G

六、程序流程图

七、运行结果截图

最初程序运行界面如下：

输入图的先相关信息后运行结果(其中深度优先遍历的起点选择的是字符所在序列的序号，且0是起点)，一下是深度优先遍历时选择不同的起点所出现的最终运行结果：

程序源代码：

//图的邻接表表示：

#include<iostream>

#include<malloc.h>

#include<queue>

using namespace std;

# define MAX_VEX_NUM 20//宏定义数组最大

int visited[MAX_VEX_NUM];//设置标志数组

queue<int>q;

typedef struct ArcNode//定义邻接表结构

{

int adjvex;//该弧所指向的顶点的位置

struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode;

typedef struct VNode//定义顶点结构类型

{

char data;//存放顶点信息

ArcNode *firstarc;//指向第一条依附于该定点的指针 }VNode,Adjlist[MAX_VEX_NUM];

typedef struct ALGraph

{

Adjlist vertices;

int arcnum;

}ALGraph;

ALGraph G;//申明一个无向图的邻接矩阵类型

int locatevex(ALGraph G,char v)//图的基本操作，寻找顶点位置的下标

{

}

void Create_DG(ALGraph &G)//创建一个有向图图的邻接链表表示

{

cout<<"请输入图的顶点数和弧数:"<<endl; cin>>G.vexnum; cin>>G.arcnum; int i=0; while(i<G.vexnum && v!=G.vertices[i].data) i++; if(i<G.vexnum) return i;

char v2; int v1locate; int v2locate; ArcNode * p; cout<<"输入图的顶点信息"<<endl; for(int i=0;i<G.vexnum;i++)//构造表头向量 { } cout<<"请输入从起点到终点的一条弧所对应的顶点cin>>G.vertices[i].data;//输入顶点值 G.vertices[i].firstarc=NULL;//初始化指针 "<<endl;

表

{ cin>>v1>>v2;//输入一条弧的起点和终点 for(int k=1;k<=G.arcnum;k++)//输入各弧并创建十字链

v1locate=locatevex(G,v1);//确定v1在图G中位置

v2locate=locatevex(G,v2);//确定v2在图G中位置

p=new ArcNode;//假定有足够空间

值

p->nextarc=G.vertices[v1locate].firstarc;//对弧节点赋 G.vertices[v1locate].firstarc=p;//完成在入弧和出弧链表的插入

/*q=new ArcNode;

} q->adjvex=v1locate; q->nextarc=G.vertices[v2locate].firstarc; G.vertices[v2locate].firstarc=q;*/

}//Create_DG

void DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G

{

visited[v]=1;//访问第v个节点

cout<<G.vertices[v].data<<" ";//输出节点值 for(ArcNode *p=G.vertices[v].firstarc;p;p=p->nextarc) { if(!visited[p->adjvex])

DFS(G,p->adjvex);//对v的尚未访问的邻接顶点p递归调用dfs

}

}//DFS

void DFSTraverse(ALGraph G,int vex)//对图G做深度优先遍历

{

历

if(!visited[v]) //对尚未访问的顶点调用dfs DFS(G,v); for(int i = 0;i < G.vexnum;i++) visited[i]=0; //访问数组初始化 //先对图从指定定点访问 DFS(G,vex); for(int v = 0;v < G.vexnum;v ++) //对可能出现的子图遍

}//DFSTraverse

int BFSTraverse(ALGraph G)//无向图的广度遍历，从第v个顶点出发，v为顶点下标

{

for(int i = 0;i < G.vexnum;i++) //访问数组初始化

visited[i]=0; q.empty();

int v;

int u; for(v=0;v<G.vexnum;v++) if(!visited[v])//v尚未被访问 { visited[v]=1; cout<<G.vertices[v].data<<" "; q.push(v);//V入队列 while(!q.empty()) { u=q.front();//对头元素出队并置为u q.pop(); for(ArcNode

*p=G.vertices[v].firstarc;p;p=p->nextarc)

if(!visited[p->adjvex])//p为u的尚未访问的邻接节点

{ visited[p->adjvex]=1; cout<<G.vertices[p->adjvex].data<<" "; q.push(p->adjvex); }//if }//while }//if

return 1;

}//BFSTraverse

void main()

{

int a;

Create_DG(G);

cout<<"输入图深度遍历的起点"<<endl; cin>>a;

cout<<"深度优先遍历"<<endl; DFSTraverse(G,a);

cout<<endl;

cout<<"广度优先遍历"<<endl; BFSTraverse(G);

}