图

实验报告

20010 – 2011 学年第 1 学期 任课老师： 课程名称 实验题目 实验目的、要求 实验目的 数据结构 图 班级 实验时间 座号 姓名 实验日期： 3—11 提交日期： 3—12 1．熟悉图的存储结构； 2．熟悉图的创建操作； 3．熟悉图的遍历操作。 实验设计内容 1

1．理解实现无向图邻接表的创建的算法，理解实现无向图的深度优先遍历的算法；转换成程序并上机实现，并按要求撰写实验报告；以下例子作为一个测试用例. 例 a b c d G2 e 深度遍历：a b c  d e 2．实现无向图邻接矩阵的创建，实现无向图邻接矩阵方式存储的深度优先遍历的算法，转换成程序并上机实现； 3．（选做）无向图邻接表存储方式的广度优先遍历，转换成程序并上机实现； 1． 二、 实验报告 1.邻接表 #include #include #define MaxVertexNum 100 typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; typedef char VertexType; typedef struct node { /*边表结点*/ int adjvex; /*邻接点域*/ struct node *nextedge; /*链域 */ } EdgeNode; typedef struct vnode { /*顶点表结点*/ VertexType vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*/ 2

typedef struct { AdjList adjlist;/*邻接表*/ int n,e;/*图中当前顶点数和边数*/ int kind; /* 图的种类标志*/ } ALGraph; void CreateALGraph(ALGraph *G1) {/*建立无向图的邻接表表示 */ int i,j,k; EdgeNode *s; printf(\"qing shu ru dingdian shu he bian shu:\\n\"); scanf(\"%d %d\读入顶点数和边数*/ fflush(stdin); printf(\"input dingdian information:\\n\"); for(i=0;in;i++) { /*建立顶点表*/ /*scanf(\"%c\ G1->adjlist[i].vertex=getchar(); /*读入顶点信息*/ G1->adjlist[i].firstedge=NULL;/*边表置为空表*/ } printf(\"input (vi,vj)dingdian duixuhao:\\n\"); for(k=0;ke;k++) { /*建立边表*/ scanf(\"%d %d\读入边(vi，vj)的顶点对序号*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/ s->adjvex=j; /*邻接点序号为j*/ s->nextedge=G1->adjlist[i].firstedge; G1->adjlist[i].firstedge=s; /*将新结点*s插入顶点vi的边表头部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; /*邻接点序号为i*/ s->nextedge=G1->adjlist[j].firstedge; G1->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/ }/*end for?*/ }/* end CreateALGraph */ void DFS(ALGraph *G1,int i) { EdgeNode *p; printf(\"visit vertex:%c\\n\ visited[i]=TRUE; p=G1->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) 3

DFS(G1,p->adjvex); p=p->nextedge; } } void DFSTraverse(ALGraph *G1) /* 深度优先遍历*/ { int i; for(i=0;in;i++) visited[i]=FALSE; /*访问标志数组初始化*/ for(i=0;in;i++) if(!visited[i]) DFS(G1,i); } void main() { ALGraph *G; printf(\"Network Engeering 0902 zhangbinghuang NO.10\\n\"); CreateALGraph(G); DFSTraverse(G); } 2.邻接矩阵 #include #include #define MaxVertexNum 100 typedef char VertexType;/*顶点类型应由用户定义*/ typedef int EdgeType;/*边上的权值类型应由用户定义*/ typedef struct { VertexType vexs[MaxVertexNum]; /*顶点表 */ EdgeType edges[MaxVertexNum][MaxVertexNum]; /*邻接矩阵，可看作边表*/ int n,e; /*图中当前的顶点数和边数*/ }MGraph; void CreateMGraph(MGraph *G1) { /*建立无向网的邻接矩阵表示*/ int i,j,k,w; printf(\"qing shu ru dingdian shu he bian shu:\\n\"); scanf(\"%d%d\输入顶点数和边数*/ fflush(stdin); printf(\"input dingdian:\\n\"); 4

for(i=0;in;i++) /*读人顶点信息，建立顶点表*/ G1->vexs[i]=getchar(); fflush(stdin); for(i=0;in;i++) for(j=0; jn;j++) G1->edges[i][j]=0; /*邻接矩阵初始化*/ printf(\"input duiying dingdian de bian and quan: \\n \"); for(k=0;ke;k++) {/*读入e条边，建立邻接矩阵*/ scanf(\"%d%d%d\输入边(vi,vj)上的权w */ G1->edges[i-1][j-1]=w; G1->edges[j-1][i-1]=w; } }/*Create_MGraph */ typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; void DFSM(MGraph *G1,int i) { int j; printf(\"visit vertex:%c\\n\ visited[i]=TRUE; for(j=0;jn;j++) if(G1->edges[i][j]==1&&!visited[j]) DFSM(G1,j); } void DFSTraverse(MGraph *G1) /* 深度优先遍历*/ { int i; for (i=0;i< G1->n;++i) visited[i] = FALSE; /*访问标志数组初始化*/ for (i=0;in;++i) if(!visited[i]) DFSM(G1, i); } void main() { MGraph *G; printf(\"Network Engeering 0902 zhangbinghuang NO.10\\n\"); CreateMGraph(G); DFSTraverse(G); } 5

调试过程记录 实验结果记录以及与预期结果比较以及分析 1.邻接表 2.邻接矩阵 6

总结以及心得体会 教师评阅意见 教师： 年 月 日 填写内容时，可把表格扩大。实验的源程序代码（要有注释）附在表后。

7