求无向连通图的生成树教学教材.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<VertexLen;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(vertexnum<1)return(-1);//参数vertexnum非法
int i,front,rear,k;
Enode *q;
//先生成不带边表的顶点表--即顶点为孤立顶点集
A=new Vnode[vertexnum];
if(!A)return(0);//堆耗尽
for(i=0;i<vertexnum;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(edgenum<0)return(1);//无边的图
for(i=0;i<edgenum;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(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<<"连通分量="<<flag<<'\t';
cout<<"顶点键值="<<key<<endl;
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(Type<3)return(-1);//不考虑由向图
//cout<<"begain....\n";
if(!(Find(v0,k))){cout<<"find=="<<k<<endl;return(0);};//初始结点v0不存在
if(Type>2)cout<<"---连通分量"<<componentnum<<"---"<<endl;
Dfs(k,componentnum);
componentnum++;
for(i=0;i<VertexLen;i++)
{
if(!A[i].tag){
if(Type>2)cout<<"---连通分量"<<componentnum<<"---"<<endl;
Dfs(i,componentnum);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<VertexLen;i++)A[i].tag=0;//初始化已访问标志
for(i=0;i<VertexLen;i++)
{
if(A[i].tag==0)
{
A[i].tag=comp;
//入队该顶点的key
p=new queue;
if(!p)return(-1);
p->key=A[i].data.key;
p->next=0;
f->next=p;r=p;
while(f->next)//当队非空时
{//出队一顶点
q=f->next;
if(Type>2)cout<<"连通分量"<<comp<<'\t';
cout<<"顶点键值="<<q->key<<endl;
f->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<VertexLen;i++)A[i].tag=A[i].data.InDegree; //初始化入度到tag域
for(i=0;i<VertexLen;i++)if(A[i].tag==0){que[r++]=i;A[i].tag=-1;loop=0;};
if(loop)return(0);
while(f<r)
{//栈未处理完
index=que[f++];
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(r<VertexLen)return(0);//存在环
return 1;
};
int main(int argc, char* argv[])
{ Graph g1(1);
int num=5,temp=1;
int *stack=new int[5];
Edge 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].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}};
g1.CreateGraph(num,b,6);
if(g1.GetType()>2)cout<<"连通分量数="<<g1.DfsDravers(2)<<endl;
cout<<"--------------"<<endl;
if(g1.GetType()>2)cout<<"连通分量数="<<g1.Bfs()<<endl;
if(g1.GetType()<3)
{
if(g1.TopoSort(stack,temp))cout<<"拓扑排序成功！\n";
else cout<<"该图有环！\n";
cout<<"部分或全部的拓扑序列为：(顶点总数="<<g1.GetLen()<<")\n";
for(int i=0;i<temp;i++)cout<<stack[i]<<'\t';cout<<"已排序顶点数目="<<temp<<endl;
};
delete[5]stack;

//printf("Hello World!\n");
return 0;
}
四、运行与调试
运行结果为：
该图有环！
部分或全部拓扑序列为：<顶点总数=5>
2 0 已排序顶点数目=2
Press any key to continue
五、总结与心得
仅供学习与交流，如有侵权请联系网站删除 谢谢8