24李后浪实验四.doc

实验四 图的操作及应用 实验课程名：数据结构与算法 专业班级：网络工程（二）班 学号：201240420224 姓名： 李后浪 实验时间： 12.2 12.9 34节 实验地点： K4-203 指导教师： 邓丹君 一、实验目的和要求 1、理解图的基本概念及术语。 2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。 3、熟练掌握图的两种遍历(深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列。 4、理解最小生成树的概念，能按Prim算法构造最小生成树。 二、实验内容 1、构造图的邻接矩阵存储结构和邻接表存储结构。 解答： 源代码： 图的邻接矩阵存储结构： #include stdio.h #include stdlib.h # define INFINITY 1000 # define MAX_VERTEX_NUM 20 # define OK 1 typedef enum{DG,DN,UDG,UDN} GraphKind; typedef int EType; typedef char InfoType; typedef int VertexType; typedef struct ArcCell //define structure MGraph { EType adj; InfoType *info; }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; }MGraph; int CreatUDN(MGraph G) //CreatUDN() sub-function { int IncInfo,i,j,k,v1,v2,w; char in[100]; printf(Please input the number of G.vexnum (eg,G.vexnum=4): \n); scanf(%d,G.vexnum); //input the number of vex printf(Please input the number of G.arcnum (eg,G.arcnum=4): \n); scanf(%d,G.arcnum); //input the number of arc printf(Please input IncInfo (0 for none) : \n); scanf(%d,IncInfo); for(i=0;iG.vexnum;++i) for(j=0;jG.vexnum;++j) { G.arcs[i][j].adj=INFINITY; //initial G.arcs[i][j].adj G.arcs[i][j].info=NULL; //initial G.arcs[i][j].info } printf(Plese input arc(V1--V2), For example: (V1=1,V2=3),(V1=2,V2=4)... \n); for(k=0;kG.arcnum;++k) //input arc(v1,v2) { printf(Please input the %dth arcs v1 (0v1G.vexnum) : \n,k+1); scanf(%d,v1); //input v1 printf(Please input the %dth arcs v2 (0v2G.vexnum): \n,k+1); scanf(%d,v2); //input v2 printf(Please input the %dth arcs weight : \n,k+1); scanf(%d,w); //input weight i=v1; j=v2; while(i1||iG.vexnum||j1||jG.vexnum) //if (v1,v2) illegal,again { printf(Please input the %dth a