文档库

最新最全的文档下载
当前位置:文档库 > 图的遍历实习报告

图的遍历实习报告

实习报告

问题:图的遍历

【1】问题描述:

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示无向图的遍历操作。

【2】求解思路:

首先创建一个用邻接表表示的图,图的初始赋值是用文本输入进行的,因此在赋值前应对其中的“》”操作符进行重载,从而建立一个图。利用DFS函数和BFS函数分别实现对图的遍历访问并输出相应的访问序列,对于输出相应的生成树的边的操作时,可以采用深度优先搜索的结果的对应的生成树输出即可,此时便要定义一个DFStree函数来实现,故也要用到树的数据结构。

【3】采用的数据结构:

本题主要采用的数据结构主要是图、树、链表、循环队列、最小生成堆。

【4】程序实现说明:

定义一个Graphlnk,然后对Graphlnk进行初始化。调用DFS函数和函数BFS输出该Graphlnk的深度优先搜索和广度优先搜索,然后调用DFStree函数来生成这个深度优先搜索的生成树,同时再调用ShowTree()函数来输出生成树的结构和相应的边。程序清单:

// 图的遍历.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"

#include "Graph.h"

#include "Graphlnk.h"

#include

#include

using namespace std;

int _tmain(intargc, _TCHAR* argv[])

{

Graphlnk g; //定义一个邻接表表示的图对象

ifstream fin("data.txt"); //采用文本输入对图进行初始化

assert(fin);

fin>>g;

cout<< g; //输出对应的图

char a; //开始遍历的Vertex

cout<<"请输入遍历的开始Vertex:";

图的遍历实习报告

(共4页)