实验九：图的基本操作.doc

湖南农业大学信息科学技术学院学 生 实 验 报 告姓名： 年级专业班级 日期 年 月 日 成绩 课程名称数据结构实验名称图的基本操作 实验类型验证 设计综合 创新【实验目的、要求】（1） 熟悉VC+的上机环境，掌握VC+语言的编程过程（2） 会定义图的邻接矩阵及图的邻接表的存储结构（3） 熟悉以图的邻接矩阵及图的邻接表表示的图的基本操作【实验内容】（1） 对一个图（图的形式自构建）按邻接矩阵建立，实现其深度、广度算法、求最小生成树（PRIM算法和Kruskal算法）（2） 对一个图（图的形式自构建）按邻接表建立，实现其深度、广度算法、求最小生成树（PRIM算法和Kruskal算法）【实验环境】（含主要设计设备、器材、软件等）运行VC+的电脑一台【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）Maing1.createGraph(5,vert,10,edge1);g1.depthFirstSearch(); g1.breadthFirstSearch(); #include typedef int dataType; /抽象数据类型dataType定义为intclass Queue1 /顺序循环队列类 /数组元素类型为抽象数据类型dataType dataType *table; /指向数组的指针 int size; /队列的数组容量 int front,rear; /front、rear为队列首尾下标 public: Queue1(int n=0); /初始化长度为n的空队列 Queue1(); bool isEmpty(); /判断队列的状态是否为空 bool isFull(); /判断队列的状态是否已满 bool enQueue(const dataType k); /入队 dataType deQueue(); /出队 friend ostream& operator(ostream& out,Queue1 &q); ;Queue1:Queue1(int n) /初始化长度为n的空队列 table=new dataTypen; /为队列分配n个存储单元 size=n; front=rear=0; /设置队列为空Queue1:Queue1() /析构函数 delete table; size=0; front=rear=0;bool Queue1:isEmpty() /判断队列的状态是否为空 return front=rear;bool Queue1:isFull() /判断队列的状态是否已满 return front=rear % size + 1;bool Queue1:enQueue(const dataType ch)/数据元素ch入队 if(!isFull() /队列不满时 tablerear=ch; rear=(rear+1) % size; return true; else cout队列已满，ch值无法入队列！n; return false; /队列溢出 dataType Queue1:deQueue() /出队 dataType ch=0; if(!isEmpty() /队列不空 ch=tablefront; /取得队首数据元素值 front=(front+1) % size; return ch;ostream& operator(ostream& out,Queue1 &q)/输出队列中各数据元素值 int i=q.front; while(!q.isEmpty() & iq.rear) coutq.tablei ; i=(i+1) % q.size; coutendl; return out;struct EdgeNode1 /带权值的边 int init; /边的起点 int end; /边的终点 int weight; /边的权值;class Graph1 /邻接矩阵图类 private: int visitedMaxSize; /访问标记数组 void unvisited(); /设置未访问标记 void depthfs(int k); /从结点k开始的深度优先遍历 void breadthfs(int k); /从结点k开始的广度优先遍历 public: char vertexMaxSize; /图的结点集，MaxSize为最大结点数 int matMaxSizeMaxSize; /图的邻接矩阵 int vertCount; /图的结点数 int edgeCount; /图的边数 Graph1(); /初始化图的结点集和邻接矩阵 Graph1() /析构函数为空 void createGraph(int n,char vert,int m,EdgeNode1 edge); friend ostream& operator(ostream& out,Graph1 &g1); void depthFirstSearch(); /图的深度优先遍历 void breadthFirstSearch(); /图的广度优先遍历 void insertVertex(char vert); /插入结点 void insertEdge(EdgeNode1 e); /插入边 void insertEdge(int init,int end,int w); void removeVertex(char vert); /删除结点 void removeEdge(EdgeNode1 e); /删除边 void removeEdge(int init,int end); /删除边;Graph1:Graph1() /初始化图的结点集和邻接矩阵 int i,j; for(i=0;iMaxSize;i+) /初始化图的结点集 vertexi= ; for(i=0;iMaxSize;i+) /初始化图的邻接矩阵 for(j=0;jMaxSize;j+) if(i=j) matij=0; /数据元素权值为0 else matij=MaxWeight; /权值为无穷大 vertCount=0; /当前结点数为0 edgeCount=0; /当前边数为0void Graph1:createGraph(int n,char vert,int m,EdgeNode1 edge) /以结点集和边集构造一个图 vertCount=n; /图的结点个数 int i,j,k; for(i=0;in;i+) /初始结点加入结点集 vertexi=verti; edgeCount=m; /图的边数 for(k=0;km;k+) /初始边值加入邻接矩阵 i=edgek.init; /边的起点 j=edgek.end; /边的终点 matij=edgek.weight; /边的权值 ostream& operator(ostream& out,Graph1 &g1) /输出图的结点集和邻接矩阵 void Graph1:unvisited() /设置未访问标记 for(int i=0;ivertCount;i+) visitedi=0;void Graph1:depthfs(int k) /从结点k开始的深度优先遍历void Graph1:depthFirstSearch() /图的深度优先遍历 cout深度优先遍历Depth first search:endl; for(int k=0;kvertCount;k+) /k为结点下标 unvisited(); /设置未访问标记 depthfs(k); coutendl; void Graph1:breadthfs(int k) /从结点k开始的广度优先遍历 /k为起始结点下标 Queue1 q1(vertCount); /设置空队列 int i=k; coutvertexi ; /访问起始结点 visitedi=1; /设置访问标记 q1.enQueue(i); /访问过的结点k入队 while(!q1.isEmpty() /队列不空时 i=q1.deQueue(); /出队,i是结点k的数组下标 int j=0; while(j0 & matijMaxWeight & visitedj=0) coutvertexj ; /访问结点 visitedj=1; q1.enQueue(j); /入队 else j+; void Graph1:breadthFirstSearch() /图的广度优先遍历 /k为起始结点下标 cout广度优先遍历Breadth first search:endl; for(int k=0;kvertCount;k+) unvisited(); breadthfs(k); coutendl; const int MaxSize=10; /定义最大结点数const int MaxWeight=9999; /定义权值为无穷大void main() char vert=ABCDE; EdgeNode1 edge1= 0,1,1,0,3,1, /无向图G6的边集1,0,1,1,2,1,1,3,1,2,1,1,2,4,1,3,0,1,3,1,1,4,2,1 ; Graph1 g1,g2; g1.createGraph(5,vert,10,edge1); coutg1; g1.depthFirstSearch(); /图的深度优先遍历 g1.breadthFirstSearch(); /图的广度优先遍历 coutendl; EdgeNode1 edge2= 0,1,1, /有向图G7的边集 1,2,1,1,3,1,2,4,1,3,0,1 ; g2.createGraph(5,vert,5,edge2); coutg2; g2.depthFirst