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

求无向连通图的生成树 一、实验目的 ⑴掌握图的逻辑结构 ⑵掌握图的邻接矩阵存储结构 ⑶验证图的邻接矩阵存储及其遍历操作的实现 二、实验内容 （1）建立无向图的邻接矩阵存储 （2）对建立的无向图，进行深度优先遍历 （3）对建立的无向图进行广度优先遍历 三、设计与编码 （1）本实验用到的理论知识 （2）算法设计 （3）编码 // 图抽象类型及其实现.cpp : Defines the entry point for the console application. // #include stdafx.h #include Graph.h #include iostream.h int Graph::Find(int key,int k) { int flag=0; for(int i=0;iVertexLen;i++) if(A[i].data.key==key){k=i;flag=1;break;}; return flag; }; int Graph::CreateGraph(int vertexnum,Edge *E,int edgenum) { //由边的集合E(E[0]~E[VertexNum-1])，生成该图的邻接表表示 if(vertexnum1)return(-1);//参数vertexnum非法 int i,front,rear,k; Enode *q; //先生成不带边表的顶点表--即顶点为孤立顶点集 A=new Vnode[vertexnum]; if(!A)return(0);//堆耗尽 for(i=0;ivertexnum;i++) { A[i].data.key=i; A[i].tag=0; A[i].data.InDegree=A[i].data.OutDegree=A[i].tag=0; A[i].first=0; }; VertexLen=vertexnum; //在生成边表 if(edgenum0)return(1);//无边的图 for(i=0;iedgenum;i++) { front=E[i].Head;rear=E[i].Tail; if(!Find(rear,k) || !Find(front,k))return(-2);//参数E非法 q=new Enode; 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(Type2) { q=new Enode; if(!q)return(0); q-key=rear; q-next=A[front].first; A[front].first=q; q-Weight=E[i].weight; }; }; return(1); }; void Graph::Dfs(int key,int flag) { //static run=1; Enode *w; A[key].tag=flag; if(Type2)cout连通分量=flag\t; cout顶点键值=keyendl; for(w=A[key].first;w ;w=w-next) if(!A[w-key].tag)Dfs(w-key,flag); }; int Graph::DfsDravers(int v0) //从指定顶点深度遍历 { int i,k,componentnum=1; //if(Type3)return(-1);//不考虑由向图 //coutbegain....\n; if(!(Find(v0,k))){coutfind==kendl;return(0);};//初始结点v0不存在 if(Type2)cout---连通分量componentnum---endl; Dfs(k,componentnum); componentnum++; for(i=0;iVertexLen;i++) { if(!A[i].tag){ if(Type2)cout---连通分量componentnum---endl; Dfs(i,componentnum);componentnum++; }; }; return(componentnum-1); }; int Graph::Bfs() { int i,comp=1;