数据结构实验五实验报告.doc

数据结构实验报告
实验五
图子系统
实验题目:图的遍历问题
专业班级:网络工程 1002班
组长:王星(2010100230)
组员:郭坤铭(2010100243)
张磊(2010100244)
2012年 5月 18日
实验报告
实验类型__综合__ 实验室_软件实验室二__
实验题目
图的遍历问题
二、实验目的和要求
1、掌握图的存储思想及其存储实现
2、掌握图的深度、广度优先遍历算法思想及其程序实现
3、掌握图的常见应用算法的思想及其程序实现
三、需求分析
本演示程序用c++,完成用户用键盘输入以下结点数据:太原、成都、北京、上海、天津、大连、河北。(1)建立一个有向图或无向图(自定)的邻接表并输出该邻接表。(2)在图的邻接表的基础上计算各顶点的度,并输出。(3)以有向图的邻接表为基础实现输出它的拓扑排序序列。(4)采用邻接表存储实现无向图的深度优先遍历。(5)采用邻接表存储实现无向图的广度优先遍历。(6)采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。最后,在主函数中设计一个简单的菜单,分别调试上述算法。
概要设计
为了实现上述程序功能,需要定义如下内容
基本数据类型定义如下:
typedef struct node{ //边表结点
int adj; //边表结点数据域
struct node *next;
}node;
typedef struct vnode //顶点表结点
{ char name[20];
node *fnext;
}vnode,AList[20];
typedef struct
{ AList List; //邻接表
int v,e; //顶点树和边数
}*Graph;
Graph CreatDG(){ } //建立无向邻接表
Graph CreatAG(){ } //有向邻接图
void Print(Graph G){} //输出图的邻接表
void CreateAN(AGraph *G1){} //构造邻接矩阵结构的图G
void Du(Graph G){} //输出各顶点的度数
void DFSTravel(Graph G){} //深度优先遍历
void BFSTravel(Graph G){} //广度优先遍历
详细设计
#include<>
#include<>
#include<>
typedef struct node{//边表结点
int adj;//边表结点数据域
struct node *next;
}node;
typedef struct vnode{//顶点表结点
char name[20];
node *fnext;
}vnode,AList[20];
typedef struct{
AList List;//邻接表
int v,e;//顶点树和边数
}*Graph;
//建立无向邻接表
Graph CreatDG(){
Graph G;
int i,j,k;
node *s;
G=malloc(20*sizeof(vnode));
printf("请输入图的顶点数和边数(空格隔开):");
scanf("%d%d",&G->v,&G->e);//读入顶点数和边数
for(i=0;i<G->v;i++){
printf("请输入图中第%d元素:",i+1);
scanf("%s",G->List[i].name);//读入顶点信息
G->List[i].fnext=NULL;//边表置为空表
}
for(k=0;k<G->e;k++){
printf("请请输入第%d条边的两顶点序号(空格隔开):",k+1);
scanf("%d%d",&i,&j);//读入边(Vi,Vj)的顶点对序号;
s=(node *)malloc(sizeof(node));//生成边表结点
s->adj=j;
s->next=G->List[i].fnext;
G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部
s=(node *)malloc(sizeof(node));
s->adj=i;//邻接点序号为i
s->next=G->List[j].fnext;
G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部
}
return G;
}
//有向邻接图
Graph CreatAG(){
Graph G;
int i,j