数据结构实验报告无向图

◎实验题目: 无向图的建立与遍历

◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。

◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。

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

4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出 （3）以广度优先遍历输出（4）结束 5.测试数据：

a b c d f e

顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4

深度优先遍历输出： a d e c b f

广度优先遍历输出： a d c b e f

二 概要设计

为了实现上述操作，应以邻接链表为存储结构。 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\读入顶点数和边数*/ getchar();

printf(\"请输入顶点信息(输入格式为:(顶点号(CR))):\\n\");

for(i=0;iscanf(\"%c\读入顶点信息*/ getchar();

g.adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/ }

printf(\"请输入边的信息(输入格式为:i,j):\\n\"); for(k=0;kscanf(\"%d,%d\读入边（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）深度优先遍历输出模块

void dfstraverseal(algraph &g,int v) {

int j=0;

edgenode *stack[maxvernum],*p; int visited[maxvernum],top=-1,i; for(i=0;ii=0;

while(visited[i]==1) {

i++; }v=i;

printf(\"%c \访问图的指定起始顶点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 \从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）广度优先遍历输出模块

void bfstraverseal(algraph &g,int v) {

int i,front=-1,rear=-1,j=0; edgenode *p;

for(i=0;ii=0;

while(visited[i]==1) {

i++; } v=i;

visited[v]=1;

printf(\"%c \ 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 \ j++;

rear=rear+1;

queue[rear]=p->adjvex; }

p=p->next; } }

printf(\"\\n\"); } }

3.函数调用图：

int main() void void createalgraph(aldfstraverseal(agraph &g) lgraph &g,int v) 4.完整的程序：（见源文件）。 四 使用说明、测试分析及结果 1．程序使用说明

（1）本程序的运行环境为VC6.0。

（2）进入演示程序后即显示提示信息：

请输入顶点数和边数(输入格式为:顶点数,边数): 请输入顶点信息(输入格式为:(顶点号(CR))): 请输入边的信息(输入格式为:i,j): 2.测试数据：

a b c d e 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4

深度优先遍历输出： a d e c b f

广度优先遍历输出：

void bfstraverseal(algraph &g,int v) f

a d c b e f

3.运行界面：

五、实验总结

本次程序由于书上有相关程序作为参考，所以编写起来比较顺手，通过本次编程，对于无向图的邻接链表存储有了一定的基础，同时还熟练掌握了无向图的深度、广度优先遍历输出，中间由于要存储无向不连通图，出了点小问题，在自己的努力下和同学的帮助下，完成了无向不连通图的存储与遍历输出。通过本次试验对于无向图有了更深的了解，可以很好地掌握它的建立与遍历输出。 教师评语：

#include #include #define maxvernum 100 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;

int visited[maxvernum]; int queue[maxvernum]; //创建无向图

void createalgraph(algraph &g) {

int i,j,k; edgenode *s;

printf(\"请输入顶点数和边数(输入格式为:顶点数,边数):\\n\");

scanf(\"%d,%d\读入顶点数和边数*/ getchar();

printf(\"请输入顶点信息(输入格式为:(顶点号(CR))):\\n\"); for(i=0;iscanf(\"%c\读入顶点信息*/ getchar();

g.adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/ }

printf(\"请输入边的信息(输入格式为:i,j):\\n\"); for(k=0;kscanf(\"%d,%d\读入边（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;iwhile(j!=g.n) {

i=0;

while(visited[i]==1) {

i++; }v=i;

printf(\"%c \访问图的指定起始顶点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 \从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;iwhile(j!=g.n) {

i=0;

while(visited[i]==1) {

i++; } v=i;

visited[v]=1;

printf(\"%c \ 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 \ 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; }