当前位置：文档之家› 数据结构实验-图的遍历和最小生成树

数据结构实验-图的遍历和最小生成树

实验名称：图的遍历和最小生成树

实验内容：

给定无向带权图G 如下，

1. 请分别用深度优先和广度优先两种方法从结点v 1开始对G 进行遍历。

2. 构造G 的最小生成树。

编程完成上述功能。

要求：

1. 必须完成图的存储功能。图的输入可由命令行完成。

2. 按遍历到的先后顺序依次输出G 中各结点内容。

3. 以文本形式输出生成树中各条边以及它们的权值。

一、概要设计

图的存储使用数组表示法，即邻接矩阵存储，结构体包含图的邻接矩阵，当前顶点数和弧数。图的初始化使用二重循环得到顶点和表的权值，邻接矩阵的打印使用二重for 循环。然后把图各边的权值按从小到大排序；然后依次把最小边加入进来，即生成最小生成树。克鲁斯卡尔算法：假设 WN=(V ,{E}) 是一个含有 n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有 n-1条边为止。

图的抽象数据类型:

ADT Graph{ v 1

v 2

v 3 v 4 v 5 v 6

v 7 24

8 15 6 7 3 2 9 3 5

4 3

数据对象V:V是具有相同特性的数据元素的集合,称为点集. 数据关系R:

R={VR}

VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径}

基本操作P:

CreatGraph(&G,V,VR)

初始条件:V是图的顶点集,VR是图中弧的集合.

操作结果:按V和VR是定义构造图G.

Sort(edge* ,MGraph *)

初始条件: 图G存在，各边权值已知；

操作结果:对权值进行排序；

Find(int *, int )

初始条件:前者为已存在的集合，后者为集合中的元素；

操作结果:查找函数，确定后者所属子集；

MiniSpanTree(MGraph *)

初始条件: 图G存在，各边权值已知；

操作结果:生成最小树；

Swapn(edge *, int, int)

初始条件: 图G存在，各边权值已知；

操作结果:交换某两个边的权值；

2 图的存储结构

typedef struct

{

int adj;

int weight;

}AdjMatrix[MAX][MAX];

typedef struct

{

AdjMatrix arc;

int vexnum, arcnum;

}MGraph;

typedef struct

{

int begin;

int end;

int weight;

}edge;

3 本程序包含的模块

}

1）初始化操作，结构体定义；

2）函数声明模块；

3）函数定义模块；

4）主程序模块

Main()

{

调用函数生成图；

判断图是否为空；（空则从新输入）

调用函数生成最小生成树；

退出；

二、详细设计

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

//…………………………………………邻接矩阵定义……………………typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[max][max];

typedef struct

{

char 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;

G.vexnum=7;G.arcnum=12;

for(i=0;i!=G.vexnum;++i)

{

cout<<"输入顶点V"<

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;

}

G.arcs[0][1].adj=24;

G.arcs[1][0].adj=24;

G.arcs[0][2].adj=8;

G.arcs[2][0].adj=8;

G.arcs[0][3].adj=15;

G.arcs[3][0].adj=15;

G.arcs[1][4].adj=6;

G.arcs[4][1].adj=6;

G.arcs[1][6].adj=3;

G.arcs[6][1].adj=3;

G.arcs[2][4].adj=7;

G.arcs[4][2].adj=7;

G.arcs[2][5].adj=3;

G.arcs[5][2].adj=3;

G.arcs[3][5].adj=5;

G.arcs[5][3].adj=5;

G.arcs[3][6].adj=4;

G.arcs[6][3].adj=4;

G.arcs[4][5].adj=2;

G.arcs[5][4].adj=2;

G.arcs[4][6].adj=9;

G.arcs[6][4].adj=9;

G.arcs[5][6].adj=3;

G.arcs[6][5].adj=3;

cout<<"图G邻接矩阵创建成功！"<

return G.vexnum;

}

void ljjzprint(MGraph_L G) //邻接矩阵的输出

{

int i,j;

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

cout<

}

int visited[max];//访问标记

int we;

typedef struct arcnode//弧结点

{

int adjvex;//该弧指向的顶点的位置

struct arcnode *nextarc;//弧尾相同的下一条弧

char *info;//该弧信息

}arcnode;

typedef struct vnode//邻接链表顶点头接点

{

char data;//结点信息

arcnode *firstarc;//指向第一条依附该结点的弧的指针

}vnode,adjlist;

typedef struct//图的定义

{

adjlist vertices[max];

int vexnum,arcnum;

int kind;

}algraph;

//…………………………………………队列定义……………………typedef struct qnode

{

int data;

struct qnode *next;

}qnode,*queueptr;

typedef struct

{

queueptr front;

queueptr rear;

}linkqueue;

//………………………………………………………………………typedef struct acr

{

int pre;//弧的一结点

int bak;//弧另一结点

int weight;//弧的权

}edg;

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(gra.vertices[i].firstarc==NULL)

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode *)malloc(sizeof(arcnode));

arc->adjvex=j;

gra.vertices[i].firstarc=arc;

arc->nextarc=NULL;

p=arc;

++j;

while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

tem=(arcnode *)malloc(sizeof(arcnode));

tem->adjvex=j;

gra.vertices[i].firstarc=tem;

tem->nextarc=arc;

arc=tem;

++j;

}

--j;

}

else

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode *)malloc(sizeof(arcnode));

arc->adjvex=j;

p->nextarc=arc;

arc->nextarc=NULL;

p=arc;

}

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

return 1;

}

int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点

//即以V为尾的第一个结点

{

if(v.firstarc!=NULL)

return v.firstarc->adjvex;

}

int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点{

arcnode *p;

p=v.firstarc;

while(p!=NULL&&p->adjvex!=w)

{

p=p->nextarc;

}

if(p->adjvex==w&&p->nextarc!=NULL)

{

p=p->nextarc;

return p->adjvex;

}

if(p->adjvex==w&&p->nextarc==NULL)

return -10;

}

int initqueue(linkqueue &q)//初始化队列

{

q.rear=(queueptr)malloc(sizeof(qnode));

q.front=q.rear;

if(!q.front)

return 0;

q.front->next=NULL;

return 1;

}

int enqueue(linkqueue &q,int e)//入队

{

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;

}

int dequeue(linkqueue &q,int &e)//出队

{

queueptr p;

if(q.front==q.rear)

p=q.front->next;

e=p->data;

q.front->next=p->next;

if(q.rear==p)

q.rear=q.front;

free(p);

return 1;

}

int queueempty(linkqueue q)//判断队为空

{

if(q.front==q.rear) return 1;

return 0;

}

void bfstra(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<

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<

enqueue(q,we);

}

int dfs(algraph gra,int i)

{

visited[i]=1;

int we1;

cout<

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)

{

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 bfstra_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<

}

return 0;

}

typedef struct

{

int adjvex;

int lowcost;

}closedge;

int prim(int g[][max],int n) //最小生成树PRIM算法

{

FILE * fp;

char ch;

if((fp=fopen("tree.txt","w+"))==NULL)

{

printf("cannot open file\n");

exit(0);

}

int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径

//prevex[]存储最短路径在U中的结点

int i,j,k,min;

for(i=2;i<=n;i++) //n个顶点，n-1条边

{

lowcost[i]=g[1][i]; //初始化

prevex[i]=1; //顶点未加入到最小生成树中

}

lowcost[1]=0; //标志顶点1加入U集合

for(i=2;i<=n;i++) //形成n-1条边的生成树

{

min=inf;

k=0;

for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]

min=lowcost[j];

k=j;

}

printf("(V%d,V%d)%d\t",prevex[k],k,min);

fprintf(fp,"(V%d,V%d)%d",prevex[k],k,min);

fputc('\n',fp);

lowcost[k]=0; //顶点k加入U

for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值if(g[k][j]

{

lowcost[j]=g[k][j];

prevex[j]=k;

}

printf("\n");

}

fclose(fp);

return 0;

}

int acrvisited[100];//kruscal弧标记数组

int find(int acrvisited[],int f)

{

while(acrvisited[f]>0)

f=acrvisited[f];

return f;

}

void kruscal_arc(MGraph_L G,algraph gra)

{

edg edgs[20];

int i,j,k=0;

for(i=0;i!=G.vexnum;++i)

for(j=i;j!=G.vexnum;++j)

{

if(G.arcs[i][j].adj!=10000)

{

edgs[k].pre=i;

edgs[k].bak=j;

edgs[k].weight=G.arcs[i][j].adj;

++k;

}

int x,y,m,n;

int buf,edf;

for(i=0;i!=gra.arcnum;++i)

acrvisited[i]=0;

for(j=0;j!=G.arcnum;++j)

{

m=10000;

for(i=0;i!=G.arcnum;++i)

{

if(edgs[i].weight

{

m=edgs[i].weight;

x=edgs[i].pre;

y=edgs[i].bak;

n=i;

}

buf=find(acrvisited,x);

edf=find(acrvisited,y);

edgs[n].weight=10000;

if(buf!=edf)

{

acrvisited[buf]=edf;

cout<<"("<

cout<

}

int main()

{

algraph gra;

MGraph_L G;

int i,d,g[20][20];

char a='a';

d=creatMGraph_L(G);

creatadj(gra,G);

vnode v;

cout<<"请选择："<

cout<<"0、显示该图的邻接矩阵"<

cout<<"2、深度优先遍历"<

cout<<"3、最小生成树"<

int s;

char y='y';

while(y='y')

{

cin>>s;

switch(s)

{

case 0:

cout<<"图G邻接矩阵显示如下："<

ljjzprint(G);

break;

case 1:

cout<<"G图的广度优先遍历：";

bfstra(gra);

cout<

break;

case 2:

for(i=0;i!=gra.vexnum;++i)

{

visited[i]=0;

}

cout<<"G图的深度优先遍历：";

dfstra(gra);

cout<

break;

case 3:

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<<"prim:"<

prim(g,d);

break;

}

cout<

cin>>y;

if(y=='n')

break;

}

system("pause");

return 0;

}

三、算法的时空分析：

在localvex函数中，有n1个顶点返回，则复杂度为0（n1）。

在creatMGraph_L函数中，输入顶点n1个，存储顶点n1^2，输入弧n2，存入弧2n2则复杂度为0（n1+n1^2+n2+2n2）。

在bfstra函数中，经过顶点两遍，则复杂度为0（2n1）。

在dfs函数中，经过顶点两遍，则复杂度为0（2n1）。

在prim函数中，经过n1个顶点一遍，形成n1-1条边，寻找满足边的一个顶点在U,另一个顶点在V的最小边须经历n1-1个点，则复杂度为0（3n1-2）。

程序复杂度为0（n1^2+9n1+3n2-2）

四、测试结果

运行：

…………创建无向图…………

输入顶点0

输入顶点1

输入顶点2

输入顶点3

输入顶点4

输入顶点5

输入顶点6

图G存储成功！

…………………菜单……………………

1、广度优先遍历…………………………

2、深度优先遍历…………………………

3、最小生成树…………………

请选择菜单：

广度优先遍历：1432675

是否继续？y/n:y

请选择菜单：

深度优先遍历：1465327

是否继续？y/n:y

请选择菜单：

(0,2)8

(2,5)3

(5,4)2

(5,6)3

(6,1)3

(6,3)4

是否继续？y/n:n

请按任意键继续。。。。。。。

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

算法设计与分析课程设计报告学院计算机科学与技术专业计算机科学与技术年级2011 姓名XXX 学号 2013年5 月19 日

题目：最小生成树问题的算法实现及复杂度分析摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。

图的遍历和生成树求解实现_课程设计报告

中北大学数据结构课程设计说明书 2011年12月19日

1设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2设计内容和要求设计内容： (1)采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2) 图的DFS,BFS的递归和非递归算法的实现（3) 最小生成树（两个算法）的实现，求连通分量的实现（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。 4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和

数据结构课程设计-图的遍历和生成树的求解实现说明书

******************* 实践教学 ******************* 兰州理工大学计算机与通信学院 2012年春季学期算法与数据结构课程设计题目：图的遍历和生成树的求解实现专业班级：计算机科学与技术姓名：*** 学号：1234567 指导教师：**** 成绩：

目录摘要 (3) 前言 (4) 正文 (5) 1.问题描述： (5) 2.采用类C语言定义相关的数据类型 (5) 3．各模块流程图及伪码算法 (6) 4．函数的调用关系图 (8) 5．调试分析 (9) 1.调试中遇到的问题及对问题的解决方法 (9) 2.算法的时间复杂度和空间复杂度 (9) 6.测试结果 (10) 参考文献 (14)

图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。

分别利用prim算法和kruskal算法实现求图的最小生成树

/*分别利用prim算法和kruskal算法实现求图的最小生成树*/ #include #include #define MaxVertexNum 12 #define MaxEdgeNum 20 #define MaxValue 1000 typedef int Vertextype; typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; typedef Vertextype vexlist[MaxVertexNum]; int visited[MaxVertexNum]={0}; struct edgeElem {int fromvex; int endvex; int weight; }; typedef struct edgeElem edgeset[MaxVertexNum]; void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e) {int i,j,k,w; printf("输入%d个顶点数据",n); for(i=0;i

if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; printf("输入%d条无向带权边",e); for(k=0;k

最小生成树算法分析

最小生成树算法分析一、生成树的概念若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。

例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数）以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边：选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)；将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 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={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈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