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

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

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

2、d(intkey,int&k){intforflag=0;(inti=0;i

3、生成不带边表的顶点表--即顶点为孤立顶点集A=newVnode[vertexnum];if(!A)return(0);//堆耗尽for(i=0;i

4、il;if(!Find(rear,k)

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[front]、data、InDegree++;if(Type>2){q=newEnode;if(!q)return(0);q->key=rear;q->next=A[front]、first;A[front]、f

7、irst=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)//从指定顶点深

8、度遍历{inti,k,componentnum=1;//if(Type<3)return(-1);////cout<<"begain、、、、if(!(Find(v0,k))){cout<<不考虑由向图";"find=="<2)cout<<"---连通分量"<2)c

9、out<<"---连通分量"<next=0;f=r