文档库

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

图的遍历实习报告

实习报告

问题:图的遍历

【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:";

cin>>a;

cout<<"深度优先遍历(DFS):"<

g.DFS(g,a); //深度优先搜索

cout<

cout<<"广度优先遍历(BFS):"<

g.BFS(g,a); //广度优先搜索

cout<

cout<<"输出相应的边集和相应的DFS的生成树:"<

Tree tree;

g.DFSTree(tree); //深度优先搜索生成树

tree.IntendedText();

tree.ShowTree();

cout<

return 0;

}

/////////////////深度优先搜索///////////////////////

template void Graph::DFS(Graph&G,const T& v)

{

inti,loc,n=G.NumberOfVertices(); //获取Vertices的个数

bool *visited=new bool[n];

for(i=0;i

loc=G.getVertexPos(v); //获取当前vertex的位置

DFS(G,loc,visited); //调用子过程

delete []visited;

}

/////////////////深度优先搜索子过程///////////////////////

template void Graph::

DFS(Graph&G,intv,bool visited[])

{

cout<

visited[v] = true; //顶点v作访问标记

int w = G.getFirstNeighbor(v); //找顶点v的第一个邻接顶点w while (w != -1)

{ //若邻接顶点w存在。#注意因为邻接顶点数目不定,使用循环语句,与树相同,与二叉树不同

if (visited[w] == false)

{ //若w未访问过, 递归访问顶点w

DFS(G,w, visited);

}

w = G.getNextNeighbor(v, w); //取v排在w后的下一个邻接顶点}

}

/////////////////广度优先搜索///////////////////////

template void Graph::

DFS(Graph&G,intv,bool visited[])

{

cout<

visited[v] = true; //顶点v作访问标记

int w = G.getFirstNeighbor(v); //找顶点v的第一个邻接顶点w

while (w != -1)

{ //若邻接顶点w存在。#注意因为邻接顶点数目不定,使用循环语句,与树相同,与二叉树不同

if (visited[w] == false)

{ //若w未访问过, 递归访问顶点w

DFS(G,w, visited);

}

w = G.getNextNeighbor(v, w); //取v排在w后的下一个邻接顶点}

}

//从图的顶点a出发,深度优先遍历图,

//建立以左子女-右兄弟链表表示的DFS生成森林。

template void Graph::DFSTree(Tree&tree){ TreeNode *p, *q;

int v, n = NumberOfVertices(); //取图中顶点个数

bool *visited = new bool[n]; //创建辅助数组

for (v = 0; v < n; v++){ //辅助数组visited初始化

visited[v] = false;

}

for(v = 0; v < n; v++){ //#从每个顶点开始,各做一次遍历。

if(!visited[v]){ //#借助辅助数组,上一趟遍历已访问过的各顶点不会作为新起点。所以输出了所有连通分量,不会重复。

p = new TreeNode(getValue(v));

if (!tree.getRoot()){

tree.setRoot(p);

}

else{

q->nextSibling = p;

}

q = p;

DFSTree(v, visited, p); //从顶点0开始深度优先搜索

}

}

delete [] visited; //释放visited

}

利用的树的相关操作输出这个树的结构和相应的边。

【5】运行结果:

从顶点B开始遍历:

图的遍历实习报告

从顶点F开始遍历:

图的遍历实习报告