数据结构实验---图的储存与遍历(共10页)

1、数据结构课程实验报告学号： 姓名： 实验日期： 2016.1.7实验名称： 图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS和BFS遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。测试数据：V0V1V4V3V2如图所示题目2：对以邻接表为存储结构的图进行DFS和BFS遍历问题描述：以邻接表为图的存储结构，实现图的DFS和BF

2、S遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS和BFS序列。测试数据：如图所示1 010 3 3 4 V0V1V2V3V4三、附录： 在此贴上调试好的程序。#include<stdio.h>#include<malloc.h>#include<string.h>#define M 100 typedef struct node char vexM2; int edgeM M ; int n,e; Graph;int visitedM;Graph *Create_Graph() Graph *GA; int i,j,k,w; GA=(Graph

3、*)malloc(sizeof(Graph);printf ("请输入矩阵的顶点数和边数(用逗号隔开)：n");scanf("%d,%d",&GA->n,&GA->e);printf ("请输入矩阵顶点信息：n"); for(i = 0;i<GA->n;i+) scanf("%s",&(GA->vexi0),&(GA->vexi1); for (i = 0;i<GA->n;i+) for (j = 0;j<GA->n;j+)

4、 GA->edgeij = 0; for (k = 0;k<GA->e;k+) printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edgeij = w; return(GA);void dfs(Graph *GA, int v) int i; printf("%c%cn",GA->vexv0,GA->vexv1); visitedv=1; for(i=0; i<G

5、A->n; i+) if (GA->edgevi=1 && visitedi=0) dfs(GA, i);void traver(Graph *GA) int i; for(i=0; i<GA->n; i+) visitedi=0; for(i=0; i<GA->n;i+) if(visitedi=0) dfs(GA, i);void bfs( Graph *GA, int v) int j,k,front=-1,rear=-1; int QM; printf("%c%cn",GA->vexv0,GA->vex

6、v1); visitedv=1; rear=rear+1; Qrear=v; while (front!=rear) front=front+1;k=Qfront; for (j=0; j<GA->n; j+) if (GA->edgekj=1 && visitedj=0) printf("%c%cn",GA->vexj0,GA->vexj1); visitedj=1; rear=rear+1; Qrear=j; void traver1(Graph *GA) int i; for (i=0; i<GA->n;i+)

7、 visitedi=0; for (i=0; i<GA->n; i+) if (visitedi=0) bfs(GA, i); typedef struct NODE int adjvex; struct NODE *next; ENode;typedef struct NODE1 char vex2; ENode *first; VexNode;typedef struct FS1VexNode GLM;int bian,top;FS;FS *CreateGL( ) FS *kk=(FS *)malloc(sizeof(FS); int i,j,k; ENode *s; prin

8、tf("请输入顶点数和边数(用逗号隔开)：n"); scanf("%d,%d",&kk->top, &kk->bian); printf("请输入顶点信息：n"); for (i=0; i<kk->top; i+) scanf("%s",kk->GLi.vex); kk->GLi.first=NULL; printf("请输入边的信息(i,j)：n"); for (k=0;k<kk->bian;k+) scanf("n%d

9、,%d",&i,&j); s =(ENode*)malloc(sizeof(ENode); s->adjvex=j; s->next=kk->GLi.first; kk->GLi.first =s; return kk;void DFS(FS *kk, int v) ENode *w; int i; printf("%sn",kk->GLv.vex); visitedv=1; w=kk->GLv.first ; while (w!=NULL) i=w->adjvex; if (visitedi=0) DFS

10、(kk,i); w=w->next; void TRAVER(FS *kk) int i; for(i=0; i<kk->top;i+) visitedi=0; for(i=0; i<kk->top; i+) if(visitedi=0) DFS(kk, i); void BFS(FS *kk, int v) int QM, front=-1,rear=-1; ENode *w; int i, k; printf("%sn",kk->GLv.vex); visitedv=1; rear=rear+1; Qrear=v; while (fr

11、ont!=rear) front=front+1; k=Qfront; w=kk->GLk.first; while(w!=NULL) i=w->adjvex; if( visitedi=0) visitedi=1; printf("%s",kk->GLi.vex); rear=rear+1; Qrear=i; w=w->next; void TRAVER1(FS *kk) int i; for(i=0; i<kk->top;i+) visitedi=0; for(i=0; i <kk->top;i+) if(visitedi

12、=0) BFS(kk,i); int main() int i=0; Graph *p; FS *q; while(i=1) /*建立菜单*/char jz30="1.创建邻接矩阵"char jd30="2.邻接矩阵DFS遍历"char jb30="3.邻接矩阵BFS遍历"char bg30="4.创建邻接表"char bd30="5.邻接表DFS遍历"char bb30="6.邻接表BFS遍历"char tc30="7.退出"char mn30=&quo

13、t;菜单"int l=strlen(jd);int o=strlen(mn);int m,n;printf("n");for(m=0;m<=(2*l-o)/2;m+)printf(" ");printf("%s",mn);for(m=0;m<=(2*l-o)/2;m+)printf(" ");printf("n");for(m=0;m<=2*l;m+)printf("*");printf("n");printf("* %s *n* %s *n* %s *n* %s *n* %s *n* %s *n* %s *n",jz,jd,jb,bg,bd,bb,tc);for(m=0;m<=2*l;m+)printf("*");printf("n");/*选择功能*/printf("请输入所需功能序号：");scanf("%d",&n);switch(n) case 1: p=Create_Graph();break; case 2: traver(p);break; case 3: t