数据结构与算法分析

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

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

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

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

实验报告

班级 __ 姓名 学号

一、实验号题目:深度优先搜索和广度优先搜索算法实现 二、实验的目的和要求: 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 = 0; };

// Array-based queue implementation

template <class Elem> class AQueue: public Queue<Elem> { private:

int size; // Maximum size of queue int front; // Index of front element int rear; // Index of rear element

Elem *listArray; // Array holding queue elements public:

AQueue(int sz =DefaultListSize) { // Constructor

// Make list array one position larger for empty slot size = sz+1;

rear = 0; front = 1; listArray = new Elem[size]; }

~AQueue() { delete [] listArray; } // Destructor void clear() { front = rear; } bool enqueue(const Elem& it) {

if (((rear+2) % size) == front) return false; // Full rear = (rear+1) % size; // Circular increment listArray[rear] = it; return true;

}

bool dequeue(Elem& it) {

if (length() == 0) return false; // Empty

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

it = listArray[front];

front = (front+1) % size; // Circular increment return true; }

bool frontValue(Elem& it) const { if (length() == 0) return false; // Empty it = listArray[front]; return true; }

virtual int length() const

{ return ((rear+size) - front + 1) % size; } };

void PreVisit(Graph* G, int v) {

cout << "PreVisit vertex " << v << "\n"; }

void PostVisit(Graph* G, int v) {

cout << "PostVisit vertex " << v << "\n"; }

void DFS(Graph* G, int v) { // Depth first search PreVisit(G, v); // Take appropriate action G->setMark(v, VISITED);

for (int w=G->first(v); w<G->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED)

DFS(G, w); PostVisit(G, v); // Take appropriate action }

void BFS(Graph* G, int start, Queue<int>* Q) { int v, w;

Q->enqueue(start); // Initialize Q G->setMark(start, VISITED);

while (Q->length() != 0) { // Process all vertices on Q Q->dequeue(v);

PreVisit(G, v); // Take appropriate action for (w=G->first(v); w<G->n(); w = G->next(v,w)) if (G->getMark(w) == UNVISITED) { G->setMark(w, VISITED);

Q->enqueue(w); }

PostVisit(G, v); // Take appropriate action

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

}

}

// Test Depth First Search and Breadth First Search int main(int argc,char *argv[]){

Graph* g=new Graphm(6);// Initialize a graphm g int chance; g->setEdge(0,2,1); g->setEdge(2,0,1); g->setEdge(2,1,1); g->setEdge(1,2,1); g->setEdge(1,5,1); g->setEdge(5,1,1); g->setEdge(2,5,1); g->setEdge(5,2,1); g->setEdge(3,5,1); g->setEdge(5,3,1); g->setEdge(2,3,1); g->setEdge(3,2,1); g->setEdge(4,5,1); g->setEdge(5,4,1);

g->setEdge(0,4,1); g->setEdge(4,0,1);

cout<<"enter the number "<<endl<<"1 to do the Depth First Search "<<endl <<"2 to do Breadth First Search"<<endl; cin>>chance; if( chance == 1){

cout<<"the Depth First Search is"<<endl; DFS(g,0); }

else if(chance== 2){

AQueue<int>* q=new AQueue<int>(6); // Initialize q cout<<"the Breadth First Search is"<<endl; BFS(g,0,q); }

else {

cout<<"you enter the wrong number"<<endl; } return 0; }

六、运行结果:

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

七、实验运行情况分析.

算法: 图和队列都是使用的数组实现的,但用邻接矩阵实现图的时候要注意, void setEdge(int v1, int v2, int wgt) 中在图的实例化的时候wgt为0是表示的是 int1和int2没有连通,但在用邻接表实现图的时候wgt为1表示这条边上的权是1; 图和队列使用的数组实现,虽然代码短些但是增大了使用的空间.

深度优先搜索和广度优先搜索花费的时间都是样的,定点数的平方.

本文来源：https://www.bwwdw.com/article/88dm.html