图基本操作实验报告 [2).doc

图的基本操作实验报告 P向禹 题目要求及其分析 建立一个图，将图进行初始化，通过输入图的结点信息构建图的邻接链表，对图的结构进行深度和广度优先遍历，由此构建图的最小生成树。 要求：输入图的各个结点信息建立图的邻接链表，以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列，同时以用户指定的结点为起点，分别利用普利姆算法和克鲁斯卡尔算法求图的最小生成树。 设计概要 首先根据图的存储结构定义图的链表结构（包括顶点关系类型，与弧或边相关的信息，指向下一个结点的指针,图的当前顶点数与边数邻接矩阵等），采用二维数组形式存储图的邻接矩阵，以邻接表来作为图的链式存储结构，每个结点由邻接点域，链域和数据域组成，由此可构造图G。 图的深度优先遍历：从某个顶点v出发访问，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到所有与v相邻的顶点都被访问到，若途中尚有顶点未被访问，则另选途中一个未被访问的电作为起始点，重复上述过程直到所有顶点被访问到。 图的广度优先遍历：从v出发，依次访问v和v的未被访问的邻接点，然后从这些邻接点出发访问它们的邻接点，直到所有已被访问的顶点的邻接点都被访问到，若尚有未被访问到的顶点，则选取一个顶点重复上述步骤，直到所有顶点被访问到。 最小生成树：假设联通网N=（V,{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个分量自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则社区此边额选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。 3．详细设计（主要算法步骤描述） typedef struct ArcCell{ //VRtype是顶点关系类型，对无权图，用1或0 VRType adj; //表示相邻否；对带权图，则为权值类型 InfoType *info; //该弧相关信息的指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点输和弧数 GraghKind kind; //图的种类标志 }Mgragh; Status CreateUDN(Mgragh G){ //采用数组（邻接矩阵）表示法，构造无向网G scanf(G.vexnum,G.arcnum,IncInfo); //IncInfo为0则各弧不含其它信息 for(i=0;iG.vexnum;++i); //初始化邻接矩阵 for(j=0;jG.vexnum;++j) G.arcs[i][j]={INFINITY,NULL};//{adj,info} for(k=0;kG.arcnum;++K){ //构造邻接矩阵 scanf(v1,v2,w); //输入一条边依附的顶点及权值 i=LocateVex(G,v1);j= LocateVex(G,v2); //确定v1,v2在G中的位置 G.arc[i][j].adj=w; // 弧v1,v2的权值 if(IncInfo)Input(*G.arcs[i][j].info); //若弧含有相关信息，则输入 G.arcs[j][i]=G.arcs[i][j]; } return OK; } typedef struct Arcnode{ int adjvex; //该弧指向的顶点位置 struct *nextarc; //指向下一条弧的指针 INfoType *info; //该弧相关信息的指针 }Arcnode;