求无向连通图的生成树教学教材.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;i if(vertexnum<1)return(-1);//参数vertexnum非法
int i,front,rear,k;
Enode *q;
//先生成不带边表的顶点表--即顶点为孤立顶点集
A=new Vnode[vertexnum];
if(!A)return(0);//堆耗尽
for(i=0;irtexLen=vertexnum;
//在生成边表
if(edgenum<0)return(1);//无边的图
for(i=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=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(Type>2)cout<<"连通分量="<gain....\n";
if(!(Find(v0,k))){cout<<"find=="<2)cout<<"---连通分量"<2)cout<<"---连通分量"<nentnum);componentnum++;
};
};
return(componentnum-1);

};
int Graph::Bfs()
{
int i,comp=1; //comp=连通分量的标记，、、...
struct queue{int key;queue * next;};
Enode *pe;
queue *f,*r,*q,*p=new queue;
if(!p)return(-1); //堆耗尽
p->next=0;f=r=p; //生成空队列
for(i=0;i)A[i].tag=0;//初始化已访问标志
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<<"连通分量"<p<<'\t';
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=new queue))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;
};//end of (pe)
delete q;
};//end of (f->next)
comp++;
};//enf of if
};
//释放队列
while(f){p=f->next;delete f;f=p;};
return comp-1; //返回连通分量数
};
/*
int Graph::TopoSort(int *que,int &num)
{ //que顺序队列保存了拓扑排序的结果，f和r为que的头尾指示；loop用于判有无环
int i,f=0,r=0,index,loop=1;
Enode *pe;
num=0;
for(i=0;i for(pe=A[index].first;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(rEdge b[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].weight1;
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}};
g1.CreateGraph(num,b,6);

if(g1.GetType()>2)cout<<"连通分量数="<2)cout<<"连通分量数="<
2 0 已排序顶点数目=2
Press any key to continue
五、总结与心得
仅供学习与交流，如有侵权请联系网站删除 谢谢8