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

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

求无向连通图的生成树一、实验目的⑴掌握图的逻辑结构⑵掌握图的邻接矩阵存储结构⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容（1）建立无向图的邻接矩阵存储（2）对建立的无向图，进行深度优先遍历（3）对建立的无向图进行广度优先遍历三、设计与编码（1）本实验用到的理论知识（2）算法设计（3）编码//图抽象类型及其实现.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"Graph.h"#include"iostream.h"intGraph::Find(intkey,int&k){intflag=0;for(inti=0;ikey=front;q->Weight=E[i].weight;q->next=A[rear].first;A[rear].first=q;A[rear].data.OutDegree++;A[front].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<<"连通分量="<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=="<2)cout<<"---连通分量"<2)cout<<"---连通分量"<next=0;f=r=p;//生成空队列for(i=0;ikey=A[i].data.key;p->next=0;f->next=p;r=p;while(f->next)//当队非空时{//出队一顶点q=f->next;if(Type>2)cout<<"连通分量"<key<next=q->next;if(q==r)r=f;//与q连接的未访问的顶点入队pe=A[q->key].first;while(pe){if(A[pe->key].tag==0) {//入队if(!(p=newqueue))return(-1);A[pe->key].tag=comp;p->key=pe->key;p->next=0;if(f==r)f->next=p;r->next=p;r=p;};pe=pe->next;};//endof(pe)deleteq;};//endof(f->next)comp++;};//enfofif};//释放队列while(f){p=f->next;deletef;f=p;};returncomp-1;//返回连通分量数};/*intGraph::TopoSort(int*que,int&num){//que顺序队列保存了拓扑排序的结果，f和r为que的头尾指示；loop用于判有无环inti,f=0,r=0,index,loop=1;Enode*pe;num=0;for(i=0;inext) {A[pe->key].tag--;if(A[pe->key].tag==0){que[r++]=pe->key;A[pe->key].tag=-1;};};};num=r;if(r2)cout<<"连通分量数="<2)cout<<"连通分量数="<20已排序顶点数目=2Pressanykeytocontinue五、总结与心得