求无向连通图的生成树.doc

《求无向连通图的生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求无向连通图的生成树一、实验目的⑴掌握图的逻辑结构⑵掌握图的邻接矩阵存储结构⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容（1）建立无向图的邻接矩阵存储（2）对建立的无向图，进行深度优先遍历（3）对建立的无向图进行广度优先遍历三、设计与编码（1）本实验用到的理论知识（2）算法设计（3）编码//图抽象类型及其实现.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"Graph.h"#include"i

2、ostream.h"intGraph::Find(intkey,int&k){intflag=0;for(inti=0;i

3、ertexnum非法inti,front,rear,k;Enode*q;//先生成不带边表的顶点表--即顶点为孤立顶点集A=newVnode[vertexnum];if(!A)return(0);//堆耗尽for(i=0;i

4、m<0)return(1);//无边的图for(i=0;i

5、

6、!Find(front,k))return(-2);//参数E非法q=newEnode;if(!q)return(0);q->key=front;q->Weight=E[i].weight;q->next=A[rear].first;A[rear].first=q;A[rear].data.OutDegree++;A[fron

7、t].data.InDegree++;if(Type>2){q=newEnode;if(!q)return(0);q->key=rear;q->next=A[front].first;A[front].first=q;q->Weight=E[i].weight;};};return(1);};voidGraph::Dfs(intkey,int&flag){//staticrun=1;Enode*w;A[key].tag=flag;if(Type>2)cout<<"连通分量="<

8、t<<"顶点键值="<next)if(!A[w->key].tag)Dfs(w->key,flag);};intGraph::DfsDravers(intv0)//从指定顶点深度遍历{inti,k,componentnum=1;//if(Type<3)return(-1);//不考虑由向图//cout<<"begain....";if(!(Find(v0,k))){cout<<"find=="<

9、;};//初始结点v0不存在if(Type>2)cout<<"---连通分量"<2)cout<<"---连通分量"<

10、};intGraph::Bfs(){inti,comp=1;//comp=连通分量的标记，、、...structqueue{intkey;queue*next;};Enode*pe;queue*f,*r,*q,*p=newqueue;if(!p)return(-1);//堆耗尽p->next=0;f=r=p;//生成空队列for(i=0;i