C++邻接链表的方式确定一个无向网设计报告Word文档下载推荐.docx
《C++邻接链表的方式确定一个无向网设计报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《C++邻接链表的方式确定一个无向网设计报告Word文档下载推荐.docx（31页珍藏版）》请在冰点文库上搜索。
邻接链表是一种链式存储结构。
在邻接链表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。
每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；
数据域存储和边或弧相关的信息，如权值等。
所以一开始必须先定义邻接链表的边结点类型以及邻接链表类型，并对邻接链表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向（此处默认为无向），以及各条边的起点与终点及权值，建立图的邻接链表。
（2）邻接矩阵
图的邻接矩阵存储表示即是数组存储表示，在邻接矩阵中，我们定义两个数组分别存储数据元素的信息和数据元素之间的关系（边或弧）的信息，以二维数组表示有n个顶点的图时，需存放n个顶点信息和n的平方个弧信息的存储量。
借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求得各个顶点的度。
故在建立邻接矩阵之前，必须先定义顶点关系类型和相关指针指示弧的信息。
（3）广度优先遍历
假设从图总某顶点出发，在访问了v之后依次访问v的各个未曾访问到的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到。
若此时图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问饿v有路径相通且路径长度为1,2….的顶点。
和深度优先搜索类似，在遍历过程中也需要一个访问标志数组。
并且，为了顺次访问路径长度为2,3…的顶点，需附设队列以存储已被访问的路径长度为1,2….的顶点。
所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。
同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。
当队列非空时进行循环处理。
当结点被访问时对其进行标志，并入队列。
通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。
（4）普里姆算法
假设N=（V,{E}）是连通网，TE是N上最小生成数中边的集合。
算法从U={U0}，TE={}开始，重复执行如下操作；
在所有的边（u,v）中找一条代价最小的边（u0,v0）并入集合TE,同时V0并入U,直到U=V为止。
此时TE中必有n-1条边，则，T=（V,{TE}）为N的最小生成树。
（5）克鲁斯卡尔算法
假设连通网N=（V,{E}）,则令最小生成树的初始状态为只有n个顶点且无边的非连通图T=（V,{}）,图中每个顶点自成一个连通分量。
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。
依次类推，直到T中的所有顶点都在同一个连通分量上为止。
2．主要的数据结构设计说明
图的邻接矩阵、邻接表的建立。
图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树。
3．程序的主要流程图
4．程序的主要模块
用邻接链表的方式确定一个无向图，以邻接矩阵的方式输出，再进行图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树并输出。
5．程序的主要函数及其伪代码说明（不需要完整的代码）
Graph（）;
构造函数，构造无向网络图（以邻接表方式构造）
voidBuildAndDisplay（）;
邻接矩阵的建立和输出
voidBFTraverse（）;
广度优先遍历
voidPrim（MinSpanTree<
A>
&
T）;
普里姆算法
voidKruskal（MinSpanTree<
克鲁斯卡尔算法
三、上机结果及体会
1．上机过程中出现的问题及其解决方案。
问题：
编译时出现许多错误。
解决方案：
有很多是细节错误，简单改正下即可。
但还有一些是算法上的
错误，需要断点逐步调试找到错误。
找错误时要耐心和细心。
2．程序中可以改进的地方说明
（1）程序中的数据要以正确方式输入，否则会出错。
可以添加语句实现对
不正确数据的重新输入。
（2）该程序只能构造一个网络无向图。
可以在主程序中设计循环来选择是
否继续构造无向图。
四、实验源程序
1．无向网络图的边节点类定义
#ifndefARCNODE
#defineARCNODE
template<
classA>
classArcNode//无向网络图的边节点类定义
{
public:
ArcNode<
*nextarc;
intvex;
Aweight;
//构造边节点
ArcNode（）{};
ArcNode（intv,Aw）
{
vex=v;
weight=w;
nextarc=NULL;
}
};
#endif
2．无向网络图的顶点节点类定义
#ifndefVERTEXNODE
#defineVERTEXNODE
classV,classA>
classVertexNode
//无向网络图的顶点节点类定义
*first;
Vdata;
//构造函数
VertexNode（）{};
VertexNode（Vd）
data=d;
first=NULL;
3．最小生成树的类定义
#ifndefMINSPANTREE
#defineMINSPANTREE
#include"
MSTArcNode.h"
constintMaxNumArcs=20;
//最大边数量
classMinSpanTree//最小生成树的类定义
protected:
MSTArcNode<
*arctable;
//存放边的数组
intCurrentNumArcs;
//当前边数
MinSpanTree（）
CurrentNumArcs=0;
arctable=newMSTArcNode<
[MaxNumArcs];
voidInsert（MSTArcNode<
e）
if（CurrentNumArcs<
MaxNumArcs）
arctable[CurrentNumArcs++]=e;
else
cout<
<
"
超出能存放的最大边数量"
;
~MinSpanTree（）
delete[]arctable;
4．最小生成树边节点的类定义
#ifndefMSTARCNODE
#defineMSTARCNODE
classMSTArcNode//生成树边节点的类定义
intvex1,vex2;
//边的依附顶点
//边的权值
MSTArcNode（Aw=0）
5．普里姆算法中的辅助数组closearc[]的类定义
#ifndefCLOSEARCTYPE
#defineCLOSEARCTYPE
classCloseArcType
//普里姆算法中的辅助数组closearc[]的类定义
Alowweight;
intnearvex;
6．克鲁斯卡尔算法中最小堆的类定义
#ifndefMINHEAP
#defineMINHEAP
#include<
iostream>
classT>
classMinHeap//最小堆的类定义
private:
T*heapArr;
//存放堆中数据元素的数组
intheapCurrentSize;
//当前数据元素个数
intheapMaxSize;
//堆中数据元素最大数目
intIsFull（）const//判断堆是否满。
满返回，否则返回
returnheapCurrentSize==heapMaxSize;
intIsEmpty（）const//判断堆是否空。
空返回，否则返回
returnheapCurrentSize==0;
voidFilterUp（intp）//从p开始向上调整。
使序列成为堆
intj=p,i;
Ttemp=heapArr[j];
i=（j-1）/2;
while（j>
0）
{
if（heapArr[i].weight<
=temp.weight）
break;
else
{
heapArr[j]=heapArr[i];
j=i;
i=（j-1）/2;
}
}
heapArr[j]=temp;
voidFilterDown（constintstart）
//向下调整从start到heapCurrentSize-1为止的子序列成为最小堆
inti=start,j;
Ttemp=heapArr[i];
j=2*i+1;
//j为i的左孩子
while（j<
=heapCurrentSize-1）
if（j<
heapCurrentSize-1&
heapArr[j].weight>
heapArr[j+1].weight）
j++;
//在左右孩子中选权值小的
if（temp.weight<
=heapArr[j].weight）
heapArr[i]=heapArr[j];
i=j;
j=2*j+1;
heapArr[i]=temp;
MinHeap（intmaxSize）
if（maxSize<
=0）
堆得大小不能小于"
endl;
return;
heapMaxSize=maxSize;
//确定堆的最大空间
heapArr=newT[heapMaxSize];
//创建堆
heapCurrentSize=0;
//初始化
voidInsert（constT&
d）
if（IsFull（））//堆满
堆已满"
heapArr[heapCurrentSize]=d;
//在堆尾插入元素d
FilterUp（heapCurrentSize）;
//向上调整为堆
heapCurrentSize++;
TDeleteTop（）
if（IsEmpty（））
推已空"
returnNULL;
Ttemp=heapArr[0];
//取堆顶元素
heapArr[0]=heapArr[heapCurrentSize-1];
//堆末元素上移到堆顶
heapCurrentSize--;
FilterDown（0）;
//从堆顶开始自顶向下调整为堆
returntemp;
#endif
7．克鲁斯卡尔算法中并查集的类定义
#ifndefUFSETS
#defineUFSETS
classUFSets;
classTreeNode//定义树的双亲表示节点类
friendclassUFSets<
T>
TTdata;
//数据域
intparent;
//双亲域
classUFSets//并查集的类定义
TreeNode<
*sets;
//存储集合元素的数组
intsize;
//集合大小
intOrder（Td）//定位函数，确定数据元素d在数组中的位置
intp=0;
while（p<
size）
if（sets[p].Tdata.data==d.data）
returnp;
p++;
return-1;
UFSets（T*arr,intn）//构造函数
size=n;
sets=newTreeNode<
[size];
for（inti=0;
i<
size;
i++）
sets[i].parent=-1;
sets[i].Tdata=arr[i];
~UFSets（）
delete[]sets;
intFind（Td）//查找函数，确定数据元素d所在的等价类
intp;
if（（p=Order（d））==-1）
return-1;
//元素d不在任何等价类中
if（sets[p].parent<
returnp;
//p为一个等价类根结点的序号
returnFind（sets[sets[p].parent].Tdata）;
//求p的双亲所在的等价类
voidUnion（ints1,ints2）
//合并函数，把以s1，s2为根的两个等价类合并成一个等价类
sets[s1].parent=sets[s1].parent+sets[s2].parent;
//两个等价类的元素个数相加
sets[s2].parent=s1;
//s2的双亲指针指向s1
8．无向网络图的类定义
#ifndefGRAPH
#defineGRAPH
string>
iomanip>
ArcNode.h"
VertexNode.h"
MinSpanTree.h"
CloseArcType.h"
UFSets.h"
MinHeap.h"
usingnamespacestd;
constintMaxVertexes=20;
constintMaxNum=999999;
//表示无穷
classGraph//无向网络图类定义
Aarcs[MaxVertexes][MaxVertexes];
//邻接矩阵
VertexNode<
V,A>
*VertexesTable;
intCurrentNumVertexes;
//取v在顶点节点表中的位置
intGetVertexPos（constV&
v）
CurrentNumVertexes;
if（VertexesTable[i].data==v）
returni;
Graph（）
intnum;
Vd;
CurrentNumVertexes=0;
VertexesTable=newVertexNode<
[MaxVertexes];
inte;
Vtail,head;
Aw;
cout<
输入要插入的顶点数：
cin>
>
num;
while（num>
MaxVertexes）
超过最大顶点数，请重新输入：
cin>
for（inti=1;
=num;
i++）//顶点插入顶点表中
if（CurrentNumVertexes<
输入第"
个顶点：
d;
VertexesTable[i-1].data=d;
VertexesTable[i-1].first=NULL;
CurrentNumVertexes++;
请输入要插入边数：
e;
while（e>
num*（num-1）/2）
超过最大边数，请重新输入：
=e;
条边的个依附顶点和权值：
tail>
head>
w;
//输入顶点和权值
InsertArc（tail,head,w）;
//析构函数
~Graph（）
ArcNode<
*p=VertexesTable[i].first;
while（p）//逐条边释放
VertexesTable[i].first=p->
nextarc;
deletep;
p=VertexesTable[i].first;
delete[]VertexesTable;
//释放顶点表
//取得点的信息
VGetValue（intv）
if（v>
=0&
v<
CurrentNumVertexes）
returnVertexesTable[v].data;
returnNULL;
//访问节点
voidvisit（Vx）
----->
x<
//插入边
voidInsertArc（V&
head,V&
tail,Aw）
intt=GetVertexPos（tail）,h=GetVertexPos（head）;
if（t==-1）
cout<
输入的顶点"
tail<
不存在"
elseif（h==-1）
head<
ArcNode<
*p=newArcNode<
（h,w）;
if（VertexesTable[t].first==NULL）
VertexesTable[t].first=p;
else
{
ArcNode<
*q=VertexesTable[t].first;
if（q->
nextarc）
q=q->
q->
nextarc=p;
}
p=newArcNode<
（t,w）;
if（VertexesTable[h].first==NULL）
VertexesTable[h].first=p;
*q=VertexesTable[h].first;
CurrentNumArcs++;
//获取v的第一个邻接点
intGetFirst（intv）
if（VertexesTable[v].first）
returnVertexesTable[v].first->
vex;
//获取v在w后的一个邻接点
intGetNext（intv,intw）
for（ArcNode<
*p=VertexesTable[v].first;
p;
p=p->
if（p->
vex==w&
p->
nextarc!
=NULL）
returnp->
nextarc->
//建立邻接矩阵并显示
voidBuildAndDisplay（）
intnum=GetVertexesNum（）;
for（intj=0;
j<
j++）
升级会员 