实验四 图的遍历算法

实验四图的遍历算法

4.1.实验的问题与要求

1.如何对给定图的每个顶点各做一次且仅做一次访问？有哪些方法可以实

现图的遍历？

2.如何用这些算法解决实际问题？

3.熟练掌握图的基本存储方法

4.熟练掌握图的两种搜索路径的遍历方法

5.掌握有关图的操作算法并用高级语言实现

4.2.实验的基本思想和基本原理

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。遍历常用两种方法：深度优先搜索遍历；广度优先搜索遍历

4.2.1 深度优先搜索（Depth-First Traversal）

深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。

1.图的深度优先遍历的递归定义

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

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

2.深度优先搜索的过程

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发

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

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

算法思路 :

(1)、首先访问一个顶点vi(初始点),将其标记为已访问过(因为图的每个顶

点可能有多个前驱和后继，所以当一个顶点被访问以后，必须记录它已经被访问，以避免再次被访问，为此设置一个辅助数组visited[n], 它的每个元素的初值均为逻辑值假（false），即为常量0，表明尚未被访问，一旦访问了顶点vi，就将对应元素visited[i]设置为逻辑值真，即为常量1，表明vi已被访问)。

(2)、然后从vi的任一未被访问过的邻接点出发进行深度优先搜索遍历，当

vi所有邻接点均被访问过，则退回到上一个顶点vk,从vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历，直到退回到初始点并且没有未被访问过的邻接点为止。

遍历过程

(1)访问vo, 记录visited[0]=True, 从v0的一个未被访问过的邻接点v1

出发遍历；

(2)访问v1, visited[1]=True,从v1的一个未被访问过的邻接点v4出发遍

历；

(3)访问v4, visited[4]=True,从v4的一个未被访问过的邻接点v5出发遍

历；

(4)访问v5, visited[5]=True,由于v5的两个邻接点v1和v4都被访问过，

退回上一邻接点v4，又v4的两个邻接点v1和v5都被访问过，再退回上一邻接点v1,从未被访问过邻接点V6出发遍历；

(5)访问v6, visited[6]=True,从v6的一个未被访问过的邻接点v2出发遍历；

(6)访问v2, visited[2]=True,v2所有邻接点都访问过，退回上一顶点v6,同理，v6退回v1,v1退回v0,再从v0未被访问过邻接点v3出发遍历；(7)访问v3, visited[3]=True，退回v0,因所有邻接点都访问过，再退回，结束。

3.邻接表表示的深度优先搜索非递归算法（参考代码）:

#define MAXVEX 100

void dfs(adjlist g，int v,int n)

/*从顶点v出发进行深度优先遍历*/

{

struct vexnode *stack[MAXVEX], *p;

int visited[MAXVEX],top=0;

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

visited[i]=0;

printf(“%d”,v);

p=g[v].link;

visited[v]=1;

while(top>0||p!=NULL)

{

while(p!=NULL)

if (visited[p->adjvex]==1)

p=p->next;

else

{

printf(“%d”,p->adjvex);

visited[p->adjvex]=1;

top++;

stack[top]=p;

p=g[p->adjvex].link;

}

if(top>0)

{

top--;

/*退栈，回溯查找已被访问结点的未被访问过的邻接点 */

p=stack[top];

p =p->next;

}

}

}

4.DFS时间复杂性

一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。

对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。

4.2.2图的广度优先搜索（Breadth-first Traversal）

广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

1.广度优先搜索的基本思想

首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk……，并均标记为已访问过，然后再按照Vj、Vk……的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止

在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。

设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。

广度优先搜索不是递归过程，不能用递归形式。

2.遍历过程

(1)访问v0,visited[0]=True

(2)访问v0所有未访问过邻接v1和v2, visited[1]=True,

visited[2]=True;

(3)访问v1所有未被访问过的邻接点v3和v4,v5,并将它们标记已访问过；

(4)访问v2所有未被访问过的邻接点v6, visited[6]=True；

(5)访问v3所有未被访问过的邻接点v7, visited[7]=True；

(6)访问v4所有未被访问过的邻接点(无)

(7)访问v5所有未被访问过的邻接点v8, visited[8]=True；

(8)访问v6所有未被访问过的邻接点(无)；

(9)依次访问v7，v8所有未被访问过的邻接点(无)，结束。

3.BFS时间复杂度

一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，广度优先搜索图时间复杂度的c为O(e+n)。

4.3.实验内容与实现提示

1.写一个图形的邻接矩阵表示的深度优先搜索程序。（递归算法）

算法提示：（参考代码）

void DFSM(MGraph *G，int i)

{ //以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵

int j；

printf("visit vertex：％c"，G->vexs[i])；//访问顶点vi

visited[i]=TRUE；

for(j=0；jn；j++) //依次搜索vi的邻接点

if(G->edges[i][j]==1&&!visited[j])

DFSM(G，j)//(vi，vj)∈E，且vj未访问过，故vj为新出发点

}//DFSM

注意：

遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph 或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。

2.写一个邻接表表示的深度优先搜索算法

算法提示：（参考代码）

void DFS(ALGraph *G，int i){

//以vi为出发点对邻接表表示的图G进行深度优先搜索

EdgeNode *p；

printf("visit vertex：％c"，G->adjlist[i].vertex)；//访问顶点vi

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex])//若vi尚未被访问

DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索

p=p->next； //找vi的下一邻接点

}

}//DFS

3.写一个图的邻接表表示的广度优先搜索算法(非递归算法)。

4.写一个邻接矩阵表示的图的广度优先搜索算法（非递归算法）

算法提示：（参考代码）

void BFSM(MGraph *G，int k)

{ 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索

int i，j；

CirQueue Q；

InitQueue(&Q)；

printf("visit vertex：％c"，G->vexs[k])； //访问源点vk

visited[k]=TRUE；

EnQueue(&Q，k)；

while(!QueueEmpty(&Q)){

i=DeQueue(&Q)； //vi出队

for(j=0;jn;j++)//依次搜索vi的邻接点vj

if(G->edges[i][j]==1&&!visited[j]){//vi未访问

printf("visit vertex：％c"，G->vexs[j])；//访问vi visited[j]=TRUE；

EnQueue(&Q，j)；//访问过的vi人队

}

}//endwhile

}//BFSM

5.应用题

如下图：

图中共有9个顶点，14条边为：

98，95，81，75，65，63，60，51，43，42，30，21，20，10

分别用深度优先搜索和广度优先搜索遍历此图。

实现提示：

根据题给信息，程序中建立的数据为：edges="98817565636051434230212010";

createAMLGraph(G,10,13,edges); 深度遍历可以利用递归算法。

(1).深度优先遍历的递归算法(参考代码)：

void DFS(ALGraph *G，int i){

//以vi为出发点对邻接表表示的图G进行深度优先搜索

EdgeNode *p；

printf("visit vertex：％c"，G->adjlist[i].vertex)；//访问顶点vi

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针

while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex])//若vi尚未被访问

DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索

p=p->next； //找vi的下一邻接点

}

}//DFS

(2).邻接表表示图的广度优先搜索算法（参考代码）

void BFS(ALGraph*G，int k)

{// 以vk为源点对用邻接表表示的图G进行广度优先搜索

int i；

CirQueue Q； //须将队列定义中DataType改为int

EdgeNode *p；

InitQueue(&Q)；//队列初始化

//访问源点vk

printf("visit vertex：％e"，G->adjlist[k].vertex)；

visited[k]=TRUE；

EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q)){//队非空则执行

i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针

while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)

if(!visited[p->adivex]){ //若vj未访问过

printf("visitvertex：％c"，C->adjlistlp->adjvex).vertex)； //访问vj

visited[p->adjvex]=TRUE；

EnQueue(&Q，p->adjvex)；//访问过的vj人队

}//endif

p=p->next；//找vi的下一邻接点

}//endwhile

}//endwhile

}//end of BFS

图的遍历操作实验报告

. .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握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; //读入顶点信息，建立顶点表 }

图的优先遍历算法(C语言版)

#include #define MAX_VERTEX_NUM 20 #define ERROR -1 #define TRUE 1 #define FALSE 0 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; void CreateAL(ALGraph *G); int LocateVex(ALGraph G,char u); void DFSTraverse(ALGraph G,void (*Visit)(ALGraph G,int v)); void PrintElem(ALGraph G,int v); void DFS(ALGraph G,int v); int FirstAdjVex(ALGraph G,int v); int NextAdjVex(ALGraph G,int v,int w); int visited[MAX_VERTEX_NUM]; void (*VisitFunc)(ALGraph G,int v); int main(){ ALGraph G; CreateAL(&G); printf("The Graph is:\n"); DFSTraverse(G,PrintElem); getch(); } void CreateAL(ALGraph *T){ int i,j,m; ArcNode *p,*s; char ch[100]; printf("Please input the vexnum and arcnumm:\n"); scanf("%d%d",&(T->vexnum),&(T->arcnum)); printf("Please input the vertexs:\n"); for(i=0;i<(T->vexnum);++i){ scanf(" %c",&(T->vertices[i].data)); T->vertices[i].firstarc=NULL; }

树与图的简单遍历算法

树与图的简单遍历算法 发表时间：2019-01-14T09:56:22.797Z 来源：《科技新时代》2018年11期作者：闵俊齐 [导读] 树与图是两种重要的数据结构，而树可以说是一种特殊的图，它的两两结点之间存在唯一简单路径。 重庆第二外国语学校重庆 400065 摘要：树与图是两种重要的数据结构，而树可以说是一种特殊的图，它的两两结点之间存在唯一简单路径。利用其特殊性质，人们创造了许多算法来处理数据结构问题和程序调用问题。而树与图的遍历算法也是数据结构中重要的算法之一。本文从树与图的概念出发，简单的介绍了树与图的主要存储方式，并重点对二叉树的简单遍历算法、哈夫曼树的生成和图的深度优先遍历及广度优先遍历做出了介绍。 关键词：数据结构；二叉树；图；遍历算法 1.树与图的概念 树是一种数据结构，是由n（n≥0）个结点构成的具有明显层次关系的有限集合。一棵树一般由一个根节点和若干个子结点构成。结点与结点之间具有明显的并列或层次关系，这种层次关系称为父子关系。在一棵树中，没有父结点的结点被称为根结点。树有几个重要的概念，以下做出简单的介绍——树的度：某个结点拥有的子树的数量称为这个结点的度，度为零的结点也叫做叶结点，而度不为零的结点叫做分支结点。树的深度：一棵树的根结点的层次为1，其他结点的层次是其父结点的层次加1。一棵树里最大的层次的值被称为这棵树的深度。树有无序树，有序树，二叉树等。其中二叉树是每个结点最多有两个子结点的树，每个结点的子树通常被称为“左子树”和“右子树”，故二叉树中每个结点的度的最大值为2，而又有左右之分，二叉树中结点的次序不能任意颠倒。除最后一层的叶结点没有子结点外，其余每一层的每个结点都具有两个子结点的二叉树称为满二叉树。如果存在一个深度为h的二叉树，它的除h层外其余各层（1~h-1）的结点数都达到了最大值，并且它的第h层的结点全部集中在树的左边，这种二叉树就被称为完全二叉树。完全二叉树是由满二叉树引申出来的，它是一种效率很高的数据结构。本文后部分将会介绍二叉树的简单遍历算法。 图由若干个顶点组成的有限非空集合和各个顶点的边构成，通常表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图数据结构主要研究形状和图形数据元素之间的关系。它必须反映数据所对应的元素之间的几何关系和拓扑关系。图依照边的方向可分为有向图和无向图。有向图由顶点和弧构成。弧有弧尾和弧头，带箭头的一边称为弧头。图结构与树结构相比较，图中的任意两个元素都有可能相关。而对某个结点而言，树下层可能有多个元素，上层只有能一个元素，复杂度比树大[1]。 2二叉树与图的储存方式 2.1二叉树的储存方式 二叉树有两种储存方式：顺序存储和链式存储。 顺序储存就是按照完全二叉树的结点层次顺序存储的一种只适用于完全二叉树的储存方式，且在最坏的情况下，k个结点的单支数却只需要长度的 -1的一维数据。这种储存需要一个完全连续地址，所以会占用许多的储存空间。 在二叉树中，每个结点信息一般都由一下几个部分构成：该结点的数据元素（Data）、指向左子树的指针（L child）和指向右子树的指针（R child）。利用指针，我们可以很好的存储二叉树。若使用二叉链表，每个结点的结构如图1（a）所示。一般可以（L,D,R）来表示。在三叉链表中，可表示每个结点的父结点，结构如图1（b）所示。一般可以（L,D,P,R）来表示[5]。链式储存不需要完全连续地址，节约储存空间[2]。 图2 3.二叉树的遍历算法及哈夫曼树的生成 3.1二叉树的遍历算法 遍历，是指用某种方法沿着某条路对每一个元素做一且仅一次访问，它是二叉树的重要运算之一。二叉树的主要有三种访问方式：先序遍历、中序遍历、后序遍历。具体实现过程如下：

图的遍历实验报告

实验四：图的遍历 题目：图及其应用——图的遍历 班级：姓名：学号：完成日期： 一.需求分析 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.树的结构体类型如下所示：

图的深度优先遍历算法课程设计报告

合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。

深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。

所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;sn;s++) { printf("请输入下标为%d的顶点的元素:\n",s); scanf("%c",&(G->adjlist[s].vertex)); scanf("%c",&y); //用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。 G->adjlist[s].firstedge=NULL; } printf("请分别输入该图的%d条弧\n",G->e); for(k=0;ke;k++) { printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1)); scanf("%d,%d",&i,&j); p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } } 2.深度优先遍历 void DFS(ALGraph* G,int v) //深度优先遍历 { EdgeNode* p;

图的生成、图的遍历

数据结构B实验报告 一、实验内容 图的生成、图的遍历 二、实验目的 掌握图的基本存储结构 掌握图的相关算法 掌握图的两种遍历方法 三、功能 本实验要求实现以下功能： 1．以邻接矩阵或者邻接表作为存储结构建立一个无向图。 2．深度优先搜索该无向图，输出遍历序列。 3．广度优先搜索该无向图，输出遍历序列。

四、主要代码 #include #include using namespace std; enum Status{UNVISITED,VISITED,SUCCESS,OVER_FLOW, RANGE_ERROR, NOT_PRESENT, ENTRY_FOUND, UNDER_FLOW}; const int DEFAULT_SIZE = 30; const int DEFAULT_INFAULTY =99999; const int MaxSize = 50; template struct Node { ElemType data; Node*next; Node();//普通构造函数 Node(ElemType e, Node*link = NULL);//带形参的构造函数 }; template Node::Node() { next = NULL; } template Node::Node(ElemType e, Node*link) { data = e; next = link; } template class LinkQueue { protected: Node *front, *rear; // 队头队尾指针 public: LinkQueue(); virtual ~LinkQueue(); int GetLength() const; bool IsEmpty() const; void Clear(); Status DelQueue(ElemType &e); Status GetHead(ElemType &e) const; Status EnQueue(const ElemType e); };

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

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

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

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

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

数据结构实验报告图实验

邻接矩阵的实现 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; } }

实验报告：图的存储结构和遍历

武汉东湖学院 实验报告 学院：计算机科学学院—专业计算机科学与技术2016年11月18日 1.实验目的 (1)了解邻接矩阵存储法和邻接表存储法的实现过程。 (2)了解图的深度优先遍历和广度优先遍历的实现过程。 2.实验内容 1.采用图的邻接矩阵存储方法，实现下图的邻接矩阵存储，并输出该矩阵 2.设计一个将第1小题中的邻接矩阵转换为邻接表的算法，并设计一个在屏幕上显示邻接表的算法 3.实现基于第2小题中邻接表的深度优先遍历算法，并输出遍历序列 4.实现基于第2小题中邻接表的广度优先遍历算法，并输出遍历序列

3.实验环境Visual C++ 6.0

4 .实验方法和步骤（含设计） 我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可 知， 其邻接矩阵示意图为如下： V0 v1 v2 v3 v4 v5 V0 1 0 1 0 1 V1 1 0 1 1 1 0 V2 0 1 0 0 1 0 V3 1 1 0 0 1 1 V4 0 1 1 1 0 0 V5 1 1 此时的 “1 ” 表示这两个节点有关系，“ 0”表示这两个节点无关系 我们通过邻接表来在计算机中存储图时，其邻接表存储图如下:

5.程序及测试结果 #include #include int visited [6]; typedef struct { int a[6][6]; int n; }mgraph; typedef struct ANode { int adjvex; struct ANode *nextarc; }ArcNode; typedef struct Vnode { ArcNode *firstarc; }VNode; typedef VNode AdjList [6]; typedef struct { AdjList adjlist; int n; }ALGraph; void mattolist (mgraph g,ALGraph *&G) { int i,j; ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;iadjlist[i].firstarc=NULL; for(i=0;i=0;j--) if(g.a[i][j]!=0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; } G->n=g.n; } void dispadj(ALGraph *G) { int i; ArcNode *p;

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

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，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);

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

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

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

图的基本操作 实验报告

实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。

五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include #define MaxVerNum 100 struct edgenode { int endver; int inform; edgenode* edgenext; }; struct vexnode { char vertex; edgenode* edgelink; }; struct Graph { vexnode adjlists[MaxVerNum]; int vexnum; int arcnum; }; 2、创建无向图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; cout<<"请输入顶点数和边数:"<>G->vexnum>>G->arcnum; cout<<"开始输入顶点表:"<vexnum;i++) { cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL; } cout<<"开始输入边表信息:"<arcnum;k++) { cout<<"请输入边对应的顶点:"; cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1;

数据结构实验七图的创建与遍历

实验七图的创建与遍历 实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求： 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计： #include #include #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数#define QUEUE_SIZE (MAX_VEX+1) //队列长度 using namespace std; bool *visited; //访问标志数组 //图的邻接矩阵存储结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }Graph; //队列类 class Queue{ public: void InitQueue() { base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i

图的深度优先遍历实验报告.doc

一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的 关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶 点未曾访问，则深度优先搜索可从图中某个顶点 v 出发，访问此顶点，然后依次从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有 与 v 有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验容 编写 LocateVex 函数， Create 函数， print 函数， main 函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20

邻接矩阵表示图,深度,广度优先遍历

*问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或∈E； A[i,j]={ 0，反之 图5-2中有向图G1和无向图G2的邻接矩阵分别为M1和M2: M1=┌0 1 0 1 ┐ │ 1 0 1 0 │ │ 1 0 0 1 │ └0 0 0 0 ┘ M2=┌0 1 1 1 ┐ │ 1 0 1 0 │ │ 1 1 0 1 │ └ 1 0 1 0 ┘ 注意无向图的邻接是一个对称矩阵，例如M2。 用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下： VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧(边)数 GraphKind kind; // 图的种类标志

若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若或(Vi,Vj) A[i,j]＝{ ∞, 否则。 其中Wij为或(Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改：adj:weightype ; {weightype为权类型} 图5-6列出一个网和它的邻接矩阵。 ┌∞３１∞∞┐ │∞∞５１∞│ │∞∞∞∞∞│ │∞∞６∞∞│ └∞３２２∞┘ (a)网(b)邻接矩阵 图5-6 网及其邻接矩阵 对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，

图的遍历操作实验报告

实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握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"" #include"" ertex); irstedge; irstedge; } } }//endwhile } //==========主函数=========== void main() { ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 五、实验内容 1调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。 邻接矩阵作为存储结构的运行结果： 邻接链表作为存储结构的运行结果： 六、实验报告要求 画出你所设计的图，写出两种方法的遍历序列。

数据结构实验—图实验报告

精品文档数据结构 实 验 报 告

目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int QElemType; typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue &Q){ //初始化队列 Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; } int EnQueue(LinkQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素{ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;