图的遍历与最小生成树的实现.doc

图的遍历与最小生成树的实现

———————————————————————————————— 作者：
———————————————————————————————— 日期：

42

个人收集整理 勿做商业用途

数学与计算机学院
课程设计说明书

课 程 名 称:数据结构与算法课程设计
课 程 代 码:
题 目：图的遍历和最小生成树
年级/专业/班: 2011级软工一班
学 生 姓 名:
学　　 号:
开 始 时 间: 2012 年 12 月 24 日
完 成 时 间： 2012 年 1 月 3 日
课程设计成绩：
学习态度及平时成绩（30）
技术水平与实际能力（20)
创新（5)
说明书（计算书、图纸、分析报告）撰写质量（45)
总 分（100）

指导教师签名： 年 月 日

目 录 （小三黑体，居中）

引言……………………………………………………………………………1
1 需求分析……………………………………………………………………
2 概要设计……………………………………………………………………
3详细设计……………………………………………………………………
4调试分析……………………………………………………………………
5用户使用说明………………………………………………………………
6测试结果……………………………………………………………………
7结论………………………………………………………………………
致谢……………………………………………………………………………
参考文献………………………………………………………………………
（目录左对齐，所有的均为1。5倍行距，未具体指明使用字体的均为小四宋体，以下同）

(目录中最多放二级标题。注意看页面的规范要求。尤其注意页眉。页眉从目录开始）

摘 要
图是一种比线形表和树更为复杂的数据结构.在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关.本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。

关键词:图;存储结构；遍历

引 言
数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合.利用数据结构能解决许多实际问题，在各个方面都有非常不错的成就.
通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固《数据结构》课程学习的内容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关；为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创意识和创新能力，使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础.同时，可以利用这次机会来检验自己的c++数据结构水平,提高自己的写作水平,锻炼自己的动手能力。
而此次课程设计的任务和意义在于：增强自己的动手能力，利用VC++6.0等专业软件编程实现图各种遍历的算法，以及最小生成树算法，增强自己的调试程序和测试程序的能力.
1 需求分析
1。1任务与分析
1. 由键盘向程序输入相关数据;
2. 程序处理输入数据,以十字链表，邻接矩阵和邻接链表的形式输出；
3. 根据已建成的图，程序实现图的深度优先遍历，广度优先遍历；
4. 显示图的最小生成树，连同分量的实现；
5. 采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储.
1.2测试数据
1. 邻接矩阵测试数据:6 6 a b c d e f a b 2 a e 6 a d 5 b d 4 b c 1 b f 3
2. 邻接链表测试数据:7 8 a b c d e f g a b a e a c a f b g b d d g c f
3. 十字链表测试数据：4 5 3 2 2 5 4 3 99 3 4 66

2 概要设计
2.1 ADT描述
ADT Graph ｛
数据对象：V{具有相同特征的数据元素，即V顶点集｝
数据关系：E＝｛VR｝
VR=｛〈v，w〉｜v,w∈V，〈v。w〉表示顶点v和顶点w之间的边；}
基本操作:初始化空图；
输入建立图;
广度优先遍历；
深度优先遍历;
最小生成树；
｝ADT Graph
2.2程序模块结构
根据本系统对功能实现的要求，主要可以分为一下三个大的模块：
1. 邻接矩阵存储结构；
2. 邻接链表存储结构；
3. 十字链表存储结构；
其中每个模块又包涵其它相应的子功能模块.
则根据以上可以得到本系统的概要设计图
图的遍历与最小生成树

退出系统
十字链表存储结构
邻接链表存储结构
邻接矩阵存储结构

2.3　各功能模块（四号黑体）
2。3.1在邻接矩阵(AdjMWGraph）类中
void kruscal_arc（)； //克鲁斯卡尔算法
AdjMWGraph（）； //构造函数
void CreatG(int n,int e); //建立一个图的邻接矩阵
void DepthF(）； //连通分量的实现
void BoradF()； //连通分量的实现
void PrintOut()； //输出图的信息
void Prim （）; //普里姆算法
void kruscal_arc（)； //克鲁斯卡算法
void DepthM（）； //深度非递归优先遍历
void Borad（int v,int visited［])； //广度非递归优先遍历
void Depth（int v,int visited［]）; //深度递归优先遍历
2.3.2在邻接链表（ AdjTWGraph）类中
void Prim （); //普里姆算法
void CreatG(int n，int e）; //建立一个图的邻接表
void kruscal_arc（）； //克鲁斯卡算法
void DepthF(） //连通分量的实现
void BoradF(） //连通分量的实现
void PrintOut（）； //输出图的信息
void Borad(int v,int visited[］）; //广度非递归优先遍历
void Depth（int v,int visited[])； //深度非递归优先遍历
void DepthM（int v,int visited［]);//深度递归优先遍历
2.3.3在十字链表（ Linkedmat ）类中
void Creat（）； //创建一个十字链表
void Show（）； //输出显示十字链表
void zh（)； //十字链表转换为邻接矩阵
void Depth(int v，int visited［]）;//深度递归优先遍历
void Borad(int v,int visited［]）；//广度非递归优先遍历
void DepthF（）； //连通分量的实现
void BoradF（); //连通分量的实现
void Prim （)； //普里姆算法
void kruscal_arc（)； //克鲁斯卡尔算法

3　详细设计
3。1结构体定义
struct Node
{
int row;
int col；
Node *down;
Node *right；
union
{
Node＊next；
ElemType val;
｝；
};
struct Edge｛
int dest;
ElemType weight；
Edge ＊next；
｝；
struct item
｛
ElemType data;
Edge *adj；
};
struct MinSpanTree
{ ElemType begin，end;
ElemType length；
｝;

3。2 初始化（四号黑体)
3.2。1邻接矩阵的初始化
AdjMWGraph()
{ for （ int i=0； i〈MaxVertices; i++ ）
for （ int j=0; j〈MaxVertices; j++ )
｛
if( i==j ） Edge[i］[j］=0；
else Edge［i][j］=MaxWeight；
}
numE=0;
numV=0；
｝
3.2.2邻接链表的初始化
AdjTWGraph：：AdjTWGraph（）
{
for(int i=0；i〈MaxVertices;i++）
{
Vertices［i］.data=0；
Vertices［i].adj=NULL；
}
numV=0;
numE=0；
}
3。2。3十字链表的初始化
LinkeDmat()
｛
*hm=null;
}
3。3 图的创建（四号黑体）
3。3.1创建图的邻接矩阵
void AdjMWGraph：:CreatG(int n，int e）
{
int vi,vj,w，i;
numE=e； numV=n;
cout〈〈”\n 输入顶点的信息（整型）：” ;
for （i=0； i<numV； i++ ）
{
cout<<”\n ”〈〈i+1<<”: "；
cin〉>Vertices［i］；
｝
for （i=0； i<numE; i++ ）
{
cout<〈”\n 输入边的信息（vi，vj，W）：”;
cin〉>vi>>vj〉>w;
Edge［vi—1］[vj-1］=w；
}
｝
3.3.2创建图的邻接链表
void AdjTWGraph：:CreatG(int n，int e）
｛
int vi,vj;
DistT w;
numE=e；
numV=n；
cout<<"\n输入顶点信息:"〈〈endl；
for(int i=0;i<numV；i++)
｛
cout<〈”\n"〈<i+1<<"：”；
cin>〉Vertices［i］。data;
｝
for（int j=0；j<numE;j++)
｛
cout〈〈”\n 输入边的信息（顶点号vi 顶点号vj 边的权值 w）："；
cin>>vi〉>vj>>w；
if（vi〈1｜|vi>numV||vj<1｜|vj〉numV) cout〈〈"\n v1或v2越界出错！"〈〈endl；
Edge *q=new Edge;
q-〉dest=vj-1；
q—〉weight=w;
q->next=NULL；
if（Vertices[vi-1］.adj==NULL）Vertices[vi—1］.adj=q;
else{
Edge ＊curr=Vertices[vi—1］.adj,＊pre=NULL;
while（curr！=NULL＆＆curr->dest<vj-1)
{
pre=curr;
curr=curr—〉next;
｝
if（pre==NULL）
{
q-〉next=Vertices［vi-1].adj;
Vertices［vi—1］.adj=q；
｝
else
{
q->next=pre->next;
pre—〉next=q；
}
}
Edge *p=new Edge；
p->dest=vi—1;
p->weight=w;
p->next=NULL;
if（Vertices[vj—1]。adj==NULL）Vertices[vj—1].adj=p;
else｛
Edge *curr=Vertices[vj—1］.adj,*pre=NULL；
while(curr！=NULL＆&curr—>dest〈vi—1）
{
pre=curr；
curr=curr—〉next;
｝
if(pre==NULL）
｛
p-〉next=Vertices[vj-1］。adj；
Vertices[vj—1］。adj=p；
｝
else
{
p—〉next=pre-〉next;
pre-〉next=p;
｝
}
｝
｝
3.3.3创建图的十字链表
void Linkedmat:：Creat()
｛
int m,n,r,c,v，s；
Node ＊p，＊q，*h［10]；
cout<〈"请输入您要创建的矩阵维数—〉”〈<endl<<endl；
cout〈<”行数："；
cin〉>m；
cout<〈"列数：”；
cin>>n；
s=m〉n？m:n;
if（m>n) k=n；
else k=m;
p=new Node;
p->row=m;p-〉col=n;
hm=p；
h［0］=p；
for（int i=1;i<=s；i++）
{
p=new Node;
p—>row=0;p—〉col=0；
h［i］=p；
p—>right=p;
p—>down=p;
h［i—1］—〉next=p;
｝
h［s]—>next=hm；
cout<〈endl〈〈”注意："<<endl；
cout〈<”最大行坐标:”<<m<〈endl；
cout〈〈"最大列坐标:"〈〈n〈<endl;
cout〈〈”三元组最多个数："<<m*n<<endl;
cout〈<”若输入不在此范围内的数据将丢失!"〈〈endl;
int t;
cout<<”输入非零元素的个数t=?”;cin〉>t；
cout〈〈”请输入三元组的格式(以空格分开)：r c v（回车）"<〈endl〈<endl；
for（int j=0;j<t；j++)
｛
cout<〈"输入三元组：”；
cin>>r〉〉c>〉v;
p=new Node；
p—>row=r；
p-〉col=c;
p-〉val=v；
q=h［r］；
while((q—>right!=h[r］）＆＆(q—>right->col〈c))q=q-〉right；
p->right=q—〉right;
q-〉right=p；
q=h[c];
while(（q-〉down!=h［c］）＆&（q->down—〉row〈r））q=q-〉down；
p—〉down=q-〉down；q—>down=p;
｝
}
3。4 图的广度优先遍历（四号黑体）
3。4。1图的邻接矩阵的广度优先遍历
void AdjMWGraph::Borad(int v，int visited[])
{
SqQueue〈int>q;
cout<<endl<〈”\n顶点”〈<v+1<<"权值”<〈Vertices[v］；
visited[v］=1;
q.EnQueue(v）；
while(!q.IsEmpty（)）
{
v=q.DeQueue(）；
for(int col=0;col<numV;col++)
if(Edge［v]［col］〉0&&Edge［v］[col]〈MaxWeight&＆visited［col]==0)
{
cout〈<endl<<"\n顶点”〈<col+1〈〈"权值"〈<Vertices［col］；
visited[col］=1;
q。EnQueue（col)；
}
｝
｝
3。4。2图的邻接链表的广度优先遍历
void AdjTWGraph：:Borad（int v,int visited［］)
{
int vj；
Edge ＊p；
SqQueue〈int>Q;
cout<<"\n顶点”〈<v+1<〈”权值”〈〈Vertices［v].data；
visited［v］=1；
Q.EnQueue(v)；
while(!Q。IsEmpty（）)
{
v=Q。DeQueue（）;
p=Vertices［v］。adj；
while(p!=NULL）
｛
vj=p-〉dest；
if（visited[vj]==0）
{
cout<<"\n顶点"<<vj+1〈<"权值"〈〈Vertices［vj].data；
visited[vj]=1；
Q.EnQueue（vj）；
｝
p=p->next；
｝
｝
cout〈<endl；
｝
3.5 图的深度优先遍历（四号黑体)
3.5。1图的邻接矩阵的深度递归优先遍历
void AdjMWGraph:：Depth(int v,int visited［])
{
cout<〈”\n 顶点"<〈v+1〈〈”权值"<〈Vertices[v］；
visited[v]=1;
for(int col=0；col<numV；col++)
｛
if（Edge［v］［col］==0｜|Edge［v]［col］==MaxWeight)continue；
if(！visited[col]）Depth（col,visited);
｝
｝
3。5。2图的邻接矩阵的深度非递归优先遍历
void AdjMWGraph:：DepthM（）
｛
int i，j，k，m;
cout〈<”\n 顶点”<<1〈〈"权值"〈〈Vertices[0］<<endl；
for（m=0；m<numV;m++)
{
i=0；
for（j=0；；）
｛
j=j％numV;
if（Edge[i］[j]！=0)
｛
Edge［i］[j]=0;
Edge［j］［i］=0;
if(Edge［j］[j］==0）
｛
for（k=0;k<numV;k++)
{
if（Edge[j][k]==0）
continue；
else
break;
｝
if(k==numV）
break;
else
cout〈<”\n顶点”<〈j+1<<”权值”<<Vertices[j]<<endl;
｝
i=j;
j++；
}
if(Edge[i]［j］==0)
{
for(k=0；k〈numV；k++）
{
if（Edge[i］［k］==0）
continue；
else
break；
}
if（k==numV)
break;
else
j++；
}
}
｝
｝
3.5.3图的邻接链表的深度递归优先遍历
void AdjTWGraph：:DepthM（int v,int visited[])
{int vj；
Edge ＊p；
cout<<"\n顶点"〈<v+1〈〈”权值"〈<Vertices［v]。data；
visited[v］=1;
p=Vertices[v］。adj;
while（p!=NULL)
{
vj=p-〉dest;
if(visited［vj]==0) DepthM(vj，visited);
p=p->next；
｝
｝
3。5。4图的邻接链表的深度非递归优先遍历
void AdjTWGraph：:Depth(int v，int visited［]）
{
int vj；
Edge ＊p;
SqQueue 〈int〉 Q;
Q.EnQueue（v）;
while(!Q.IsEmpty())
｛
v=Q.DeQueue()；
cout<<"\n顶点"<〈v+1<<"权值"〈<Vertices[v].data；
visited[v］=1;
p=Vertices［v］。adj;
while(p！=NULL） ｛
vj=p->dest；
if（visited[vj］==0） Q。EnQueue(vj)；
p=p—>next;
}
}
}
3.6 最小生成树的实现(四号黑体)
3.6.1普利姆算法
void AdjMWGraph::Prim （)
{
int n=numV，m,v，j，d；
MinSpanTree e， mintree[MaxVertices];
for （j=1; j<n; j++）
｛
mintree［j—1].begin=1；
mintree［j-1].end=j+1;
mintree[j—1］。length=Edge［0]［j］；
}
for (int k=0; k〈n-1; k++)
{
int min=MaxWeight；
for （j=k； j〈n-1; j++)
if (mintree[j］。length〈min ) ｛min=mintree［j］。length; m=j;｝
e=mintree［m]； mintree［m]=mintree[k]; mintree［k]=e;
v=mintree[k].end;
for （j=k+1； j<n-1; j++）
tree［n—1]
{
d=Edge［v-1][mintree[j]。end-1];
if （d〈mintree[j］。length)
{
mintree［j]。length=d;
mintree［j]。begin=v;
}
}
｝
for （j=0;j<n-1； j++)
cout<〈"起点："〈<mintree[j]。begin〈〈” 终点:"〈<
mintree[j］.end〈〈” 权值：”〈<mintree［j］.length〈<"\n”;
｝
3。6。2克鲁斯卡尔算法
void AdjMWGraph:：kruscal_arc（)
｛

MinSpanTree mintree［20]；
int i，j,k=0；
for(i=0；i<numV;i++)
for（j=i；j<numV；j++）
{
if(Edge［i][j］！=10000)
｛
mintree[k］。begin=i；
mintree[k]。end=j；
mintree［k].length=Edge［i］[j]；
k++；
}
｝
int x,y，m，n;
int buf，edf;
for（i=0；i<numV；i++)
acrvisited[i]=0；
for（j=0;j<numV;j++）
｛
m=10000；
for(i=0；i〈numV；i++）
{
if（mintree［i]。length〈m）
{
m=mintree[i].length；
x=mintree［i］.begin;
y=mintree[i］.end;
n=i；
}

}
buf=find（acrvisited，x);
edf=find（acrvisited，y)；
mintree［n］。length=10000;
if（buf！=edf）
{
acrvisited［buf]=edf；
cout<<"（”<<x+1<〈”,”<<y+1<<")"〈〈m;
cout〈〈endl；
}
｝
}
3.7 图的连通分量的实现（四号黑体）
void DepthF（）
{
int visit［MaxVertices］;
for(int j=0；j<MaxVertices；j++）visit[j]=0；
for（int i=0;i〈numV；i++）
if(visit［i]==0）｛
Depth（i，visit)；
cout<<endl<<endl;
}
}
3。8 输出图的信息（四号黑体）
3。8。1输出图的邻接矩阵的信息
void AdjMWGraph:：PrintOut（）
{
int i；
cout<<”\n 输出顶点的信息（整型）：\n”；
for ( i=0； i<numV； i++ )cout<<Vertices[i]〈〈" ”;
cout<<”\n 输出邻接矩阵 ：” ；
for (i=0； i<numV； i++ ）
{
cout〈<”\n "<<i+1<〈”: ";
for （ int j=0； j<numV ;j++ )
cout〈<setw（6）〈〈Edge[i］[j]〈<” ";
cout<〈endl；
}
｝
3。8。2输出图的邻接链表的信息
void AdjTWGraph:：PrintOut（)
{
Edge ＊curr;
for(int i=0;i〈numV;i++）
｛
cout〈<”\n输出顶点编号信息，它的邻接点编号和边的权值：";
cout<〈" "〈<i+1<<" ”〈〈Vertices［i].data;
curr=Vertices[i].adj;
while（curr！=NULL）{
cout<〈” ”〈〈curr->dest<<" "<〈curr—〉weight;
curr=curr—>next；
｝
cout〈<endl；
}
｝
3。8.3输出图的十字链表的信息
void Linkedmat：:Show()
｛
Node ＊p,*q；
cout〈〈endl<〈"以此十字链表存储的矩阵为：”<〈endl<<endl；
int m，n;
m=hm->row；
n=hm—>col；
q=p=hm-〉next；
p=p—〉right；
cout〈<endl<〈endl;
cout<<”\n\n\t\t";
for（int i=1;i<=m；i++)
{
for(int j=1；j〈=n；j++）
｛
if（(p->row==i)&＆（p—>col==j））
{
cout〈<setw(8)<<p-〉val;
p=p—>right;
}
else cout〈<setw（8)<<’0';
}
cout<〈”\n\n\t\t”;
p=q；
q=p=p-〉next;
p=p—〉right;
}
｝
3。9系统的层次图

图的遍历与最小生成树

十字链表
存储结构
邻接链表
存储结构
邻接矩阵
存储结构

十字链表建图
输出信息
最小生成树
最小生成树
广度优先遍历
深度优先遍历
输出信息
最小生成树
广度优先遍历
深度优先遍历
邻接链表建图
输出信息
广度优先遍历
深度优先遍历
邻接矩阵建图

4 调试分析（小三黑体）

5　用户使用说明（小三黑体）
本系统是关于图的操作，可根据界面提示进行操作。

6　测试结果（小三黑体）
登录系统主界面,如下图：

图6。1 系统主菜单
选择功能1，进入第二菜单界面：

图 6.2 邻接矩阵存储结构
选择1，建立矩阵图：

图 6.3 邻接矩阵创建图
邻接矩阵显示：

图 5.4 矩阵显示图
返回第二菜单,选择2，深度递归优先遍历:

图 6。5 深度递归优先遍历
选择3，广度非递归优先遍历：

图6。6 广度非递归优先遍历
选择4，最小生成树PRIM算法：

图6。7 最小生成树PRIM算法
选择5，最小生成树KRUSCAL算法

图6。8 最小生成树KRUSCAL算法
选择6，深度非递归优先遍历

图6。8 深度非递归优先遍历
返回主菜单,选择2,邻接链表存储结构的实现：

图 6。9 邻接链表功能
选择功能1，如下：

图 6.10 图信息录入
选择2，深度非递归优先遍历

图 6。11 深度非递归优先遍历结果
选择3，广度非递归优先遍历

图 6.12 广度非递归优先遍历结果
选择4，广度优先遍历

图 6。13 广度递归优先遍历结果
返回主菜单，选择功能3:

图 6。14 十字链表
选择1建立十字链表

图 6.15信息录入
选择2，显示矩阵

图 6.16 显示十字链表

结 论 （小三黑体，单独占页，居中）
通过一个学期对数据结构的系统学习和本次课程设计，加深了我对C++程序设计语言的认识，使得我对程序的开发过程有了更为深刻的理解。在实际编程过程中遇到过很多问题，迫使我去查阅各种资料,并且利用VC++6.0等软件开发工具以及一些建模工具解决了这些难题。通过这次的实验,我得出了一个结论,那就是任何一个成功软件的背后都包含着检查和测试的艰辛，很多问题只有在实际运行中才能被发现，只有更加踏实工作和仔细查验才能让程序更加完美.
以上便是我对《数据结构课程设计》这门课的总结,在接下来的时间里,我要更加勤恳的投入到C++编程语言的学习实践中去，在打牢基础的前提下更加深入的学习.

致 谢 (小三黑体,单独占页，居中)
在本次课程设计过程中，首先感谢陈红红老师对我的细心辅导和帮助。感谢学校给我们这次机会让我们独自解决一系列问题，感谢唐建梅老师数据结构课堂上的仔细讲解，在陈老师的指