图的遍历算法

数据结构

7.3 图的遍历回顾其他数据结构的遍历： 顺序表的遍历 单链表的遍历 二叉树、树和森林的遍历 问题： 那么对于图，我们怎样进行遍历呢？ (需要记录访问过顶点的信息，引入visited[0…n-1]) 图的深度优先遍历 图的广度优先遍历 这两个算法是后面拓扑排序、求关键路径算法的基础

数据结构

7.3.1.连通图的深度优先遍历 类似于树的先根遍历，是其推广

数据结构

算法描述:

1.深度优先遍历以v开始的连通图① 访问v ② 分别深度优先遍历v的各个未被 访问的邻接点

数据结构

2.算法演示

数据结构

例图及其邻接表表示

01 v1 v2 v3

v1

2 v2v3

v1v1

v4v6

v5v7

v2

3 V3 4 V4

v2v2

v8v8

v4

v5

v6

v7

5 v5 6 v6 7 v7 8 v8

v8

v3v3

v7v6

v4

v5

数据结构

演示开始，以v1为遍历的起点

数据结构

0v1

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2v2

v8v8

v3v3

v7v6

v4

v5

数据结构

0v1 ,

1 v1

v2

v3

2 v2 3 V3 4 V45 v5 6 v6 7 v7 8 v8

v1v1

v4v6

v5v7

v2v2

v8v8

v3

第二章部分习题参考答案

1.证明下列结论：

1）在一个无向图中，如果每个顶点的度大于等于2，则该图一定含有圈； 证明：设无向图最长的无重复顶点的迹P?V0V1?Vk,（若含有重复顶点，则取重复顶点及其之间的点，即可构成一个圈）。由于每个顶点度大于等于2，故存在与V1相异的点V'与V0相邻，若V'?P,则得到比P更长的迹，与P的取法矛盾。因此，V'?P，从而V0V1?V'V0是闭迹，又顶点无重复故存在圈V0V1?V'V0. 其他证明方式二：设在无向图G中，有n个顶点，m条边。由题意知，m>=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m>=n>n-1，故该图一定含有圈。

证明方式三：（201228015029012 皇甫杨）

逆否命题：在一个无向图中，若该图没有圈，则必存在顶点的度数小于2。 ∵ 该图没有圈 ∴ 该图为森林

∵ 森林是由树组成的，且树中必包含叶子结点 ∵ 叶子结点的度为1 ∴逆否命题得证。

（定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。） 2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。

证明

关于图的遍历的数据结构课程设计

图的遍历

课 程 设 计

题 目 教 学 院 专 业 班 级 姓 名 指导教师

图的遍历 计算机

2011 年 12 月 31 日

关于图的遍历的数据结构课程设计

课程设计任务书

2010 ～2011 学年第1 学期

学生姓名： 专业班级：

指导教师： 工作部门：

一、课程设计题目

图的遍历

二、课程设计内容（含技术指标）

1．显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。 2．当用户选择的功能错误时，系统会输出相应的提示。 3．通过图操作的实现，把一些实际生活中的具体的事物抽象出来

三、进度安排

1．初步完成总体设计，搭好框架；

2．完成最低要求：两种必须都要实现，写出画图的思路；

3．进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。

四、基本要求

1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案

关于图的遍历的数据结构课程设计

目 录

一 概述 .............................................1

1.问题描述 ………………………

关于图的遍历的数据结构课程设计

图的遍历

课 程 设 计

题 目 教 学 院 专 业 班 级 姓 名 指导教师

图的遍历 计算机

2011 年 12 月 31 日

关于图的遍历的数据结构课程设计

课程设计任务书

2010 ～2011 学年第1 学期

学生姓名： 专业班级：

指导教师： 工作部门：

一、课程设计题目

图的遍历

二、课程设计内容（含技术指标）

1．显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。 2．当用户选择的功能错误时，系统会输出相应的提示。 3．通过图操作的实现，把一些实际生活中的具体的事物抽象出来

三、进度安排

1．初步完成总体设计，搭好框架；

2．完成最低要求：两种必须都要实现，写出画图的思路；

3．进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。

四、基本要求

1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案

关于图的遍历的数据结构课程设计

目 录

一 概述 .............................................1

1.问题描述 ………………………

实验五图的表示与遍历

一、实验目的

1、掌握图的邻接矩阵和邻接表表示

2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法

二、实验预习

说明以下概念

1、深度优先搜索遍历：

从根开始一个一个搜索 2、广度优先搜索遍历：

从根的邻接点出发依次访问 3、拓扑排序：

一个无指向的点开始排序 4、最小生成树： 最小权的生成树 5、最短路径： 路径权数最小

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。 #include #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);

摘要

《数据结构》作为信息类专业的一门核心专业课，对《编译原理》等后续课程的学习极其重要。

传统的《数据结构》算法是基于以Turbo C为代表的DOS开发坏境，可视化效果很差。而这种坏境给学习者的理解和深入探讨带来很大的问题。本设计从对数据结构图的算法的深入研究开始，在Visual C++的编程坏境下，致力于开发一套专门帮助学习者理解数据结构算法的动态演示系统。该系统将可视性，交互性和可扩展性紧紧的结合在一起，能大大改善传统教学的弊端，使复杂的难以理解的数据结构算法通过教师的课堂演示和学习者的不断自我交互式操作试验变得通俗明朗，有效地提高教学的质量和效果。

关键字：动态演示系统；Visual C++

I

Abstract

The data structure as a core of information specialty courses, learning to follow-up such as the compiling principles of course extremely important.

Traditional algorithm is based on the data structure to DOS deve

武汉理工大学《数据结构》课程设计说明书

学 号：

课 程 设 计

题 目 学 院 专 业 班 级 姓 名 指导教师

图的遍历的实现

计算机科学与技术学院

软件工程

2013 年 12 月 23 日

1

武汉理工大学《数据结构》课程设计说明书

课程设计任务书

学生姓名： 专业班级： 指导教师： 工作单位：计算机科学与技术学院 题 目: 图的遍历的实现 初始条件：

理论：学习了《数据结构》课程，掌握了一种计算机高级语言。 实践：计算机技术系实验中心提供计算机及软件开发环境。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

1、系统应具备的功能： 1)先任意创建一个图；

2)图的DFS,BFS的递归或非递归算法的实现 3)要求用有向图或无向图分别实现

4)要求用邻接矩阵、邻接表多种结构存储实现 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现；

5、撰写课程设计报告，包括： （1）设计题目；

（2）摘要和关键字（中文和英文）；

（3）正文，包括引言、需求分析

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

一． 实验目的

熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。

二． 实验原理

深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10

typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex;

struct ArcNode *nextarc; }ArcNode;

typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList v