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

求无向连通图的生成树

求无向连通图的生成树

一、实验目的

=1\*GB2⑴掌握图的逻辑结构

=2\*GB2⑵掌握图的邻接矩阵存储结构

=3\*GB2⑶验证图的邻接矩阵存储及其遍历操作的实现

二、实验内容

（1）建立无向图的邻接矩阵存储

（2）对建立的无向图，进行深度优先遍历

（3）对建立的无向图进行广度优先遍历

三、设计与编码

（1）本实验用到的理论知识

（2）算法设计

（3）编码

//图抽象类型及其实现.cpp:Definestheentrypointfortheconsoleapplication.

//

#includestdafx.h

#includeGraph.h

#includeiostream.h

intGraph::Find(intkey,intk)

{

intflag=0;

for(inti=0;iVertexLen;i++)

if(A[i].data.key==key){k=i;flag=1;break;};

returnflag;

};

intGraph::CreateGraph(intvertexnum,Edge*E,intedgenum)

{ //由边的集合E(E[0]~E[VertexNum-1])，生成该图的邻接表表示

if(vertexnum1)return(-1);//参数vertexnum非法

inti,front,rear,k;

Enode*q;

//先生成不带边表的顶点表--即顶点为孤立顶点集

A=newVnode[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=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(Type2)

{

q=newEnode;

if(!q)return(0);

q-key=rear;

q-next=A[front].first;

A[pe-key].tag--;

if(A[pe-key].tag==0){que[r++]=pe-key;A[pe-key].tag=-1;};

};

};

num=r;

if(rVertexLen)return(0);//存在环

return1;

};

intmain(intargc,char*argv[])

{Graphg1(1);

intnum=5,temp=1;

int*stack=newint[5];

Edgeb[12];

b[0].Head=1;b[0].Tail=0;b[0].weight=1;

b[1].Head=3;b[1].Tail=1;b[1].weight=1;

b[2].Head=0;b[2].Tail=2;b[2].weight=1;

b[3].Head=1;b[3].Tail=4;b[3].weight=1;

b[4].Head=4;b[4].Tail=2;b[4].weight=1;

b[5].Head=4;b[5].Tail=3;b[5].weight=1;

//

b[6].Head=0;b[6].Tail=1;b[6].weight=1;

b[7].Head=1;b[7].Tail=3;b[7].weight=1;

b[8].Head=2;b[8].Tail=0;b[8].weight=1;

b[9].Head=4;b[9].Tail=1;b[9].weight=1;

b[10].Head=2;b[10].Tail=4;b[10].weight=1;