求无向连通图的生成树
一、实验目的
⑴掌握图的逻辑结构
⑵掌握图的邻接矩阵存储结构
⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容
（1）建立无向图的邻接矩阵存储
（2）对建立的无向图，进行深度优先遍历（3）对建立的无向图进行广度优先遍历
三、设计与编码
（1）本实验用到的理论知识
（2）算法设计
（3）编码
pp : Defines the entry point for the console application.
=key){k=i;flag=1;break;};
return flag;
};
int Graph::CreateGraph(int vertexnum,Edge *E,int edgenum) { i;
A[i].tag=0;
A[i].=A[i].=A[i].tag=0;
A[i].first=0;
};
VertexLen=vertexnum;
ead;rear=E[i].Tail;
if(!Find(rear,k) || !Find(front,k))return(-2);eight;
q->next=A[rear].first;
A[rear].first=q;
A[rear].++;
A[front].++;
if(Type>2)
{
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)
{
ag=flag;
if(Type>2)cout<<"连通分量="< cout<<"顶点键值="< for(w=A[key].first;w ;w=w->next) if(!A[w->key].tag)Dfs(w->key,flag); }; int Graph::DfsDravers(int v0) ..\n"; if(!(Find(v0,k))){cout<<"find=="< if(Type>2)cout<<"---连通分量"< Dfs(i,componentnum);componentnum++; }; }; return(componentnum-1); }; int Graph::Bfs() { int i,comp=1; . struct queue{int key;queue * next;}; Enode *pe; queue *f,*r,*q,*p=new queue; if(!p)return(-1); ag=0;ag==0) { A[i].tag=comp; p->next=0; f->next=p;r=p; while(f->next)irst; while(pe) { if(A[pe->key].tag==0) {ag=comp; p->key=pe->key; p->next=0; if(f==r)f->next=p; r->next=p;r=p; }; pe=pe->next; };ag=A[i].; ag==0){que[r++]=i;A[i].tag=-1;loop=0;}; if(loop)return(0); while(f {irst;pe;pe=pe->next) { A[pe->key].tag--; if(A[pe->key].tag==0){que[r++]=pe->key;A[pe->key].tag=-1;}; }; }; num=r; if(r 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; ead=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; b[11].Head=3;b[11].Tail=2;b[11].weight=1; //b=={{1,0,1},{3,1,1},{0,2,1},(1,4,1},{4,2,1},{2,3,1}}; (num,b,6); if()>2)cout<<"连通分量数="<<(2)< cout<<"--------------"< if()>2)cout<<"连通分量数="<<()< if()<3) { if(stack,temp))cout<<"拓扑排序成功！\n"; else cout<<"该图有环！\n"; cout<<"部分或全部的拓扑序列为：(顶点总数="<<()<<")\n"; for(int i=0;i }; delete[5]stack; //printf("Hello World!\n"); return 0; } 四、运行与调试 运行结果为： 该图有环！ 部分或全部拓扑序列为：<顶点总数=5> 2 0 已排序顶点数目=2 Press any key to continue 五、总结与心得
相关主题
文本预览