《数据结构》实验报告◎实验题目: 无向图的建立与遍历◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。

◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。

一、需求分析1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。

2.该无向图以深度、广度优先遍历输出。

3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。

4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束5.测试数据：顶点数和边数：6,5顶点信息：a b c d e f边的顶点对应序号：0,10,20,32,43,4深度优先遍历输出：a d e c bf广度优先遍历输出：a d cb ef二概要设计为了实现上述操作，应以邻接链表为存储结构。

1.基本操作：void createalgraph(algraph &g)创建无向图的邻接链表存储void dfstraverseal(algraph &g,int v)以深度优先遍历输出void bfstraverseal(algraph &g,int v) 以广度优先遍历输出2.本程序包含四个模块：（1）主程序模块（2）无向图的邻接链表存储模块（3）深度优先遍历输出模块（4）广度优先遍历输出模块3.模块调用图：三详细设计1.元素类型，结点类型和指针类型：typedef struct node{int adjvex;struct node *next;}edgenode;typedef struct vnode{char vertex;edgenode *firstedge;}vertxnode;typedef vertxnode Adjlist[maxvernum]; typedef struct{Adjlist adjlist;int n,e;}algraph;edgenode *s;edgenode *stack[maxvernum],*p;2.每个模块的分析：（1）主程序模块int main(){int v=0;algraph g;createalgraph(g);printf("以深度优先遍历输出\n");dfstraverseal(g,v);printf("以广度优先遍历输出\n");bfstraverseal(g,v);getchar();getchar();return 0;}（2）无向图的邻接链表存储模块void createalgraph(algraph &g){int i,j,k;edgenode *s;printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");scanf("%d,%d",&(g.n),&(g.e)); /*读入顶点数和边数*/getchar();printf("请输入顶点信息(输入格式为:(顶点号(CR))):\n");for(i=0;i<g.n;i++) /*建立有n个顶点的顶点表*/{scanf("%c",&(g.adjlist[i].vertex)); /*读入顶点信息*/getchar();g.adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/}printf("请输入边的信息(输入格式为:i,j):\n");for(k=0;k<g.e;k++) /*建立边表*/{scanf("%d,%d",&i,&j); /*读入边（vi,vj）的顶点对应序号*/s=(edgenode *)malloc(sizeof(edgenode)); /*生成新边表节点s*/s->adjvex=j; /*邻接点序号为j*/s->next=g.adjlist[i].firstedge; /*将新边表节点s插入到顶点vi的边表头部*/g.adjlist[i].firstedge=s;s=(edgenode *)malloc(sizeof(edgenode)); /*生成新边表节点s*/s->adjvex=i; /*邻接点序号为i*/s->next=g.adjlist[j].firstedge; /*将新边表节点s插入到顶点vj的边表头部*/g.adjlist[j].firstedge=s;}}（3）深度优先遍历输出模块{int j=0;edgenode *stack[maxvernum],*p;int visited[maxvernum],top=-1,i;for(i=0;i<g.n;i++)visited[i]=0;while(j!=g.n){i=0;while(visited[i]==1){i++;}v=i;printf("%c ",g.adjlist[v].vertex); /*访问图的指定起始顶点v*/j++;p=g.adjlist[v].firstedge;visited[v]=1;while(top>=0||p!=NULL){while(p!=NULL)if(visited[p->adjvex]==1)p=p->next;else{printf("%c ",g.adjlist[p->adjvex].vertex); /*从v出发访问一个与v邻接的p所指的顶点*/j++;visited[p->adjvex]=1;top++;stack[top]=p; /*将p所指的顶点入栈*/p=g.adjlist[p->adjvex].firstedge; /*从p所指顶点出发*/}if(top>=0){p=stack[top]; /*退栈，回溯查找已被访问节点的未被访问过的邻接点*/top--;p=p->next;}}printf("\n");}}（4）广度优先遍历输出模块{int i,front=-1,rear=-1,j=0;edgenode *p;for(i=0;i<g.n;i++)visited[i]=0;while(j!=g.n){i=0;while(visited[i]==1){i++;}v=i;visited[v]=1;printf("%c ",g.adjlist[v].vertex);j++;rear++;queue[rear]=v; /*初始顶点入队*/while(front!=rear) /*队列不为空*/{front=front+1;v=queue[front]; /*按访问次序出队列*/p=g.adjlist[v].firstedge; /*找v的邻接顶点*/while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%c ",g.adjlist[p->adjvex].vertex);j++;rear=rear+1;queue[rear]=p->adjvex;}p=p->next;}}printf("\n");}}3.函数调用图：4.完整的程序：（见源文件）。

四使用说明、测试分析及结果1．程序使用说明（1）本程序的运行环境为VC6.0。

（2）进入演示程序后即显示提示信息：请输入顶点数和边数(输入格式为:顶点数,边数): 请输入顶点信息(输入格式为:(顶点号(CR))):请输入边的信息(输入格式为:i,j):2.测试数据：顶点数和边数：6,5顶点信息：a b c d e f 边的顶点对应序号：0,10,20,32,43,4深度优先遍历输出：a d e c bf广度优先遍历输出：a d cb ef3.运行界面：五、实验总结本次程序由于书上有相关程序作为参考，所以编写起来比较顺手，通过本次编程，对于无向图的邻接链表存储有了一定的基础，同时还熟练掌握了无向图的深度、广度优先遍历输出，中间由于要存储无向不连通图，出了点小问题，在自己的努力下和同学的帮助下，完成了无向不连通图的存储与遍历输出。

通过本次试验对于无向图有了更深的了解，可以很好地掌握它的建立与遍历输出。

教师评语：#include<stdio.h>#include<malloc.h>#define maxvernum 100typedef struct node{int adjvex;struct node *next;}edgenode;typedef struct vnode{char vertex;edgenode *firstedge;}vertxnode;typedef vertxnode Adjlist[maxvernum];typedef struct{Adjlist adjlist;int n,e;}algraph;int visited[maxvernum];int queue[maxvernum];//创建无向图void createalgraph(algraph &g){int i,j,k;edgenode *s;printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");scanf("%d,%d",&(g.n),&(g.e)); /*读入顶点数和边数*/getchar();printf("请输入顶点信息(输入格式为:(顶点号(CR))):\n");for(i=0;i<g.n;i++) /*建立有n个顶点的顶点表*/{scanf("%c",&(g.adjlist[i].vertex)); /*读入顶点信息*/getchar();g.adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/}printf("请输入边的信息(输入格式为:i,j):\n");for(k=0;k<g.e;k++) /*建立边表*/{scanf("%d,%d",&i,&j); /*读入边（vi,vj）的顶点对应序号*/s=(edgenode *)malloc(sizeof(edgenode)); /*生成新边表节点s*/s->adjvex=j; /*邻接点序号为j*/s->next=g.adjlist[i].firstedge; /*将新边表节点s插入到顶点vi的边表头部*/g.adjlist[i].firstedge=s;s=(edgenode *)malloc(sizeof(edgenode)); /*生成新边表节点s*/s->adjvex=i; /*邻接点序号为i*/s->next=g.adjlist[j].firstedge; /*将新边表节点s插入到顶点vj的边表头部*/g.adjlist[j].firstedge=s;}}//深度优先void dfstraverseal(algraph &g,int v){int j=0;edgenode *stack[maxvernum],*p;int visited[maxvernum],top=-1,i;for(i=0;i<g.n;i++)visited[i]=0;{i=0;while(visited[i]==1){i++;}v=i;printf("%c ",g.adjlist[v].vertex); /*访问图的指定起始顶点v*/j++;p=g.adjlist[v].firstedge;visited[v]=1;while(top>=0||p!=NULL){while(p!=NULL)if(visited[p->adjvex]==1)p=p->next;else{printf("%c ",g.adjlist[p->adjvex].vertex); /*从v出发访问一个与v邻接的p所指的顶点*/j++;visited[p->adjvex]=1;top++;stack[top]=p; /*将p所指的顶点入栈*/p=g.adjlist[p->adjvex].firstedge; /*从p所指顶点出发*/}if(top>=0){p=stack[top]; /*退栈，回溯查找已被访问节点的未被访问过的邻接点*/top--;p=p->next;}}printf("\n");}}//广度优先void bfstraverseal(algraph &g,int v){int i,front=-1,rear=-1,j=0;edgenode *p;for(i=0;i<g.n;i++)visited[i]=0;{i=0;while(visited[i]==1){i++;}v=i;visited[v]=1;printf("%c ",g.adjlist[v].vertex);j++;rear++;queue[rear]=v; /*初始顶点入队*/while(front!=rear) /*队列不为空*/{front=front+1;v=queue[front]; /*按访问次序出队列*/p=g.adjlist[v].firstedge; /*找v的邻接顶点*/while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%c ",g.adjlist[p->adjvex].vertex);j++;rear=rear+1;queue[rear]=p->adjvex;}p=p->next;}}printf("\n");}}int main(){int v=0;algraph g;createalgraph(g);printf("以深度优先遍历输出\n");dfstraverseal(g,v);printf("以广度优先遍历输出\n");bfstraverseal(g,v);getchar();getchar();return 0; }。