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

文档介绍：山东大学软件工程学院
数据结构课程实验报告
 
学号:
姓名:
班级: 软件工程2014级2班
实验题目: 图的操作
实验学时:
实验日期:
实验目的:
掌握图的基本概念,描述方法;遍历方法。
硬件环境: 
实验室
软件环境:
Vistual Studio 2013

实验步骤与内容:
实验内容:
1、创建图类。二叉树的存储结构使用邻接矩阵或链表。
2、提供操作:遍历、BFS、DFS
3、对建立好的图,执行上述各操作。
4、输出生成树。
5、输出最小生成树。
代码体:

#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

#include<iostream>
#include<queue>
using namespace std;
#include ""
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