山东大学数据结构实验报告七图的算法.doc

数据结构实验报告实验七实验题目： 图的算法学号： 201411130001 日期：2015.11.26班级：计机14.1姓名： 刘方铮Email：实验目的： 1、掌握图的基本概念，描述方法；遍历方法。任务要求：1、创建图类。二叉树的存储结构使用邻接矩阵或链表。2、提供操作:遍历、BFS、DFS3、 对建立好的图，执行上述各操作。4、 输出生成树。5、输出最小生成树。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验代码：#ifndef GRAPH_H#define GRAPH_H#include#include using namespace std;template class edge public: edge(int i,int j,int w) vertex1=i; vertex2=j;weight=w; edge(int i,int j) vertex1=i; vertex2=j;weight=1; T vertex1; T vertex2; T weight;template class graph public: graph() graph() virtual int numberOfVertices()=0; /返回图顶点数 virtual int numberOfEdges()=0; /返回图边数 virtual bool existsEdge(int,int)=0; /如果边（i,j）存在，返回true,否则返回false virtual void insertEdge(edge theEdge)=0; /插入边 virtual void eraseEdge(int,int)=0; /删除边 virtual int degree(int)=0; /返回顶点i的度，只用于无向图 virtual int inDegree(int)=0; /返回顶点i的入度 virtual int outDegree(int)=0; /返回顶点i的出度 virtual bool directed()=0; /若为有向图返回true virtual bool weighted()=0; /若为加权图返回true protected: private:;template class adjacencyWgraph : public graph /加权图的邻接矩阵结构 protected: int n; /顶点个数 int e; /边的个数 T *a; /邻接数组 T noEdge; /表示不存的边 T maxWeight;/最大权 public: adjacencyWgraph(int numberOfVertices =0 , T theNoEdge=0 ) if(numberOfVertices =0; return; n = numberOfVertices; e = 0; noEdge = theNoEdge; maxWeight=0; make2dArry(a,n+1,n+1); adjacencyWgraph() for(int i=0;i=n;i+) delete ai; delete a; a =NULL; int numberOfVertices() return n; int numberOfEdges() return e; bool weighted() return true; bool directed() return false; bool existsEdge(int i,int j) /返回值为真当且仅当（i,j）是图的一条边 if (i1 | jn | jn | aij=noEdge) return false; else return true; void insEdge(int i,int j,int w) /插入边 if(wmaxWeight) maxWeight=w; edge ed(i,j,w); insertEdge(ed); void eraseEdge(int i,int j) /删除边（i,j） if(i=1 & j=1 & i=n & j=n & aij!=noEdge) aij = noEdge; aji = noEdge; e-; bool checkVertex(int theVertex) /确定为有效顶点 if(theVertexn) return false; else return true; int degree(int theVertex)/返回顶点theVertex的度 if(!checkVertex(theVertex) coutno vertextheVertexendl; return -1; int sum=0; for(int i=1;i=n;i+) if(atheVertexi!=noEdge) sum+; return sum; int inDegree(int theVertex) coutinDegree() undefined; return 0; int outDegree(int theVertex) coutoutDegree() undefined; return 0; void output() /输出邻接矩阵 for(int i =1;i=n;i+) for(int j =1;j=n;j+) coutaij ; coutendl; void bfs(int v) int reachn+1; for(int i=1;i=n;i+)reachi=0; bfs1(v,reach,-1); void dfs(int v) int reachn+1; for(int i=1;i=n;i+)reachi=0; dfs1(v,reach,-1); void makeTree(int v) /输出生成树 adjacencyWgraph awg0(n,noEdge); int reachn+1; for(int i=1;i=n;i+)reachi=0; queue *q=new queue(); reachv =-1; q-push(v); while(!q-empty() int w =q-front(); q-pop(); for(int u=1;upush(u); reachu=-1; cout生成树邻接矩阵：endl; awg0.output(); cout生成树bfs：endl; awg0.bfs(v);coutendl; void makeMinTree(int theVertex) /输出最小生成 adjacencyWgraph awg1(n,noEdge); for(int i=1;i=n;i+) for(int j=1;j=n;j+) awg1.aij=aij; int *reach; make2dArry(reach,n+1,n+1); for(int k=1;k=(e-n+1);k+)/删除多余的边 awg1.findMaxWeight(maxWeight,reach,-1); for(int h=0;h=n;h+) delete reachh; delete reach; reach =NULL; cout最小生成树邻接矩阵：endl; awg1.output(); cout最小生成树bfs：endl; awg1.bfs(theVertex); void findMaxWeight(int w,int *&reach,int lable) /找到“最大权”，删除边 int num=noEdge,row,col; for(int i=1;i=n;i+) /找到“最大权”边 for(int j=1;j=num & reachij!=lable & aij=w) num=aij; row=i;col=j; reachrowcol=lable; reachcolrow=lable; if(degree(row)=1 | degree(col)=1)/边不能删 findMaxWeight(num,reach,lable); else /删除边 eraseEdge(row,col); private: void make2dArry(T * &x,int rows,int clos) /创建二维数组 x = new T *rows; /创建行指针 for(int i=0;irows ;i+) /为每一行分配空间 xi=new T clos; for(int j=0; jrows;j+) /初始化邻接矩阵 for(int k=1;k=clos;k+) xjk = noEdge; void insertEdge(edge theEdge) /插入边，如果该边已存在，则修改权值 int v1=theEdge.vertex1; int v2=theEdge.vertex2; if(v11 | v2n | v2n | v1=v2) cout (v1,v2) is not a permissible edge; return; if(av1v2 = noEdge)/新的边 e+; av1v2 = theEdge.weight; av2v1 = theEdge.weight; void bfs1(int v,int reach,int lable) /广度先搜索，reachi用来标记所有邻接顶点v的可达到顶点 queue *q=new queue(); reachv =lable; q-push(v); while(!q-empty() int w =q-front(); q-pop(); coutw ; for(int u=1;upush(u); reachu=lable; void dfs1(int v,int reach,int lable) reachv=lable;coutv ; int i=1; while(avi=noEdge | reachi=lable) i+; if(in+1) v=i; dfs1(v,reach,lable); ;#endif / GRAPH_H#include #include using namespace std;int main() adjacencyWgraph awg(8,0); awg.insEdge(1,2,5); awg.insEdge(1,3,4); awg.insEdge(1,4,10); awg.insEdge(2,5,30); awg.insEdge(3,5,25); awg.insEdge(4,6,2); awg.insEdge(4,7,60); awg.insE