实验五  图的基本操作

一、实验目的

1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容

[问题描述]

　　对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]

　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

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

三、实验前的准备工作

1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求

1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

编程思路：

深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。

  度优先搜索算法：又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话 说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

         以临接链表作为存储结构，结合其存储特点和上面两种算法思想，给出两种遍历步骤：

（1）既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。

（2）要遍历到图中所有顶点，只需多次调用 从某一顶点出发遍历图的算法。所以，下面只考虑从某一顶点出发遍历图的问题。

（3）为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组 visited[n]，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。

（4）这就是遍历次序的问题，图的遍历通常有深度优先遍历和广度优 先遍历两种方式，这两种遍历次序对无向图和有向图都适用。

1、深度优先遍历   从图中某顶点v出发进行深度优先遍历的基本思想是：

（1）访问顶点v；

（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；

（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

2、广度优先遍历   从图中某顶点v出发进行广度优先遍历的基本思想是：

（1）访问顶点v；

（2）依次访问v的各个未被访问的邻接点v1，v2，……vk；

（3）分别从v1，v2，……vk出发依次访问它们未被访问的邻接点， 并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有与顶点v有路径的顶点都被访问到。广度优先遍历图是以顶点v为起始点，由 近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储 访问的顶点。

代码解析：

#define MAXVEX 100

int visited[MAXVEX];

int n;

struct edgenode{

    int adjvex;//临接结点序号

    int info;  //临接结点信息

    edgenode*next;

};连接结点的存储类型

struct vexnode{

    int data;//结点信息

    int No;

    edgenode*link;

};数组结点类型

/*BFS遍历时所需存储类型*/

struct queue{

    int front,rear;

    edgenode**base;

};

typedef vexnode adjlist[MAXVEX];

采用用户交换模式来创建临接链表：

void CreatGroup(adjlist&g,int&n){

    int e,s,d;   printf("输入结点(n)个数和边(e)个数:");    cin>>n>>e;

    for(int i=0;i<n;i++){//创建结点数组

        printf("\n输入第%d个结点信息No=",i);  scanf("%d",&g[i].data);

        g[i].link=NULL;

    }

    /*建立临接链表，创建的是有向图*/

    for(int i=0;i<e;i++){

        printf("第%d条边=>\n\t起点序号，终点序号：",i+1);

        cin>>s>>d;//表示弧由s指向d

        edgenode*p=new edgenode;

        /*每一个点的临接结点没有顺序，为了插入p->adjvex方便每次插入结点都插入在临接表的首位置，这样后插入的结点反而在前面*/

        p->adjvex=d;  p->info=g[d].data;  p->next=g[s].link;   g[s].link=p;

         }

}

void DFS(adjlist g,int v){

    visited[v]=0;    printf("%d==>",v);//遍历过的结点用visited[v]=0进行标记

    edgenode*p=g[v].link;//查找连接结点

    while(p) {

        if(visited[p->adjvex])

            DFS(g,p->adjvex);  p=p->next;           

    }

}

/*广度优先搜索法(类似于树的层次遍历法)*/

void BFS(adjlist g,int v){

    visited[v]=0;

    printf("%d==>",v);

    queue Q;

    edgenode*p=g[v].link;

    Q.base=new edgenode*[MAXVEX];

    Q.front=Q.rear=0;

    Q.base[Q.rear++]=p;

    while(Q.front!=Q.rear) {        

        visited[Q.base[Q.front]->adjvex]=0;

        printf("%d==>",Q.base[Q.front]->adjvex);

        while(p) {

            if(visited[p->adjvex])  Q.base[Q.rear++]=p;

           p=p->next;

        }

        p=g[Q.base[++Q.front]->adjvex].link;      

    }   

}

心得体会：

数据结构顾名思义讲求的是一种存储结构，一路走来先后学习了表、树，最后学习的是图，对于每种存储结构学习之初都会学习一些基本操作，而操作之中又以创建和遍历为最基本的操作，只有熟练掌握了以后才能对其他操作进行研究和学习。

图的存储结构相比表和树都要复杂，其操作过程也较难进行掌握。仅仅是创建图的存储结构便分为矩阵、临接链表、十字链表等，对于每一种存储结构又分为有向与无向之分。然而，深度优先和广度优先是两种算法，其算法思想并不依赖与元素的存储方式，也就是说算法思想不会因为存储结构的改变而发生改变，当然对于不同的存储结构仅仅是代码的表现形式不同而已，正所谓一同百通，只要熟悉存储结构的特点又对算法思想烂熟于心便可无往不胜。

 

第二篇：图遍历实验报告

中南民族大学管理学院

        学生实验报告

实验项目：     图的遍历

课程名称：     数据结构

年    级：      2009

   专   业：信息管理与信息系统

指导老师：     李超锋

    实验地点：管理学院综合实验室

   完成日期：2010年11月18日

  小组成员：赵纯龑 09056045

彭瑶   09056054

图的遍历

一． 简介

需求分析

概要设计

详细设计

调试分析

用户手册

测试结果

二.  需求分析

1.掌握图的邻接矩阵和邻接表表示.掌握图的深度优先和广度优先搜索方法

2.图的结点不多于30个，每个结点用一个编号表示（如一个图有 N个结点，则他们的编号分别为1、2、3…….n).通过输入图的全部边输入一个图

3.本程序的对象如下图：                                 

               

4.输入数据

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

三   概要分析

实现图转变为邻接矩阵和邻接表表示

并且实现图的深度优先和广度优先搜索

| 函数模块如下

四   详细分析

| #include<stdio.h>

| #define N 20

| #define TRUE 1

| #define FALSE 0

| int visited[N];   

| typedef struct    /*队列的定义*/

| {

|     int data[N];

|     int front,rear;

| }queue;

| typedef struct    /*图的邻接矩阵*/

| {

|     int vexnum,arcnum;

|     char vexs[N];

|     int arcs[N][N];

| }

| graph;void createGraph(graph *g);  /*建立一个无向图的邻接矩阵*/

| void dfs(int i,graph *g);    /*从第i个顶点出发深度优先搜索*/

| void tdfs(graph *g);          /*深度优先搜索整个图*/

| void bfs(int k,graph *g);    /*从第k个顶点广度优先搜索*/

| void tbfs(graph *g);          /*广度优先搜索整个图*/

| void init_visit();            /*初始化访问标识数组*/

五   调试分析

六   用户说明

七   心得体会