《2023年山东大学数据结构实验报告七》由会员分享，可在线阅读，更多相关《2023年山东大学数据结构实验报告七（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验七实验题目： 图的算法学号： 日期：2023.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 publi
2、c: 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; /
3、假如边（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()=
4、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
5、= 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）是图的一条
6、边 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 theVert
7、ex) /拟定为有效顶点 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; retur
8、n 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,re
9、ach,-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);cout
