山东大学数据结构实验报告八.docVIP

山东大学 软件工程 学院 数据结构 课程实验报告 ? 学号： 姓名： 班级： 软件工程2014级2班 实验题目： 图的操作 实验学时： 实验日期： 2015.12.9 实验目的： 掌握图的基本概念，描述方法；遍历方法。 硬件环境：? 实验室 软件环境： Vistual Studio 2013 实验步骤与内容 实验内容： 1、创建图类。二叉树的存储结构使用邻接矩阵或链表。 2、提供操作:遍历、BFS、DFS 3、对建立好的图，执行上述各操作。 4、输出生成树。 5、输出最小生成树。 代码体： Adjacencywdigraph.h #ifndef ADJACENCYWDIGRAPH_H #define ADJACENCYWDIGRAPH_H class AdjacencyWDigraph{ friend class AdjacencyWGraph; public: AdjacencyWDigraph(int Vertices = 10, int noEnge = 0); ~AdjacencyWDigraph(); bool Exist(int i, int j) const; int Edges() const{ return e; } int Vertices() const{ return n; } AdjacencyWDigraph Add(int i, int j, const int w = 1); AdjacencyWDigraph Delete(int i, int j); int OutDegree(int i) const; int InDegree(int i) const; void InitializePos() { pos = new int[n + 1]; } void DeactivatePos() { delete[] pos; } int Begin(int i); int NextVertex(int i); void BFS(int v, int reach[], int label = 1); void DFS(int v, int reach[], int label = 1); bool Connected(int x); int** SpanningTree(); int** SpanningMinTree(); void OutPut(); private: int MinNum(); int Min(int v, int reach[]); bool Connecting(int i); void dfs(int v, int reach[], int label); int NoEdge, n, e; int **a; int *pos; }; #endif Adjacencywdigraph.cpp #includeiostream #includequeue using namespace std; #include adjacencywdigraph.h AdjacencyWDigraph::AdjacencyWDigraph(int Vertices, int noEdge){ n = Vertices; e = 0; NoEdge = noEdge; a = new int*[n + 1]; for (int i = 1; i = n; i++) a[i] = new int[n + 1]; for (int i = 1; i = n; i++) for (int j = 1; j = n; j++) a[i][j] = NoEdge; } AdjacencyWDigraph::~AdjacencyWDigraph(){ for (int i = 1; i = n; i++) delete[] a[i]; delete[] a; } bool AdjacencyWDigraph::Exist(int i, int j) const{ if (i 1 || j 1 || i n || j n || a[i][j] == NoEdge) return false; return true; } AdjacencyWDigraph AdjacencyWDigraph::Add(int i, int j, const int w){ if (i 1 || j 1 || i n || j n) cout 错误!点 i 或点 j 不存在,无法添加边 endl; els