数据结构课程设计之图的遍历和生成树求解.doc

##大学
数据结构课程设计报告

题目： 图的遍历和生成树求解

院（系）： 计算机工程学院
学生姓名:
班级： 学号:
起迄日期: 2023.6.20
指导教师:

2023—2023年度 第 2 学期

一、需求分析
1.问题描述：
图的遍历和生成树求解实现
图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素也许和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都也许相关。
生成树求解重要运用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。
2.基本功能
1) 先任意创建一个图；
2) 图的DFS,BFS的递归和非递归算法的实现
3) 最小生成树（两个算法）的实现，求连通分量的实现
4) 规定用邻接矩阵、邻接表等多种结构存储实现
3.输入输出
输入数据类型为整型和字符型，输出为整型和字符
二、 概要设计
1. 设计思绪：
a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表达，无边用0表达；有全图的边为权值表达，无边用∞表达。
b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。
c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有未被访问的，则另选未被访问的反复以上环节，是一个非递归过程。
d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此反复，直至所有的点都被访问，这是个递归的过程。
e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序运用的图的深度优先遍历算法。
2.数据结构设计：
ADT Queue{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
QueueEmpty(Q)
初始条件：Q为非空队列。
操作结果：若Q为空队列，则返回真，否则为假。
EnQueue(&Q,e)
初始条件：Q为非空队列。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q,e)
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。
}ADT Queue
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={<v,w>|v,w∈V且P（v，w）,<v,w>表达从v到w的弧，
谓词P（v,w）定义了弧<v,w>的意义或信息}
基本操作P：
CreatGraph(&G,V,VR);
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
BFSTraverse(G,visit());
初始条件：图G存在，Visit是定点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点
调用函数Visit一次且仅一次。一旦visit（）失
败，则操作失败。
DFSTraverse(G,visit());
初始条件：图G存在，Visit是定点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点
调用函数Visit一次且仅一次。一旦visit（）失
败，则操作失败。
DFStra_fen(G)
初始条件：图G存在，存在图的深度优先遍历算法。
操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。
}ADT Graph;
3. 软件结构设计：

函数名
返回值类型
creatMGraph_L(G)
int
creatadj(gra,G)
int
ljjzprint(G)
void
adjprint(gra,G)
void
BFSTraverse(gra)
void
DFStra(gra)
int
DFSTraverse_fen(gra)
int
MiniSpanTree_PRIM(g,G.vexnum)
int
MiniSpanTREE_KRUSCAL(G,gra)
void

三、 具体设计
1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；
邻接矩阵定义:
typedef struct ArcCell
{
VRType adj;//VRType是顶点关系类型。对无权图，用1或0表达相邻否；对带权图，则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[max][max];
typedef struct
{
VertexType vexs[max];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph_L;
邻接表的定义:
typedef struct ArcNode//弧结点
{
int adjvex;//该弧指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode//邻接链表顶点头接点
{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList;
typedef struct//图的定义
{
AdjList vertices[max];
int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
队列定义:
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
2． 主函数和其他函数的伪码算法；
主函数：
int main()
{
int s;
char y='y';
cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤菜单¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;
cout<<"||-------------------------【0、创建一个无向图------------------------------||"<<endl;
cout<<"||-------------------------【1、显示该图的邻接矩阵--------------------------||"<<endl;
cout<<"||-------------------------【2、显示该图的邻接表----------------------------||"<<endl;
cout<<"||-------------------------【3、广度优先遍历--------------------------------||"<<endl;
cout<<"||-------------------------【4、深度优先遍历--------------------------------||"<<endl;
cout<<"||-------------------------【5、最小生成树MiniSpanTree_PRIM算法-------------||"<<endl;
cout<<"||-------------------------【6、最小生成树MiniSpanTree_KRUSCAL算法----------||"<<endl;
cout<<"||-------------------------【7、连通分量------------------------------------||"<<endl;
cout<<"||¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;
while(y=='y')
{
cout<<"请选择菜单："<<endl;
cin>>s;
if(s==0)
{
++o;
if(o==2)
{
n=0;
l=0;
o=0;
}
}
switch(s)
{
case 0:cout<<"创建一个无向图："<<endl;
MGraph_L G;
creatMGraph_L(G);
ALGraph gra;
creatadj(gra,G);
break;
case 1:cout<<"邻接矩阵显示如下："<<endl;
ljjzprint(G);
break;
case 2:
cout<<"邻接表显示如下："<<endl;
adjprint(gra,G);
break;
case 3:
cout<<"广度优先遍历：";
BFSTraverse(gra);
cout<<endl;
break;
case 4:
cout<<"深度优先遍历：";
DFStra(gra);
cout<<endl;
break;
case 5:
if(n==0){cout<<"无权图没有最小生成树";break;}
else if(l>0){cout<<"若该图为非强连通图(具有多个连通分量)时，最小生成树不存在"<<endl;break;}
else
{
int i,g[max][max];
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
cout<<"普利姆算法:"<<endl;
MiniSpanTree_PRIM(g,G.vexnum);
break;
}
case 6:if(n==0){cout<<"无权图没有最小生成树";break;}
else if(l>0){cout<<"该图为非强连通图(具有多个连通分量)，最小生成树不存在"<<endl;break;}
else
{
cout<<"克鲁斯卡尔算法:"<<endl;
MiniSpanTREE_KRUSCAL(G,gra);
break;
}
case 7:cout<<"连通分量:"<<endl;
DFSTraverse_fen(gra);
break;
}
cout<<endl<<"是否继续？y/n:";
cin>>y;
if(y=='n')
break;
}
return 0;
}
邻接矩阵存储：
int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表达
{
char v1,v2;
int i,j,w;
cout<<"请输入顶点和弧的个数"<<endl;
cin>>G.vexnum>>G.arcnum;
cout<<"输入各个顶点"<<endl;
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k<G.arcnum;++k)
{
cout<<"输入一条边依附的顶点和权"<<endl;
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//拟定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1;
}
if(n>=1)cout<<"这是一个有权图"<<endl;
else cout<<"这是一个无权图"<<endl;
cout<<"图G邻接矩阵创建成功！"<<endl;
return G.vexnum;
}
邻接矩阵的输出：
void ljjzprint(MGraph_L G) //邻接矩阵的输出
{
int i,j;
if(n==0)
{
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj==int_max){cout<<"0"<<" ";}
else {cout<<G.arcs[i][j].adj<<" ";}
}
cout<<endl;
}
}
else
{
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj==int_max){cout<<"∞"<<" ";}
else {cout<<G.arcs[i][j].adj<<" ";}
}
cout<<endl;
}
}
}
用邻接表存储图：
int creatadj(ALGraph &gra,MGraph_L G)//用邻接表存储图
{
int i=0,j=0;
ArcNode *arc;//,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=int_max)
{
arc=(ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex=j;
arc->nextarc=gra.vertices[i].firstarc;
gra.vertices[i].firstarc=arc;
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
cout<<"图G邻接表创建成功！"<<endl;
return 1;
}
邻接表输出：
void adjprint(ALGraph gra,MGraph_L G) //邻接表输出
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
ArcNode *p;
cout<<"["<<i<<","<<G.vexs[i]<<"]";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<"->"<<"["<<p->adjvex<<"]";
p=p->nextarc;
}
cout<<"->"<<"End";
cout<<endl;
}
}
初始化队列：
Status InitQueue(LinkQueue &Q)//初始化队列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)return 0;//存储分派失败
Q.front->next=NULL;
return 1;
}
入队：
Status EnQueue(LinkQueue &Q,QElemType e)//入队,插入元素e为Q的新的队尾元素
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)return 0;//存储分派失败
p->data=e;p->next=NULL;
Q.rear->next=p;Q.rear=p;
return 1;
}
出队：
Status DeQueue(LinkQueue &Q,QElemType &e)//出队，若队列不空，则删除Q的队头元素，用e返回，并返回真，否则假
{
QueuePtr p;
if(Q.front==Q.rear)return 0;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return 1;
}
判断队为空：
Status QueueEmpty(LinkQueue Q)//判断队为空
{
if(Q.front==Q.rear) return 1;
return 0;
}
广度优先遍历：
void BFSTraverse(ALGraph gra)
{
int i,e;
LinkQueue q;
for(i=0;i!=gra.vexnum;++i)visited[i]=0;
InitQueue(q);
for(i=0;i!=gra.vexnum;++i)
if(!visited[i])
{
visited[i]=1;
cout<<gra.vertices[i].data;
EnQueue(q,i);
while(!QueueEmpty(q))
{
DeQueue(q,e);
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))
{
if(!visited[we])
{
visited[we]=1;
cout<<gra.vertices[we].data;
EnQueue(q,we);
}
}
}
}
}
深度优先遍历：
int DFS(ALGraph gra,int i)
{
visited[i]=1;
int we1;
cout<<gra.vertices[i].data;
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
{
we1=we;
if(visited[we]==0)
DFS(gra,we);
we=we1;
}
return 1;
}
int DFStra(ALGraph gra)
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
{
visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)DFS(gra,j);
}
return 0;
}
连通分量：
int DFSTraverse_fen(ALGraph gra)
{
int i,j;
for(i=0;i!=gra.vexnum;++i)
visited[i]=0;
for(j=0;j!=gra.vexnum;++j)
{
if(visited[j]==0)
{
DFS(gra,j);
cout<<endl;
l++;
}
}
return 0;
}

3. 重要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表达。图的广度优先遍历
图的邻接矩阵存储
图的邻接表存储

图的普利姆算法求最小生成树

四、 调试分析

1. 实际完毕的情况说明；
a. 先任意创建一个图；
b. 图的DFS,BFS的递归和非递归算法的实现
c. 最小生成树（两个算法）的实现，求连通分量的实现
d. 规定用邻接矩阵、邻接表等多种结构存储实现
支持的数据类型：整型和字符型

2.程序的性能分析，涉及时空分析；
本程序的图的遍历是以邻接表做图的存储结构，其时间复杂度为O（n+e）。

3.上机过程中出现的问题及其解决方案；
a.程序开始对无权图和有权图的邻接矩阵的输出时，无边都用的10000（无穷大int_max）表达的，这种表达和我们习惯上的0与∞的表达有差异。所以在程序中定义了全局变量n（初值为0）,来判断创建的无向图是有权图还是无权图，n>0为有权图，此时输出的时候用∞代替10000；n=0为无权图，此时输出的时候用0代替10000.
b.程序中有的功能对某些图是不合用的，比如无权图没有最小生成树，非强连通图没有最小生成树等。所以在程序中又新增了全局变量l,l>0时表达为非强连通图，则在求最小生成树时报错。
C.当程序先创建一个有权图后，n的值会大于1，第二次创无权图时也会被程序认为有权图，所以在程序中在定义全局变量o（初值为0）,来判断创建了几次图，当第二次创建图，即o=2时，所有全局变量在开始全归零。

4. 程序中可以改善的地方说明；
当建立一个图时先得求其连通分量，从而拟定全局变量l的值，从而才干判断该图是否有最小生成树。

五、 测试结果

创建一个无权图：

创建一个费强连通的有权图：
创建一个有权连通图：

六、 用户手册

a.先选0创建一个图。b.选择y继续操作。c.按照菜单编码选择操作。
七、体会与自我评价
在做这个程序的时候你一方面必须知道图的一些概念，图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素也许和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都也许相关。
当我们拿到一个图时，我们对该图的遍历就要有一些方法，所以有了深度优先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后根据我们人脑中的方法把它写成电脑算法。
对一个图我们还定义了连通分量，所以将图存到电脑中时，我们对连通分量得有个算法。
求图的最小生成树有两种算法，普利姆是从结点出发寻找权最小的边，知道所有结点都练通了；而克鲁斯卡尔算法则是从边出发，寻找使图连通的权值最小边的方法。
算法的实现从人脑到电脑的转变是比较复杂的一件事，规定做到具体到实现该方法的每一个环节，然后再将每一个环节通过代码实现。
这规定我们要明确各个数据元素和个元素之间的关系，然后才干明确使用算法去调用这些数据。
通过本次的课程设计，我对数据结构有了一定的结识，明白了数据结构中数据，数据关系，及对其操作的方法。但同时也发现在自己有很多的局限性，在使用语言和如何精炼语言需要进行更多的训练。
源代码：
#include <iostream>
#include <malloc.h>
using namespace std;
#define int_max 10000//最大值
static int n=0;//全局变量，判断有权图和无权图
static int o=0;//全局变量，清除BUG
static int l=0;//全局变量，清除BUG
#define inf 9999//最小值的最大值
#define max 20//最大顶点个数
typedef int VRType,QElemType,Status;
typedef char InfoType,VertexType;
//|||||||||||||||||||||||||邻接矩阵|||||||||||||||||||||||||||||||
//----------------------------邻接矩阵定义-------------------------
typedef struct ArcCell
{
VRType adj;//VRType是顶点关系类型。对无权图，用1或0表达相邻否；对带权图，则为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[max][max];
typedef struct
{
VertexType vexs[max];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph_L;
//-----------------------------------------------------------------
int localvex(MGraph_L G,char v)//返回V的位置
{
int i=0;
while(G.vexs[i]!=v)++i;
return i;
}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表达
{
char v1,v2;
int i,j,w;
cout<<"请输入顶点和弧的个数"<<endl;
cin>>G.vexnum>>G.arcnum;
cout<<"输入各个顶点"<<endl;
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k<G.arcnum;++k)
{
cout<<"输入一条边依附的顶点和权"<<endl;
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//拟定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1;
}
if(n>=1)cout<<"这是一个有权图"<<endl;
else cout<<"这是一个无权图"<<endl;
cout<<"图G邻接矩阵创建成功！"<<endl;
return G.vexnum;
}
void ljjzprint(MGraph_L G) //邻接矩阵的输出
{
int i,j;
if(n==0)
{
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj==int_max){cout<<"0"<<" ";}
else {cout<<G.arcs[i][j].adj<<" ";}
}
cout<<endl;
}
}
else
{
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj==int_max){cout<<"∞"<<" ";}
else {cout<<G.arcs[i][j].adj<<" ";}
}
cout<<endl;
}
}
}
//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

//-------------------------邻接表的定义-----------------------
typedef struct ArcNode//弧结点
{
int adjvex;//该弧指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode//邻接链表顶点头接点
{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList;
typedef struct//图的定义
{
AdjList vertices[max];
int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;

int creatadj(ALGraph &gra,MGraph_L G)//用邻接表存储图
{
int i=0,j=0;
ArcNode *arc;
for(i=0;i!=G.vexnum;++i)
{
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j].adj!=int_max)
{
arc=(ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex=j;
arc->nextarc=gra.vertices[i].firstarc;
gra.vertices[i].firstarc=arc;
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
cout<<"图G邻接表创建成功！"<<endl;
return 1;
}
void adjprint(ALGraph gra,MGraph_L G) //邻接表输出
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
ArcNode *p;
cout<<"["<<i<<","<<G.vexs[i]<<"]";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{
cout<<"->"<<"["<<p->adjvex<<"]";
p=p->nextarc;
}
cout<<"->"<<"End";
cout<<endl;
}
}
//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//------------------------队列定义------------------------
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;//队头指针