深度优先搜索和广度优先搜索算法实现
四川大学软件学院 学生实验报告
实验名称：数据结构与算法分析
深度优先搜索和广度优先搜索算法实现
实验报告
班级 __ 姓名 学号
一、实验号题目:深度优先搜索和广度优先搜索算法实现 二、实验的目的和要求: 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; } };
深度优先搜索和广度优先搜索算法实现