当前位置：文档库 › 数据结构图的遍历

数据结构图的遍历

实验报告一

学号:

姓名:

完成日期:

[题目] 图的遍历

一.问题描述

从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。

图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。试编写一个程序，完成对图的遍历。

二.算法设计

2.1 设计思想

1．以邻接矩阵为存储结构，实现无向图的深度优先遍历和广度优先遍历。

2．分别输出每种遍历下的结点访问序列.从图中某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。2.1.1图的遍历介绍

2.1.2基本概念

图的遍历: 图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。

图的遍历是图运算中最重要的运算,也是图的基本运算之一,图的许多运算都是以遍历为基础的。

2..1.3 分类

按照搜索途径的不同，图的遍历可分为：深度优先遍历（Depth-First Traverse）和广度优先遍历（Breadth-First Traverse）两大类。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。

（1）深度优先遍历 (Depth-First Traverse)

特点：尽可能先对纵深方向的顶点进行访问

①．深度优先遍历的递归定义

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

②. 深度优先搜索的过程

a 基本思想:

首先访问图中某一个指定的出发点Vi；

然后任选一个与顶点Vi相邻的未被访问过的顶点Vj；

以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点均被访问过。

b具体过程:

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y 出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x

不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

(2)广度优先遍历（Breadth-First Traverse）:

特点：尽可能先从指定的出发点，横向地访问图中各个顶点。

①．广度优先遍历的定义

在访问了起始点之后,首先依次访问起始点的各个邻接点,然后依次访问那些顶点中未被访问过的邻接点.依此类推,直到所有被访问到的顶点的邻接点都被访问过为止.

②．广度优先搜索的过程

a算法基本思想：

首先访问图中某一指定的出发点Vi；

然后依次访问Vi的所有接点Vi1，Vi2…Vit；

再次访问Vi1，Vi2…，Vit的邻接点中未经访问过的顶点，依此类推，直到图中所有顶点均被访问为止。

b具体过程：

从广度优先搜索遍历方法可知，先被访问的顶点的邻接点也被访问，即假设顶点V在W 之前被访问，那么顶点V的所有未经访问的邻接点也在顶点W的所有未经访问的邻接点之前被访问。这样可以在广度优先遍历的算法中设置一个队列结构，用以保存已访问过的顶点的序号，访问该顶点的所有未经访问的顶点。

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样会出现回退的现象。因此它不是个递归的过程。为了实现逐层访问，算法中使用了一个队列以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为了避免重复访问，需要一个辅助函数visitvex[]给被访问过的顶点加标记。

2.2 概要设计

规格说明：

数据类型及函数定义

定义图

typedef struct{

int V[M];

int R[M][M];

int vexnum;

}Graph;

创建图

void creatgraph(Graph *g,int n) 打印图的邻接矩阵

void printgraph(Graph *g) 访问顶点

void visitvex(Graph *g,int vex) 深度递归遍历

void dfs(Graph *g,int vex) 队列的基本操作

定义队列

typedef struct{

int V[M];

int front;

int rear;

}Queue;

判断队列是否为空

quempty(Queue *q)

入队操作

enqueue(Queue *q,int e)

出队操作

dequeue(Queue *q)

广度遍历

void BESTraverse(Graph *g)

本程序包含四个模块：

主程序模块

void main ()

{构造一个图；

打印图的邻接矩阵

进行深度优先遍历图；

进行广度优先遍历图；}；

2.3 功能注释

本程序划分为三个不同的模块分别编译。其优点在于编译时如果有错误，只需要对出错的模块进行重新编译，无错的模块则不必再编译。因而可以明显地节约整个程序的编译调试时间。

用预处理命令#include可以包含有关文件的信息。#inlcude命令经过预处理命令（即在编译前进行的处理）后，会将其后有关文件的内容拷贝到命令所在的源程序文件中。该文件里包括常量的定义、结构的定义、函数原型的说明（即函数的返回类型、函数名以及函数参数类型的说明）等

2.4 详细设计

算法思想

算法一：

存在的问题：图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点解决办法:

为了避免重复访问，可设置一个标志顶点是否被访问过的辅助标志visitvex

辅助数组visitvex 的初始状态为0，在图的遍历过程中，一旦此顶点被访问，就立刻让visitvex为1，防止它被多次访问

Visitevex[0．．n-1]的设置：

图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visitvex[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visitvex[i]置为真。算法二：以邻接矩阵为存储结构的图的深度优先搜索遍历的算法

void dfs(Graph *g,int vex)

{ int w;

visited[vex]=1; 标记vex已被访问过

visitvex(g,vex); 访问图g的顶点

for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))

if(!visited[w])

{ dfs(g,w); } }

从初始点vex出发广度优先搜索由邻接矩阵R表示的图

void dfstraverse(Graph *g)

{ int i;

for(i=1;i<=g->vexnum;i++)

visited[i]=0;

for(i=1;i<=g->vexnum;i++)

if(!visited[i])

{dfs(g,i);} }

算法三：以邻接矩阵为存储结构的图的广度优先搜索遍历的算法

从初始点vex出发广度优先搜索由邻接矩阵R表示的图

void BESTraverse(Graph *g)

{ int i;

Queue *q=(Queue *)malloc(sizeof(Queue)); 定义一个队列q，其元素类型应为Queue型

for(i=1;i<=g->vexnum;i++)

{ visited[i]=0; 标记初始点i未被已访问过}

initqueue(q); 初始化队列

for(i=1;i<=g->vexnum;i++)

{ if(!visited[i])

{ visited[i]=1; 标记初始点i已访问过

visitvex(g,g->V[i]); 访问顶点i

enqueue(q,g->V[i]); 将已访问过的初始点序号i入队

while(!quempty(q)) 当队列非空时进行循环处理

{依次搜索i的每一个可能的邻接点

int u,w;

u=dequeue(q);

for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))

{ if(!visited[w])

{ visited[w]=1; 访问一个未被访问过的邻接点

visitvex(g,w); 访问顶点w

enqueue(q,w); 顶点w出队}}}} } }

三.用户手册:

3.1运行环境

本程序在windows环境下的Visual C++ 6.0的编译环境下执行。

3.2执行文件

四.测试数据及结果分析

4.1.1调试过程中遇到的问题以及对设计与实现的回顾讨论和分析：

一个图的DFS序列不一定惟一:当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之；源点和存储结构的内容均已确定的图的DFS序列惟一；邻接矩阵表示的图确定源点后，DFS序列惟一；DFS算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。

4.2运行结果

五.调试报告:

上机实验是对我们的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个环节。通常，我们在上机实验中遇到的问题比平时的习题复杂得多，也更接近实际,所以能从很大程度上提高我们的综合能力。一方面，实验着眼于原理与应用的结合点，使我们学会如何把书上学到的知识用于解决实际的问题，从而培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握课堂上所讲授的内容的目的。通过这一次的课程设计，我们同学之间相互交流了许多的专业知识，在查阅文献资料时不知不觉中就学习到许多专业方面的知识，让我们学习到的知识得到了实践，而且同学之间的相互合作能力也得到加强。

同时明白到在往后的学习当中，当编译程序遇到了错误的时候，不能慌乱，要认真阅读

程序，找出错误，当错误无法排除的时候，要查阅各种文献，对于我们的程序调试有很大的

帮助。

附录:

#include

#define INF 32767 /*INF表示∞*/

typedef int InfoType;

#define MAXV 100 /*最大顶点个数*/

#define MAXQUEUE 10 /* 队列的最大容量*/

struct node /* 图的顶点结构定义*/

{ int vertex; struct node *nextnode;};

typedef struct node *graph; /* 图的结构指针*/

struct node head[9]; /* 图的顶点数组*/

int visit[9]; /* 遍历标记数组*/

int queue[MAXQUEUE]; /* 定义序列数组*/

int front = -1; /* 序列前端*/

int rear = -1; /* 序列后端*/

/***********************二维数组向邻接表的转化****************************/ void creategraph(int node[20][2],int num)

{ graph newnode; /* 顶点指针*/

graph ptr;

int from; /* 边起点*/

int to; /* 边终点*/

int i;

for ( i = 0; i < num; i++ ) /* 第i条边的信息处理*/

{from = node[i][0]; /* 边的起点*/

to = node[i][1]; /* 边的终点*/

/* 建立新顶点*/

newnode = ( graph ) malloc(sizeof(struct node));

newnode->vertex = to; /* 顶点内容*/

newnode->nextnode = NULL; /* 设定指针初值*/

ptr = &(head[from]); /* 顶点位置*/

while ( ptr->nextnode != NULL ) /* 遍历至链表尾*/

ptr = ptr->nextnode; /* 下一个顶点*/ ptr->nextnode = newnode; /* 插入第i个节点的链表尾部*/ }}

/************************ 数值入队列************************************/

int enqueue(int value)

{if ( rear >= MAXQUEUE ) /* 检查伫列是否全满*/ return -1; /* 无法存入*/ rear++; /* 后端指标往前移*/

queue[rear] = value; /* 存入伫列*/

return 0;}

/************************* 数值出队列*********************************/

int dequeue(){if ( front == rear ) /* 队列是否为空*/ return -1; /* 为空，无法取出*/ front++; /* 前端指标往前移*/

return queue[front]; /* 从队列中取出信息*/}

/*********************** 图形的广度优先遍历************************/

void bfs(int current)

{graph ptr;

/* 处理第一个顶点*/

enqueue(current); /* 将顶点存入队列*/

visit[current] = 1; /* 已遍历过记录标志置疑1*/

printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值*/

while ( front != rear ) /* 队列是否为空*/

{current = dequeue(); /* 将顶点从队列列取出*/

ptr = head[current].nextnode; /* 顶点位置*/

while ( ptr != NULL ) /* 遍历至链表尾*/

{ if ( visit[ptr->vertex] == 0 ) /*顶点没有遍历过*/

{ enqueue(ptr->vertex); /* 将定点放入队列*/

visit[ptr->vertex] = 1; /* 置遍历标记为1 */

printf(" Vertex[%d]\n",ptr->vertex);/* 印出遍历顶点值*/}

ptr = ptr->nextnode; /* 下一个顶点*/} } }

/*以下定义邻接矩阵类型*/

typedef struct { int no; /*顶点编号*/

InfoType info; /*顶点其他信息*/} VertexType; /*顶点类型*/ typedef struct /*图的定义*/

{ int edges[MAXV][MAXV]; /*邻接矩阵*/

int vexnum,arcnum; /*顶点数，弧数*/

VertexType vexs[MAXV]; /*存放顶点信息*/} MGraph; /*图的邻接矩阵类型*/ /*以下定义邻接表类型*/

typedef struct ANode /*弧的结点结构类型*/

{ int adjvex; /*该弧的终点位置*/

struct ANode *nextarc; /*指向下一条弧的指针*/

InfoType info; /*该弧的相关信息,这里用于存放权值*/} ArcNode;

typedef int Vertex;

typedef struct Vnode /*邻接表头结点的类型*/

{ Vertex data; /*顶点信息*/

ArcNode *firstarc; /*指向第一条弧*/

} VNode;

typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/

typedef struct

{ AdjList adjlist; /*邻接表*/

int n,e; /*图中顶点数n和边数e*/

} ALGraph; /*图的邻接表类型*/

int visited[MAXV];

void MatToList(MGraph g,ALGraph *&G)

/*将邻接矩阵g转换成邻接表G*/

{int i,j,n=g.vexnum; /*n为顶点数*/

ArcNode *p;

G=(ALGraph *)malloc(sizeof(ALGraph));

for (i=0;i

G->adjlist[i].firstarc=NULL;

for (i=0;i

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=INF) /*邻接矩阵的当前元素不为0*/

{ p=(ArcNode *)malloc(sizeof(ArcNode)); /*创建一个结点*p*/

p->adjvex=j;

p->info=g.edges[i][j];

p->nextarc=G->adjlist[i].firstarc;

G->adjlist[i].firstarc=p;}

G->n=n;G->e=g.arcnum;}

void ListToMat(ALGraph *G,MGraph &g)/*将邻接表G转换成邻接矩阵g*/{ int i,j,n=G->n;

ArcNode *p;

for (i=0;i

for (j=0;j

g.edges[i][j]=INF;

for (i=0;iadjlist[i].firstarc;

while(p!=NULL){

g.edges[i][p->adjvex]=p->info;

p=p->nextarc;}}g.vexnum=n;g.arcnum=G->e;}

void DispMat(MGraph g)/*输出邻接矩阵g*/

{int i,j; for (i=0;i

for (j=0;j

if (g.edges[i][j]==INF)

printf("%3s","∞");else printf("%3d",g.edges[i][j]); printf("\n");}}

void DispAdj(ALGraph *G)

/*输出邻接表G*/

{int i;

ArcNode *p;

for (i=0;in;i++){p=G->adjlist[i].firstarc;

if (p!=NULL) printf("%3d: ",i);

while(p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}

printf("\n");}}

void DFS(ALGraph *G,int v)

{ArcNode *p;visited[v]=1; /*置已访问标记*/

printf("%3d",v); /*输出被访问顶点的编号*/

p=G->adjlist[v].firstarc; /*p指向顶点v的第一条弧的弧头结点*/while (p!=NULL) { if (visited[p->adjvex]==0) /*若p->adjvex顶点未访问,递归访问它*/

DFS(G,p->adjvex); p=p->nextarc; /*p指向顶点v的下一条弧的弧头结点*/}}

void DFS1(ALGraph *G,int v)

{int i,visited[MAXV],St[MAXV],top=-1;

ArcNode *p;

for (i=0;in;i++)

visited[i]=0; /*结点访问标志均置成0*/

printf("%3d",v); /*访问顶点v*/

top++; /*v入栈*/

St[top]=v;

visited[v]=1;

while (top>=-1) /*栈不空时循环*/

{v=St[top];top--; /*取栈顶顶点*/

p=G->adjlist[v].firstarc;

while (p!=NULL && visited[p->adjvex]==1)

p=p->nextarc; if (p==NULL) /*若没有退到前一个*/ top--;

else /*若有,选择一个*/

{v=p->adjvex;

printf("%3d",v); /*访问顶点*/

visited[v]=1;

top++; /*入栈*/

St[top]=v;}}

printf("\n");}

void main()

{int i,j;

MGraph g,g1;

ALGraph *G;

graph ptr;

/* 边信息数组*/

int node[20][2] = { {1, 2}, {2, 1}, {6, 3}, {3, 6},{2, 4}, {4, 2}; {1, 5}, {5, 1}, {3, 7}, {7, 3},{1, 7}, {7, 1},{4, 8},

{8, 4},{5, 8}, {8, 5},{2, 8}, {8, 2},{7, 8}, {8, 7} };

int

A[MAXV][6]={{INF,5,INF,7,INF,INF},{INF,INF,4,INF,INF,INF},{8,INF,INF,INF,INF,9},{INF,INF,5,INF,I NF,6},{INF,INF,INF,5,INF,INF},{3,INF,INF,INF,1,INF}};

g.vexnum=6;g.arcnum=10;

puts("This is an example of Width Preferred Traverse of Gragh.\n");

for ( i = 1; i <= 8; i++ ) /*顶点结构数组初始化*/

{head[i].vertex = i;head[i].nextnode = NULL; visit[i] = 0; }

creategraph(node,20); /* 图信息转换，邻接表的建立*/

printf("The content of the graph's allist is:\n");

for ( i = 1; i <= 8; i++ )

{printf(" vertex%d =>",head[i].vertex); /* 顶点值*/

ptr = head[i].nextnode; /* 顶点位置*/

while ( ptr != NULL ) /* 遍历至链表尾*/

{ printf(" %d ",ptr->vertex); /* 打印输出顶点内容*/

ptr = ptr->nextnode; /* 下一个顶点*/ }

printf("\n"); /* 换行*/}

printf("The contents of BFS are:\n");

bfs(1); /* 打印输出遍历过程*/ printf("\n"); /* 换行*/

puts(" Press any key to quit..."); getch();

for (i=0;i

for (j=0;j

g.edges[i][j]=A[i][j];

printf("\n"); printf(" 有向图G的邻接矩阵:\n");

DispMat(g);

G=(ALGraph *)malloc(sizeof(ALGraph));

printf(" 图G的邻接矩阵转换成邻接表:\n");

MatToList(g,G); printf("图G的邻接表:\n");

DispAdj(G); printf(" 图G的邻接表转换成邻接邻阵:\n");

ListToMat(G,g1); DispMat(g1); printf("\n");

printf("从顶点0开始的DFS(递归算法):\n");

DFS(G,0);printf("\n");

printf("从顶点0开始的DFS(非递归算法):\n");

DFS1(G,0);printf("\n");}

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 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１18064０33 班级网络1101班成绩指导教师申静数学与计算机科学学院 2０14年1 月4日

课程设计任务书 2013—２０14学年第一学期课程设计名称:数据结构课程设计课程设计题目:图的遍历实现完成期限：自2013年1２月23日至2014年１月4日共 2 周设计内容： 1. 任务说明 (1）采用邻接表存储结构创建一个图； (２）编程实现图的深度优先搜索(或广度优先搜索)遍历算法; (3) 输出遍历结果； (4) 给定具体数据调试程序。２．要求１）问题分析和任务定义：根据设计题目的要求,充分地分析和理解问题，明确问题要求做什么? 2)逻辑设计：写出抽象数据类型的定义，各个主要模块的算法,并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7)编写课程设计报告。 3. 参考资料指导教师:申静教研室负责人：余冬梅课程设计评阅

摘要针对图问题中如何更好地实现图的遍历问题，以无向图为例,分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以ＶＣ++为开发环境进行系统的设计和实现,其运行结果表明，系统能很好地完成遍历后节点的输出,实现了遍历的目的，系统界面友好,可操作性强。关键词：数据结构;存储结构；邻接矩阵

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

数据结构实验报告实验：图的遍历一、实验目的： 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;

数据结构C语言版无向图的邻接多重表存储表示和实现

数据结构C语言版无向图的邻接多重表存储表示和实现.txt只要你要，只要我有，你还外边转什么阿老实在我身边待着就行了。听我的就是,问那么多干嘛，我在你身边,你还走错路!跟着我!不能给你幸福是我的错，但谁让你不幸福，我TMD去砍了他/* 数据结构C语言版无向图的邻接多重表存储表示和实现 P166 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月15日 */ #include #include #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 80 // 相关信息字符串的最大长度+1 typedef char InfoType; typedef char VertexType[MAX_NAME]; // 字符串类型 // AMLGraph.h 无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef enum{unvisited,visited}VisitIf; typedef struct EBox { VisitIf mark; // 访问标记 int ivex,jvex; // 该边依附的两个顶点的位置 struct EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边 InfoType *info; // 该边信息指针 }EBox; typedef struct { VertexType data; EBox *firstedge; // 指向第一条依附该顶点的边 }VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum,edgenum; // 无向图的当前顶点数和边数 }AMLGraph; typedef int QElemType;

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

学号：姓名：实验日期： 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;

数据结构图的遍历

#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);}

数据结构课程设计-图的遍历和构建

图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

第一章课程设计目的 (3) 第二章课程设计内容和要求 (3) 2.1课程设计内容 (3) 2.1.1图的邻接矩阵的建立与输出 (3) 2.1.2图的邻接表的建立与输出 (3) 2.1.3图的遍历的实现 (4) 2.1.4 图的顶点的度 (4) 2.2 运行环境 (4) 第三章课程设计分析 (4) 3.1图的存储 (4) 3.1.1 图的邻接矩阵存储表示 (4) 3.1.2 图的邻接表存储表示 (5) 3.2 图的遍历 (5) 3.2.1 图的深度优先遍历 (5) 3.2.2 图的广度优先遍历 (6) 3.3图的顶点的度 (7) 第四章算法（数据结构）描述 (7) 4.1 图的存储结构的建立。 (7) 4.1.1 定义邻接矩阵的定义类型 (7) 4.1.2定义邻接表的边结点类型以及邻接表类型 (7) 4.1.3初始化图的邻接矩阵 (8) 4.1.4 初始化图的邻接表 (8) 4.2 图的遍历 (8) 4.2.1 深度优先遍历图 (8) 4.2.2 广度优先遍历图 (9) 4.3 main函数 (9) 4.4 图的大致流程表 (10) 第五章源代码 (10) 第六章测试结果 (20) 第七章思想总结 (21) 第八章参考文献 (22)

数据结构实验四：无向图的应用

《数据结构》实验报告 1 2 实验题目：第四次实验《无向图的应用》 3 姓名：刘创学号：132054137 班级：1320541 4 系名：计算机工程系专业：计算机科学与技术5 指导老师：刘海静 6 实验时间：2015年6月18日星期四实验地点：软件实验室【实验概述】 1.实验目的及要求目的：掌握图的有关知识要求：用图的邻接表存储无向图；实现图的遍历等操作 2.实验原理图的遍历图的存储 3.实验环境（使用的软件） VC++6.0/VS2013 【实验内容】 1.实验算法设计实验：存储图使用图的邻接表进行存储；用深度优先排序进行遍历图 2.实验过程（源代码及描述、调试过程及分析）调试过程中，两个实验没有出现太大的问题，理论联系实际，多时间去实践方可等心应手。实验代码: GraphTraverse.cpp #include #include typedef char InfoType; typedef char VertexType;

#define MaxVertexNum 40 //最大顶点数 using namespace std; typedef struct node //表结点 { int adjvertex; //邻接点域 InfoType info; //与边相关信息（权值） struct node *next; //指向下一个领节点的指针域 }EdgeNode; typedef struct vnode { VertexType vertex; //顶点域信息 EdgeNode *firstedge; //边表头指针 }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum];//邻接表 int vertexNum, edgeNum;//顶点数和边数 }ALGraph; //以邻接表存储的图 int visited[MaxVertexNum]; int e; void CreatAdjList(ALGraph* G) //创建无向图（邻接表） { int i, j, k; EdgeNode * p1; //因为是无向图，所以有两次建立边表的过程EdgeNode * p2; EdgeNode * p3; EdgeNode * p4; cout << "请输入无向图的顶点数和边数:";

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 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