实验四图的操作及应用分析.doc

实验四 图的操作及应用 实验课程名： 数据结构与算法 一、实验目的及要求 1、理解图的基本概念及术语。 2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。 3、熟练掌握图的两种遍历(深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列。 二、实验内容 任务一：构造如图1所示的图的邻接矩阵存储结构和邻接表存储结构。 图1 解答： （1）源代码：#includeiostream.h #include malloc.h #include conio.h #define INFINITY 1000 #define MAX_VERTEX_NUM 20 #define OK 1 #define STARTS ******************************** typedef enum{DG,DN,UDG,UDN} GraphKind; typedef int EType; typedef int 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; coutendlPlease input the number of G.vexnum (eg,G.vexnum=4): ; cinG.vexnum; //input the number of vex coutPlease input the number of G.arcnum (eg,G.arcnum=4): ; cinG.arcnum; //input the number of arc coutPlease input IncInfo (0 for none) : ; cinIncInfo; 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 } coutPlese input arc(V1--V2), For example: (V1=1,V2=3),(V1=2,V2=4)...endl; for(k=0;kG.arcnum;++k) //input arc(v1,v2) { coutendlPlease input the k+1th arcs v1 (0v1G.vexnum) :; cinv1; //input v1 coutPlease input the k+1th arcs v2 (0v2G.vexnum) :; cinv2; //input v2 coutPlease input the k+1th arcs weight :; cinw; //input weight i=v1; j=v2; while(i1||iG.vexnum||j1||jG.vexnum) //if (v1,v2) illegal,again { coutPlease input the k+1th arcs v1 (0v1G.vexnum) :; cinv1; coutPlease input the k+1th arcs v2 (0v1G.vexnum) :; cinv2; coutPlease input the k+1th arcs weight :; cinw; i=v1; j=v2; } //while end i--; j--; G.arcs[i][j].adj=G.arcs[j][i].adj=w; //weight coutG.arcs[i+1][j+1].adj=G.arcs[j+1][i+1].adj=wendl; if(In