电子信息工程学系实验报告 ——适用于计算机课程

课程名称： 数据结构                            

实验项目名称： 图的遍历操作             实验时间：

班级：计应102             姓名：        学号：

                                                                                                                                             

实验目的：

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

实验内容：

题目：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。

要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS遍历。

测试数据：

０　１　０　０　０

１　０　０　０　１

０　１　０　１　０

１　０　０　０　０

０　０　０　１　０

 

实验要求：

按要求编写实验程序，将实验程序调试运行，写出在各种图的遍历方法中，输入测试数据所得的结果，并提交实验报告，写出调试运行的分析和体会。

 

实验结果：

 

 

 

实验总结：

逻辑结构：邻接矩阵

Dfs遍历：利用了递归的方法，开始访问一个节点的邻接节点 再访问这个节点的邻接节点 然后再访问另外一个邻接节点、依次下去 得以访问所有的节点、

通过这次试验，熟悉了递归的使用、对图的遍历方式更加理解了、

BFS遍历：这里利用了队列这种数据结构，原理是先访问所有节点的全部邻接节点，再访问邻接节点的全部节点、这样一层层下去。

 

 

实验源代码

#include <iostream>

#include <queue>

#define N 5

using namespace std;

int vi[N];

void print(int i)

{

      printf("%c ",i+'a');

}

void connect(int a[N][N],int start)

{

      for(int i=0;i<N;++i)

      {

            if(vi[i]==0&&a[start][i]==1)

            {

                  print(i);

                  vi[i]=1;

                  connect(a,i);

            }

           

      }

}

void DFS(int a[N][N],int start)

{

      memset(vi,0,sizeof(vi));

      connect(a,start);

      for(int i=0;i<N;++i)

      {

            if(!vi[i])

            print(i);

      }   

}

void BFS(int a[N][N],int start)

{

      int d;

      memset(vi,0,sizeof(vi));

      queue<int> temp;

      temp.push(start);

      while(!temp.empty())

      {

            d=temp.front();

            temp.pop();

            print(d);

            vi[d]=1;

            for(int i=0;i<N;++i)

            {

                  if(vi[i]==0&&a[d][i]==1)

                        temp.push(i);

            }

      }

      for(int i=0;i<N;++i)

      {

            if(!vi[i])

            print(i);

      }   

}

int main()

{

      int a[N][N]={

            0,1,0,0,0,

            1,0,0,0,1,

            0,1,0,1,0,

            1,0,0,0,0,

            0,0,0,1,0,

      };

      printf("DFS遍历:");

      DFS(a,0);

      printf("\n");

      printf("BFS遍历:");

      BFS(a,0);

      printf("\n");

      return 0;

}

 

第二篇：数据结构图实验报告