数据结构与算法分析

深度优先搜索和广度优先搜索算法实现

四川大学软件学院 学生实验报告

实验名称：数据结构与算法分析

深度优先搜索和广度优先搜索算法实现

实验报告

班级 __ 姓名 学号

一、实验号题目:深度优先搜索和广度优先搜索算法实现 二、实验的目的和要求: 1.采用C++实现; 2.熟练掌握图的应用;

3.熟练掌握图的邻接表存储结构以及拓扑排序的基本思想。 4.上机调试程序,掌握查错、排错使程序能正确运行。 三、实验的环境: 1.硬件环境: 2.软件环境:

（1）操作系统windowsXP SP2。 （2）编译系统Mingw32 2.95

C-Free开发工具: Borland C++ Builder 6.0 C-Free中使用的编译系统: Mingw32 2.95 C-Free中使用的调试系统: GDB 5.2.1 C-Free中使用的VCL组件: SynEdit1.1

（3）编辑软件特点

使用c-Free自带的编辑软件，C-Free的智能输入功能能够大大提高你的代码编写速度，它能够

记住你已经输入的所有标识符、关键字，下一次输入标识符时，你不需要输入全部的标识符名称，输入一到二个字母，编辑窗口中会出现你需要的标识符。

四、算法描述:

深度优先搜索

深度优先搜索类似于树的先根遍历。假设给定图G的初态是所有顶点均未访问过，在G中任选一顶点v为初始出发点，则深度优先搜索可定义如下：首先，访问出发点v，并将其标记为已访问过，然后依次从v的未被访问过的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。

深度优先搜索和广度优先搜索算法实现

广度优先搜索

广度优先搜索类似于树的按层次遍历的过程。从图中的某个顶点v0出发，在访问v0之后依次访问v0的所有未被访问过的邻接点w1,w2,w3,…wk，然后按这些邻接点被访问的先后次序依次从w1,w2,w3,…wk出发访问它们的邻接点，如此下去，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

五、源程序清单:

#include <iostream.h> #include <stdlib.h> #include <stdio.h> #include <assert.h> #include <ctype.h>

// Used by the mark array #define UNVISITED 0 #define VISITED 1

// Graph abstract class

class Graph { public:

// Return the number of vertices

深度优先搜索和广度优先搜索算法实现

virtual int n() =0;

// Return the current number of edges virtual int e() =0;

// Return the index of the first neigbor of given vertex virtual int first(int) =0;

// Return the index of the next neigbor of given vertex virtual int next(int, int) =0;

// Store an edge defined by two vertices and weight virtual void setEdge(int, int, int) =0; // Delete edge defined by two vertices

virtual void delEdge(int, int) =0;

// Return weight of edge connecting two vertices // Return 0 if no such edge exists virtual int weight(int, int) =0; // Get mark value for a vertex virtual int getMark(int) =0; // Set mark value for a vertex virtual void setMark(int, int) =0; };

class Edge{

public:

int vectex,weight;

Edge() {vectex = -1;weight = -1; }

Edge(int v,int w) {vectex =v; weight =w;} };

class Graphm : public Graph { // Implement adjacency matrix private:

int numVertex, numEdge; // Store number of vertices, edges int **matrix; // Pointer to adjacency matrix int *mark; // Pointer to mark array

public:

Graphm(int numVert) { // Make graph w/ numVert vertices int i, j;

numVertex = numVert; numEdge = 0;

mark = new int[numVert]; // Initialize mark array for (i=0; i<numVertex; i++) mark[i] = UNVISITED;

matrix = (int**) new int*[numVertex]; // Make matrix for (i=0; i<numVertex; i++)

matrix[i] = new int[numVertex];

for (i=0; i< numVertex; i++) // Edges start w/ 0 weight

深度优先搜索和广度优先搜索算法实现

for (int j=0; j<numVertex; j++) matrix[i][j] = 0; }

~Graphm() { // Destructor

delete [] mark; // Return dynamically allocated memory for (int i=0; i<numVertex; i++) delete [] matrix[i]; delete [] matrix; }

int n() { return numVertex; } // Number of vertices int e() { return numEdge; } // Number of edges

int first(int v) { // Return v's first neighbor int i;

for (i=0; i<numVertex; i++) if (matrix[v][i] != 0) return i; return i; // Return n if none }

int next(int v1, int v2) { // Get v1's neighbor after v2 int i;

for(i=v2+1; i<numVertex; i++) if (matrix[v1][i] != 0) return i; return i; }

// Set edge (v1, v2) to wgt

void setEdge(int v1, int v2, int wgt) { Assert(wgt>0, "Illegal weight value"); if (matrix[v1][v2] == 0) numEdge++; matrix[v1][v2] = wgt; }

void delEdge(int v1, int v2) { // Delete edge (v1, v2) if (matrix[v1][v2] != 0) numEdge--; matrix[v1][v2] = 0; }

int weight(int v1, int v2) { return matrix[v1][v2]; } int getMark(int v) { return mark[v]; } void setMark(int v, int val) { mark[v] = val; } };

深度优先搜索和广度优先搜索算法实现

// Abstract queue class

template <class Elem> class Queue { public:

// Reinitialize the queue. The user is responsible for // reclaiming the storage used by the stack elements. virtual void clear() = 0;

// Place an element at the rear of the queue. Return // true if successful, false if not (if queue is full). virtual bool enqueue(const Elem&) = 0;

// Remove the element at the front of the queue. Return // true if succesful, false if queue is empty.

// The element removed is returned in the first parameter. virtual bool dequeue(Elem&) = 0; // Remove Elem from front // Return in first parameter a copy of the front element. // Return true if succesful, false if queue is empty. virtual bool frontValue(Elem&) const = 0; // Return the number of elements in the queue. virtual int length() const …… 此处隐藏：4367字，全部文档内容请下载后查看。喜欢就下载吧 ……