数据结构实验四.doc

华北水利水电学院 数据结构 实验报告20 10 20 11 学年 第 一 学期 2008级 计算机 专业实验四 图的应用一、 实验目的：1掌握图的存储结构及其构造方法2掌握图的两种遍历算法及其执行过程二、 实验内容：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。三、 实验要求：1 各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。2 C/ C+完成算法设计和程序设计并上机调试通过。3 撰写实验报告，提供实验结果和数据。4 写出算法设计小结和心得。四、 程序源代码：第 4 页 共 4 页#include #include #define MAX_VERTEX_NUM 20typedef int VRType;typedef int InfoType;typedef int VertexType;typedef enumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCellVRType adj;/VRType是顶点关系类型，对无权图用1或0表示是否相邻； /对带权图则为权值类型InfoType *info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind;/图的种类标志MGraph;void CreateMG(MGraph &M)int i,j;M.kind=DN;printf(输入顶点数:);scanf(%d,&M.vexnum);printf(输入弧数:);scanf(%d,&M.arcnum);printf(输入顶点:n);for(i=0;iM.vexnum;i+)scanf(%d,&M.vexsi);printf(建立邻接矩阵:n);for(i=0;iM.vexnum;i+)for(j=0;jM.vexnum;j+)scanf(%d,&M.arcsij.adj);printf(输入相应权值:n);for(i=0;iM.vexnum;i+)for(j=0;jM.vexnum;j+)if(M.arcsij.adj)scanf(%d,&M.);typedef struct ArcNodeint adjvex;/该弧所指向的顶点在数组中的下标struct ArcNode *nextarc;InfoType *info;/该弧相关信息的指针ArcNode;typedef struct VNodeVertexType data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;void PrintDN(ALGraph G)int i;ArcNode *p;printf(顶点:n);for(i=0;iG.vexnum;+i)printf(%2d,G.verticesi.data);printf(n弧:n);for(i=0;iadjvex,p-info);p=p-nextarc;printf(n); /forvoid CreateMGtoDN(ALGraph &G,MGraph M)/采用邻接表存储表示,构造有向图G(G.kind=DN)int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;iG.vexnum;+i)/构造表头向量G.verticesi.data=M.vexsi;G.verticesi.firstarc=NULL;/初始化指针for(i=0;iG.vexnum;+i)for(j=0;jadjvex=j;p-nextarc=G.verticesi.firstarc;p-info=M.;G.verticesi.firstarc=p;void CreateDNtoMG(MGraph &M,ALGraph G)int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;iM.vexnum;+i)M.vexsi=G.verticesi.data;for(i=0;iadjvex.adj=1;p=p-nextarc;/whilefor(j=0;jM.vexnum;+j)if(M.arcsij.adj!=1)M.arcsij.adj=0;/forvoid PrintMatrix(MGraph M)int i,j;for(i=0;iM.vexnum;+i)for(j=0;jM.vexnum;+j)printf(%2d,M.arcsij.adj);printf(n);void main()MGraph M,N;ALGraph G;CreateMG(M);PrintMatrix(M);CreateMGtoDN(G,M);PrintDN(G);CreateDNtoMG(N,G);PrintMatrix(N);有向图五、