数据结构实验报告九—图的遍历

时间:2024.3.15

问题描述:

若用有向网表示网页的链接网络,其中顶点表示某个网页,有向弧表示网页之间的链接关系。试设计一个网络蜘蛛系统,分别以广度优先和深度优先的策略抓取网页。

一、       需求分析:

1.本程序要求采用利用图实现广度优先搜索。

2.首先输入顶点的数量,然后是各顶点对应的字母,再输入各条弧(权值都置为1)。

3.在Dos界面输出从首个顶点开始的广度优先遍历序列。

4.测试数据

   输入

输入顶点数和弧数:8 9

输入8个顶点.

输入顶点0:a

输入顶点1:b

输入顶点2:c

输入顶点3:d

输入顶点4:e

输入顶点5:f

输入顶点6:g

输入顶点7:h

输入9条弧.

输入弧0:a b 1

输入弧1:b d 1

输入弧2:b e 1

输入弧3:d h 1

输入弧4:e h 1

输入弧5:a c 1

输入弧6:c f 1

输入弧7:c g 1

输入弧8:f g 1

输出

广度优先遍历: a b d h e c f g

深度优先遍历: a b c d e f g h

二、概要设计 :

     抽象数据类型 :

图的定义:

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

CreateGraph(&G,V,VR)

   初始条件:V是图的顶点集,VR是图中弧的集合

      操作结果:按V和VR的定义构造图G

FirstAdjVex(G,v)

初始条件:图G存在,v是G中某个顶点

操作结果:返回v的第一个邻接顶点,若顶点在G中没有邻接顶点,则返回“空”

Next AdjVex(G,v,w)

初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点

操作结果:返回v的(相对于w的)下一个邻接顶点,若w是v的最后一个邻接点,则返回“空”

visit(G, k)

初始条件:图G存在

操作结果:访问图G中的第K个节点

Locate(G, c)

初始条件:图G存在

操作结果:访问图G中的c顶点

DFS(G, v)

初始条件:图G存在

操作结果:以图G中的第v个节点为起点深度优先访问图G

BFS(G)

初始条件:图G存在

操作结果:广度优先访问图G

 } ADT Graph

    算法的基本思想 :

(1)图的特点是没有首尾之分,所以算法的参数要指定访问的第一个顶点。(2)对图的遍历路径有可能构成一个回路,从而造成死循环,所以算法设计要考虑遍历路径可能出现的死循环问题。(3)一个顶点可能和若干个顶点都是邻接顶点,要使一个顶点的所有邻接顶点按照某种次序被访问。

深度优先搜索遍历

连通图的深度优先遍历递归算法可描述为:(1)访问顶点vi并标记顶点vi为已访问;(2)查找顶点v的第一个邻接顶点vj;(3)若顶点v的邻接顶点vj存在,则继续执行,否则算法结束;(4)若顶点vj尚未被访问,则深度优先遍历递归访问顶点vj;(5)查找顶点vi的邻接顶点vj的下一个邻接顶点,转到步骤(3)。当寻找顶点vi的邻接顶点vj成功时继续进行,当寻找顶点vi的邻接顶点vj失败时回溯到上一次递归调用的地方继续进行。为了在遍历过程中便于区分顶点是否被访问,需附设访问标志数组visited[ ],其初值为0,一旦某个顶点被访问,则其相应的分量置为1。

广度优先遍历算法:

    需要一个队列以保持访问过的顶点的顺序,以便按顺序访问这些顶点邻接顶点。连通图的广度优先遍历算法为:(1)访问初始顶点v并标记顶点v为已访问;(2)顶点v入队列;(3)当队列非空时则继续执行,否则算法结束;(4)出队列取得队头顶点u;(5)查找顶点u的第一个邻接顶点w;(6)若顶点u的邻接顶点w不存在,则转到步骤(3),否则执行后序语句:①若顶点w尚未被访问,则访问顶点w并标记顶点w为已访问;②顶点w入队列;③查找顶点u的邻接顶点w后的下一个邻接顶点,转到步骤(6)。

程序的流程

    程序由三个模块组成:

(1)主程序模块:包括图的创建,邻接点的查找和顶点的查找

(2)数据保存中间变量模块:实现用数组代替队列存取

(3)元素结构单元模块:定义图每个元素的结构

三、详细设计

1.元素类型,图类型

typedef struct

{

  char *vexs; //顶点向量

  int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵

  int vexnum,arcnum; //图的当前顶点数和弧数

}Graph,*GP;

2.根据图的特点,G即为该图的名称,该程序的基本操作具体实现如下

void EnQueue(int e){

    base[rear]=e;

    rear=(rear+1)%QUEUE_SIZE;

  }

  void DeQueue(int &e){

    e=base[front];

    front=(front+1)%QUEUE_SIZE;

  }

  public:

  int *base;

  int front;

  int rear;

};

//图G中查找元素c的位置

int Locate(Graph G,char c){

  for(int i=0;i<G.vexnum;i++)

  if(G.vexs[i]==c) return i;

  return -1;

}

//创建无向网

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<<"输入顶点:"<<endl;

  for(i=0;i<G.vexnum;i++){ //初始化顶点

    cout<<"输入顶点"<<i<<":";

    cin>>G.vexs[i];

    temp=getchar(); //接收回车

  }

  for(i=0;i<G.vexnum;i++) //初始化邻接矩阵

    for(j=0;j<G.vexnum;j++)

      G.arcs[i][j]=INFINITY;

  cout<<"输入弧:"<<endl;

  for(i=0;i<G.arcnum;i++){ //初始化弧

    cout<<"输入弧"<<i<<":";

    cin>>a>>b>>w; //输入一条边依附的顶点和权值

    temp=getchar(); //接收回车

    s1=Locate(G,a);

    s2=Locate(G,b);

    G.arcs[s1][s2]=G.arcs[s2][s1]=w;

  }}

//图G中顶点k的第一个邻接顶点

int FirstVex(Graph G,int k){

  if(k>=0 && k<G.vexnum){ //k合理

    for(int i=0;i<G.vexnum;i++)

      if(G.arcs[k][i]!=INFINITY) return i;

  }return -1;}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(Graph G,int i,int j){

  if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理

    for(int k=j+1;k<G.vexnum;k++)

      if(G.arcs[i][k]!=INFINITY) return k;

  }

  return -1;

}//深度优先遍历

void DFS(Graph G,int k){

  int i;

  if(k==-1){ //第一次执行DFS时,k为-1

    for(i=0;i<G.vexnum;i++)

      if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

  }

  else{

    visited[k]=true;

    cout<<G.vexs[k]; //访问第k个顶点

    for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))

if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS

  }}

//广度优先遍历

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);  } } }}

3.主程序中,直接调用main函数其大概流程图为,具体代码实现如下:

void main(){

  int i;

  Graph G;

  CreateUDN(G);

  visited=(bool *)malloc(G.vexnum*sizeof(bool));

  cout<<"广度优先遍历: ";

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  DFS(G,-1);

  cout<<endl;

  cout<<"深度优先遍历: ";

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  BFS(G);

  cout<<endl;

}

算法的时空分析 :

对于具有n个顶点e条边的无向图,当图采用邻接矩阵存储时,BFS算法的总时间为O()。

输入和输出的格式 :

   输入:

输入定点数和弧数:m  n

输入定点:

输入弧:

输出:

广度优先遍历:

深度优先遍历:

四、调试分析

    略。

五、测试结果

本实验的测试结果截图如下:

分析:如右图所示

六、用户使用说明(可选)

   1 、本程序的运行环境为windows 操作系统,执行文件为tu.exe

   2 、运行程序时

   提示输入数据 并且输入数据然后回车就可以继续输入相应数据,最后即可得到结果。

七、实验心得(可选)

本次实验设计内容比较多,虽然实验过程中多次出现问题,但通过多次调试最终得到解决。并且通过本次试验,对图的建立有了更深入的了解,对书上的代码进行了实现,熟悉并掌握了BFS、DFS算法,以及图的两种存储结构,对图结构的计算与运用有了进一步的体会。

附录(实验代码):

#include <iostream>

#define INFINITY 32767

#define MAX_VEX 20 //最大顶点个数

#define QUEUE_SIZE (MAX_VEX+1) //队列长度

using namespace std;

bool *visited;  //访问标志数组

//图的邻接矩阵存储结构

typedef struct{

  char *vexs; //顶点向量

  int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵

  int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

//队列类

class Queue{

  public:

  void InitQueue(){

    base=(int *)malloc(QUEUE_SIZE*sizeof(int));

    front=rear=0;

  }

  void EnQueue(int e){

    base[rear]=e;

    rear=(rear+1)%QUEUE_SIZE;

  }

  void DeQueue(int &e){

    e=base[front];

    front=(front+1)%QUEUE_SIZE;

  }

  public:

  int *base;

  int front;

  int rear;

};

//图G中查找元素c的位置

int Locate(Graph G,char c){

  for(int i=0;i<G.vexnum;i++)

  if(G.vexs[i]==c) return i;

  return -1;

}

//创建无向网

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<<"输入顶点:"<<endl;

  for(i=0;i<G.vexnum;i++){ //初始化顶点

         cout<<"输入顶点"<<i<<":";

    cin>>G.vexs[i];

    temp=getchar(); //接收回车

  }

  for(i=0;i<G.vexnum;i++) //初始化邻接矩阵

    for(j=0;j<G.vexnum;j++)

      G.arcs[i][j]=INFINITY;

  cout<<"输入弧:"<<endl;

  for(i=0;i<G.arcnum;i++){ //初始化弧

    cout<<"输入弧"<<i<<":";

    cin>>a>>b>>w; //输入一条边依附的顶点和权值

    temp=getchar(); //接收回车

    s1=Locate(G,a);

    s2=Locate(G,b);

    G.arcs[s1][s2]=G.arcs[s2][s1]=w;

  }}

//图G中顶点k的第一个邻接顶点

int FirstVex(Graph G,int k){

  if(k>=0 && k<G.vexnum){ //k合理

    for(int i=0;i<G.vexnum;i++)

      if(G.arcs[k][i]!=INFINITY) return i;

  }return -1;}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(Graph G,int i,int j){

  if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理

    for(int k=j+1;k<G.vexnum;k++)

      if(G.arcs[i][k]!=INFINITY) return k;

  }

  return -1;

}//深度优先遍历

void DFS(Graph G,int k){

  int i;

  if(k==-1){ //第一次执行DFS时,k为-1

    for(i=0;i<G.vexnum;i++)

      if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

  }

  else{

    visited[k]=true;

    cout<<G.vexs[k]; //访问第k个顶点

    for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))

if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS

  }}

//广度优先遍历

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);  } } }}

//主函数

void main(){

  int i;

  Graph G;

  CreateUDN(G);

  visited=(bool *)malloc(G.vexnum*sizeof(bool));

  cout<<"广度优先遍历: ";

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  DFS(G,-1);

  cout<<endl;

  cout<<"深度优先遍历: ";

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  BFS(G);

  cout<<endl;

}

更多相关推荐:
图的遍历实验报告

数据结构实验报告计科101冯康20xx00814128实验五图的基本操作一实验目的1使学生可以巩固所学的有关图的基本知识2熟练掌握图的存储结构3熟练掌握图的两种遍历算法二实验内容问题描述对给定图实现图的深度优先...

图的遍历实验报告(数据结构)

电子信息工程学系实验报告适用于计算机课程课程名称数据结构实验项目名称图的遍历操作实验时间班级计应102姓名学号实验目的掌握有向图和无向图的概念掌握邻接矩阵和邻接链表建立图的存储结构掌握DFS及BFS对图的遍历操...

数据结构课程实验(图的存储与遍历)

实验五图的存储与遍历1实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示以及在此两种常用存储方式下深度优先遍历dfs和广度优先遍历BFS操作的实现2实验预备知识1图的存储结构邻接矩阵表示法和邻接表表...

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

实验五图的遍历及其应用实现一实验目的1熟悉图常用的存储结构2掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现3会用图的遍历解决简单的实际问题二需求分析很多问题都是建立在图的遍历的基础上实现的所以必须...

数据结构图的遍历实验报告

题目图的遍历的实现完成日期20xx1222一需求分析1本演示程序中输入的数据类型均为整型数据不允许输入字符等其他数据类型且需要按照提示内容进行输入成对的关系数据必须在所建立的图中已经存在对应的结点2演示程序以用...

实现图的遍历算法实验报告

实现图的遍历算法1需求分析对于下图G编写一个程序输出从顶点0开始的深度优先遍历序列非递归算法和广度优先遍历序列非递归算法2系统设计1用到的抽象数据类型的定义图的抽象数据类型定义ADTGraph数据对象VV是具有...

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

数据结构集中上机试验报告学院计算机科学与技术专业计算机科学与技术学号00000000班级6姓名题目图的创建与遍历一需求分析很多问题都是建立在图的遍历的基础上实现的所以必须有一个程序能够实现将图进行广度和深度遍历...

图的基本操作 实验报告

实验五图的基本操作一实验目的1使学生可以巩固所学的有关图的基本知识2熟练掌握图的存储结构3熟练掌握图的两种遍历算法二实验内容问题描述对给定图实现图的深度优先遍历和广度优先遍历基本要求以邻接表为存储结构实现连通无...

二叉树的遍历及其应用实验报告

实验报告题目二叉树的遍历及应用院系数学系专业数学与应用数学学号20xx114036姓名郭奇瑞一实验名称二叉树的遍历及应用二实验日期20xx年11月14日三实验要求编程实现二叉树的建立并对其进行遍历四实验目的1掌...

西南科技大学数据结构实验报告图的存储和遍历

西南科技大学数据结构实验报告实验名称实验环境windows7VS20xx实验类别指导教师专业班级姓名学号一实验目的1掌握图的存储结构2学会深度优先搜索遍历3学会广度优先搜索遍历4学会非连通图的遍历5掌握图遍历算...

数据结构课程设计报告样本(图的存储与遍历)

这是最后提交的文档资料格式必须包含几个部分如果是四到五个人完成要求文档不少于70页34个人完成要求不少于50页数据结构课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录要求自动生成第一章课程设计...

图的基本操作实验报告

图的基本操作1数据结构实验报告书实验内容图的基本操作学院班级计算机学院计算机科学与技术姓名学号20xx008指导老师高老师图的基本操作2前言计算机编程中加工处理的对象是数据而数据具有一定的组织结构所以学习计算机...

图的遍历实验报告(32篇)