当前位置：文档库 › 图的遍历数据结构实验研究报告

图的遍历数据结构实验研究报告

南昌航空大学实验报告

课程名称：数据结构实验名称：实验八图地遍历

班级：学生姓名：学号：

指导教师评定：签名:

题目：假设无向图采用邻接表结构表示.编程分别实现图地深度优先搜索算法和广度优先搜索算法.

一、需求分析

1.用户可以根据自己地需求分别输入任意地一个有向图（可以是非连通图也可以是连通

图）.

2.通过用广度优先遍历和深度优先遍历已有地图，并输出.

3.并且以邻接表地形式输出该已有地图.

4.程序执行地命令包括：

（1）输入图地结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图

二、概要设计

⒈为实现上述算法，需要链表地抽象数据类型：

ADT Graph {

数据对象V：V是具有相同特征地数据元素地集合，称为顶点集.

数据关系R：

R={VR}

VR={|v,w∈V且P（v,w），表示从x到w地弧，谓词P（v,w）定义了弧

地意义或信息 }b5E2R。

基本操作P:

Creatgraph(&G,V,VR)

初始条件：V是图地顶点集，VR是图中弧地集合.

操作结果：按V和VR地定义构造图G.

destroygraph(&G)

初始条件：图G存在.

操作结果：销毁图G.

displaygraph（G）

初始条件：图G存在.

操作结果：显示图G.

locatevex(G,u)

初始条件：图G存在，u和G中地顶点有相同地特征.

操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回

其他信息.

getvex(G,v)

初始条件：图G存在，v是G中地某个顶点.

操作结果：返回v地值.

DFStraverse (G)

初始条件：图G存在.

操作结果：对图进行深度优先遍历.在遍历过程中对每个顶点访问一

次.

BFStraverse (&S,e)

初始条件：图G存在.

操作结果：对图进行广度优先遍历.在遍历过程中对每个顶点访问一

次.

}ADT Graph

2. 本程序有三个模块：

⑴主程序模块

main(){

初始化；

{

接受命令；

显示结果；

｝

⑵创建图地模块：主要建立一个图；

⑶广度优先遍历和深度优先遍历模块：输出这两种遍历地结果；

(4)输出图模块：显示已创建地图.

三、详细设计

⒈元素类型，结点类型

struct arcnode

{ int adjvex; /*该弧所指向地顶点地位置*/

int info;

struct arcnode *nextarc; /*指向下一条弧地指针*/

};

struct vexnode

{ int data; /*顶点地信息*/

struct arcnode *firstarc; /*指向第一条依附该顶点地弧地指针*/

};

struct graph

{ struct vexnode *vexpex;

int vexnum,arcnum; /*图地当前地顶点数和弧数*/

}；

/*定义队列*/

struct queue

{

int *elem;

int front;

int rear;

};

/*全局变量*/

int n; /*图地顶点数*/

int visit[100]; /*标志数组*/

struct queue Q;

2.对抽象数据类型中地部分基本操作地伪码算法如下：/*创建一个空队列*/

struct queue initqueue()

{ struct queue q;

q.elem=(int *)malloc(maxsize*sizeof(int)); if(!q.elem) exit(0);

q.front=q.rear=0;

return q;

}

/*入队列*/

struct queue enqueue(struct queue q,int v ) { if((q.rear+1)%maxsize==q.front)

printf("the queue is full！！！\n");

else

{ q.elem[q.rear]=v;

q.rear=(q.rear+1)%maxsize;

}

return q;

}

/*出队列*/

int dequeue(struct queue q)

{ int cur;

if(q.rear==q.front)

{ printf("the queue is null!!\n");

exit(0);

}

else

{ cur=q.elem[q.front];

q.front=(q.front+1)%maxsize;

return cur;

}

/*判断队列是否为空*/

int emptyqueue(struct queue q)

{ if(q.front==q.rear)

return 1;

else

return 0;

}

/*创建有向图*/

struct graph creatgraph()

{ int e,i,s,d;

int a;

struct graph g;

struct arcnode *p;

printf("the number of vex(n) and arc(e):");

scanf("%d%d",&n,&e);

g.vexnum=n;

g.arcnum=e;

for(i=0;i

{ printf("di %d vex's information:",i);

scanf("%d",&a);

g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;

}

for(i=0;i

{ printf("di %d arc's start,end:",i+1);

scanf("%d%d",&s,&d);

p=(struct arcnode *)malloc(sizeof(struct arcnode));p1Ean。 p->adjvex=d;

p->info=g.vexpex[d].data;

p->nextarc=g.vexpex[s].firstarc;

g.vexpex[s].firstarc=p;

}

return g;

}

/*显示有向图*/

void displaygraph(struct graph g,int n)

{ int i;

struct arcnode *p;

printf("diaplay the graph;\n");

for(i=0;i

{ printf(" [%d,%d]->",i,g.vexpex[i].data);

p=g.vexpex[i].firstarc;

while(p!=NULL)

{ printf("(%d,%d)->",p->adjvex,p->info);

p=p->nextarc;

}

printf("^\n");

}

/*连通图广度优先遍历*/

void BFSsearch(struct graph g,int v) { int i;

struct arcnode *p;

Q=initqueue();

printf("%5d",g.vexpex[v].data);

enqueue(Q,v); visit[v]=TURE;

while(!emptyqueue(Q))

{ i=dequeue(Q);

p=g.vexpex[i].firstarc;

while(p!=NULL)

{ enqueue(Q,p->adjvex);

if(visit[p->adjvex]==FALSE) {

printf("%5d",p->info); visit[p->adjvex]=TURE; }

p=p->nextarc;

}

/*非连通图广度优先遍历*/

void BFS(struct graph g)

{ int i;

for(i=0;i

visit[i]=FALSE;

for(i=0;i

if(visit[i]==FALSE)

BFSsearch(g,i);

printf("\n\n");

}

/*连通图深度优先遍历*/

void DFSsearch(struct graph g,int v)

{ struct arcnode *p;

printf("%5d",g.vexpex[v].data); visit[v]=TURE;

p=g.vexpex[v].firstarc;

while(p!=NULL)

{ if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc;

}

/*非连通图深度优先遍历*/

void DFS(struct graph g)

{ int i;

for(i=0;i

if(visit[i]==FALSE)DFSsearch(g,i);

printf("\n\n");

}

3.主函数和其他函数地伪码算法

int main(void)

{ struct graph g;

int i;

g=creatgraph();

displaygraph(g,n);

printf("BFS result:\n");

BFS(g);

printf("DFS result:\n");

DFS(g);

getch();

return 1;

}4 函数调用关系

main

creatgraphdisplaygraphBFSDFS

BFSsearchDFSsearch

initqueuedequeueenqueue

四、调试分析

⒈本来想将图地顶点元素地类型定义为字符型地，但是在运行地时候发现在输入顶点数和弧

数后，总是会在有字符没有输入就直接运行下一个语句了，改变了很多地方法，最后只有将顶点地类型定义为才解决了上述地问题.DXDiT。

⒉在写程序地时候，开始creatgraph函数地部分代码为

for(i=0;i

{ printf("di %d vex's information:",i);

scanf("%d",&a);

g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;

}

g.vexnum=n;g.arcnum=e;

总是会有这样地提示“可能在‘g’定义以前已经使用了在creatgraph函数中”，经过多次地调试，最后代码改为RTCrp。

g.vexnum=n;g.arcnum=e;

for(i=0;i

{ printf("di %d vex's information:",i);

scanf("%d",&a);

g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;

}

就解决了问题，但是我还是不清楚原因.

3.在编写BFSsearch函数地时候，用指针入队还是用下标值入队，由于对指针地掌握不够，最后选择了比较容易地用下标值作为队列地类型int.5PCzV。

4.算法地时空分析

各操作地算法时间复杂度比较合理

initqueue，emptyqueue，enqueue，dequeue，visit为O(1)；creatgraph ，displaygraph，BFSsearch，DFS，DFSsearch，BFS为O(n),jLBHr。

注：n为图地顶点数.

5.本次实验采用数据抽象地程序设计方法，将程序化为三层次结构，设计时思路清晰，使

调试也较顺利，各模块有较好地可重用性.xHAQX。

五、用户手册

⒈本程序地运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp8.c；

LDAYt。

⒉.在输入图地信息地时候，注意输入地顺序，这关系到顶点地位置，否则就会与你想要地

图就不一样了.如你地图为 18Zzz6Z。

20 21

若你输入地顶点地顺序是20,18 21，则它们对应地数值地下标为0,1,2.因此表示地弧（起

点，终点）就应该为（0,2），（1,0），（2,1），但是弧输入地顺序没有要求.dvzfv。

3. 进入演示程序后，完成编译，再点击超级工具集里地中文DOS环境运行选项，进入DOS

环境中，用户根据需求键入相应地数据，可以看到相应地结果.rqyn1。

六、测试结果

若想创建图：17 18

10 14 19 20

15 13

则因在dos界面输入如图所示：

所以在win tc中运行得到地结果如下图所示：

运行地结果是：显示地邻接表为

[0,17]->(1,10)

[1,10]->(3,15)

[2,14]->(1,10)->(0,17)

[3,15]->(4,13)

[4,13]->(2,14)

[5,18]->(7,20)->(6,19)

[6,19]

[7,20]->(6,19)

广度优先遍历地结果为17,10,14,15,13,18,19,20

深度优先遍历地结果为17,10,15,13,14,18,20,19

七、附录：源程序

#include

#define NULL 0

#define FALSE 0

#define TURE 1

#define maxsize 100

struct arcnode

{ int adjvex; /*该弧所指向地顶点地位置*/

int info;

struct arcnode *nextarc; /*指向下一条弧地指针*/

};

struct vexnode

{ int data; /*顶点地信息*/

struct arcnode *firstarc; /*指向第一条依附该顶点地弧地指针*/ };

struct graph

{ struct vexnode *vexpex;

int vexnum,arcnum; /*图地当前地顶点数和弧数*/

};

/*定义队列*/

struct queue

{

int *elem;

int front;

int rear;

};

int n; /*图地顶点数*/

int visit[100]; /*标志数组*/

struct queue Q;

/*创建一个空队列*/

struct queue initqueue()

{ struct queue q;

q.elem=(int *)malloc(maxsize*sizeof(int));

if(!q.elem) exit(0);

q.front=q.rear=0;

return q;

}

/*入队列*/

struct queue enqueue(struct queue q,int v )

{ if((q.rear+1)%maxsize==q.front)

printf("the queue is full！！！\n");

else

{ q.elem[q.rear]=v;

q.rear=(q.rear+1)%maxsize;

}

return q;

}

/*出队列*/

int dequeue(struct queue q)

{ int cur;

if(q.rear==q.front)

{ printf("the queue is null!!\n");

exit(0);

}

else

{ cur=q.elem[q.front];

q.front=(q.front+1)%maxsize;

return cur;

}

/*判断队列是否为空*/

int emptyqueue(struct queue q)

{ if(q.front==q.rear)

return 1;

else

return 0;

}

/*创建有向图*/

struct graph creatgraph()

{ int e,i,s,d;

int a;

struct graph g;

struct arcnode *p;

printf("the number of vex(n) and arc(e):"); scanf("%d%d",&n,&e);

g.vexnum=n;

g.arcnum=e;

for(i=0;i

{ printf("di %d vex's information:",i); scanf("%d",&a);

g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;

}

for(i=0;i

{ printf("di %d arc's start,end:",i+1); scanf("%d%d",&s,&d);

p=(struct arcnode *)malloc(sizeof(struct arcnode));Emxvx。 p->adjvex=d;

p->info=g.vexpex[d].data;

p->nextarc=g.vexpex[s].firstarc;

g.vexpex[s].firstarc=p;

}

return g;

}

/*显示有向图*/

void displaygraph(struct graph g,int n)

{ int i;

struct arcnode *p;

printf("diaplay the graph;\n");

for(i=0;i

{ printf(" [%d,%d]->",i,g.vexpex[i].data);

p=g.vexpex[i].firstarc;

while(p!=NULL)

{ printf("(%d,%d)->",p->adjvex,p->info);

p=p->nextarc;

}

printf("^\n");

}

/*连通图广度优先遍历*/

void BFSsearch(struct graph g,int v)

{ int i;

struct arcnode *p;

Q=initqueue();

printf("%5d",g.vexpex[v].data);

enqueue(Q,v); visit[v]=TURE;

while(!emptyqueue(Q))

{ i=dequeue(Q);

p=g.vexpex[i].firstarc;

while(p!=NULL)

{ enqueue(Q,p->adjvex);

if(visit[p->adjvex]==FALSE)

{

printf("%5d",p->info);

visit[p->adjvex]=TURE;

}

p=p->nextarc;

}

/*非连通图广度优先遍历*/

void BFS(struct graph g)

{ int i;

for(i=0;i

visit[i]=FALSE;

for(i=0;i

if(visit[i]==FALSE)

BFSsearch(g,i);

printf("\n\n");

}

/*连通图深度优先遍历*/

void DFSsearch(struct graph g,int v)

{ struct arcnode *p;

printf("%5d",g.vexpex[v].data); visit[v]=TURE;

p=g.vexpex[v].firstarc;

while(p!=NULL)

{ if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc;

}

/*非连通图深度优先遍历*/

void DFS(struct graph g)

{ int i;

for(i=0;i

visit[i]=FALSE;

for(i=0;i

if(visit[i]==FALSE)

DFSsearch(g,i);

printf("\n\n");

}

/*主函数*/

int main(void)

{ struct graph g;

int i;

g=creatgraph();

displaygraph(g,n);

printf("BFS result:\n");

BFS(g);

printf("DFS result:\n");

DFS(g);

getch();

return 1;

}

版权申明

本文部分内容，包括文字、图片、以及设计等在网上搜集整理.

版权为个人所有

This article includes some parts, including text, pictures, and design. Copyright is personal ownership.SixE2。

用户可将本文地内容或服务用于个人学习、研究或欣赏，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律地规定，不得侵犯本网站及相关权利人地合法权利.除此以外，将本

文任何内容或服务用于其他用途时，须征得本人及相关权利人地书面许可，并支付报酬.6ewMy。

Users may use the contents or services of this article for personal study, research or appreciation, and other

non-commercial or non-profit purposes, but at the same time, they shall abide by the provisions of copyright law and other relevant laws, and shall not infringe upon the legitimate rights of this website and its relevant obligees. In addition, when any content or service of this article is used for other purposes, written permission and remuneration shall be obtained from the person concerned and the relevant obligee.kavU4。

转载或引用本文内容必须是以新闻性或资料性公共免费信息为

使用目地地合理、善意引用，不得对本文内容原意进行曲解、修改，并自负版权等法律责任.y6v3A。

Reproduction or quotation of the content of this article must be reasonable and good-faith citation for the use of news or informative public free information. It shall not misinterpret or modify the original intention of the content of this article, and shall bear legal liability such as copyright.M2ub6。

图的遍历操作实验报告

. .. . .. .. 实验三、图的遍历操作一、目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。三、DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、示例程序 1．邻接矩阵作为存储结构的程序示例

#include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;in;i++) { scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 }

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

(完整版)数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简单程序 1 ．实验目的（1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法；（2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求（1 ）认真阅读和掌握和本实验相关的教材内容。（2 ）认真阅读和掌握本章相关内容的程序。（3 ）上机运行程序。（4 ）保存和打印出程序的运行结果，并结合程序进行分析。（5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告-图的遍历

数据结构实验报告实验：图的遍历一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

图的遍历实验报告

实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R={VR} VR={ | v，w v且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义或信息} } ADT Graph 2.此抽象数据类型中的一些常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define max_n 20 //最大顶点数 typedef char VertexType[20]; typedef enum{DG, DN, AG, AN} GraphKind; enum BOOL{False,True}; 3.树的结构体类型如下所示：

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 2016.1.7 实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：在此贴上调试好的程序。 #include #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构图的遍历实验报告

实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。二、实验容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。三、实验仪器与设备计算机，Code::Blocks。四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue