实验五 图的遍历实验

数据结构,C语言实现,图的遍历

实验五 图的遍历实验

一、实验目的

1、掌握图的两种基本存储结构的表示

2、掌握图的深度优先搜索和广度优先搜索算法

3、理解图的相关术语

4、了解图的广泛应用

二、实验内容

1、先创建一个具有n个顶点的图，然后用深度优先搜索算法（或广度优先搜索算法—选做）对图进行遍历，并输出遍历序列。

1.1 数据结构的设计

/*图的存储结构的表示常用的有邻接矩阵、邻接表

//-------------------- 图的邻接矩阵存储表示 ----------------------------

#define MaxVertexNum 10

typedef char VertexType;

typedef int EdgeType;

typedef struct

{

VertexType vexs[MaxVertexNum]; // 顶点信息

EdgeType edges[MaxVertexNum][MaxVertexNum];//边和弧的信息

int n; //当前图顶点数

int e; //当前边数

}MGraph;

1.2基本思想： 深度优先遍历算法（广度优先遍历算法）

输入：建立图的存储结构：顶点和边（弧），例：无向图G的顶点V=｛A，B，C，D，E，F，G，H｝，边E=｛（A,B），（A,C），（B,D），（B,E），（C,F），（C,G），（D,H），（E,H），（F,G）｝（G具有8个顶点和9条边）

输出：深度优先遍历的顶点序列（按照存储结构）：A,B,D,H,E,C,F,G（或者其它的不同顺序的序列）

1.3 实验步骤：

程序的模块结构：（完整程序需要包含的内容）

头文件、宏定义、typedef

①：图的存储结构定义 /*邻接矩阵或者邻接表存储表示*/

其它数据结构的定义，如广度优先搜索算法中队列的定义

②：创建图的函数： /*输入 图的顶点和边（弧）信息，返回存储结构表示的图*/

③：深度（广度）优先搜索的函数 /*DFS算法中调用④中的函数*/

④：深度（广度）遍历v0所在的连通子图函数 /*邻接矩阵或者邻接表或者非递归算法*/

数据结构,C语言实现,图的遍历

⑤：其它函数，如队列的操作函数（广度优先搜索），输出显示函数

⑥：主函数： /*调用创建图的函数先创建一个图，然后调用深度（广度）优先搜索的函数输出遍历结果*/

源程序主要函数：（只写函数声明）

主函数：

1.4 运行结果：

三、问题讨论

1、深度优先搜索的优点是什么？和广度优先搜索有那些不同？

2、怎样设计图的邻接表存储结构？

四、实验心得

数据结构,C语言实现,图的遍历

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MaxVertexNum 10

#define CAPACITY 10

typedef char VertexType;

typedef int EdgeType;

typedef enum{TRUE, FALSE} bool;

typedef int ElemType;

bool visited[MaxVertexNum];

typedef struct

{

typedef struct

{

Queue* initQueue();

ElemType deQueue(Queue* q);

bool enQueue(Queue* q, ElemType data);

/************************************************************************/ /* 初始化图,图采用邻接矩阵的存储结构

*/ int front; int rear; int size; ElemType data[CAPACITY]; VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int n; //当前图顶点数 int e; //当前边数 }MGraph; }Queue;

/************************************************************************/ MGraph* initMGraph()

{

MGraph* m = NULL; int i, j, k; char v1, v2; m = (MGraph*)malloc(sizeof(MGraph));

数据结构,C语言实现,图的遍历

} printf("please input the number of vertex and edges(v,e): "); scanf("%d,%d", &i, &j); if(i<0 && j<0) { } m->n = i; m->e = j; printf("please input the vertexs by order:\n"); for(i=0; i<m->n; i++) { } for(i=0; i<m->n; i++) { } return m; printf("please input the edges by order('v1,v2'): "); fflush(stdin); scanf("%c,%c", &v1, &v2); for(i=0; v1!=m->vexs[i]; i++); for(j=0; v2!=m->vexs[j]; j++); m->edges[i][j] = 1; for(j=0; j<m->n; j++) m->edges[i][j] = 0; fflush(stdin); scanf("%c", &m->vexs[i]); printf("error number"); return NULL; for(k=0; k<m->e; k++)

/************************************************************************/ /* 深度优先遍历（深度优先搜索） */ /************************************************************************/ bool DFSTraverseM(MGraph* m)

{

}

int i; if(m == NULL) for(i=0; i<m->n; i++) for(i=0; i<m->n; i++) DFSM(m, i); return TRUE; visited[i] = FALSE; return FALSE;

数据结构,C语言实现,图的遍历

bool DFSM(MGraph* m, int i)

{

}

/************************************************************************/ /* 广度优先遍历（广度优先搜索） */ /************************************************************************/ bool BFSM(MGraph* m, int i)

{

}

bool BFSTraverseM(MGraph* m)

{

int j; if(m == NULL) { } for(j=0; j<m->n; j++) if(visited[j] == FALSE && m->edges[i][j] == 1) DFSM(m, j); printf("DFSM: node %c\n", m->vexs[i]); visited[i] = TRUE; return FALSE; if(visited[i] == FALSE) return TRUE; int j; Queue* q = NULL; if(m == NULL) visited[i] = TRUE; printf("BFSM: node %c\n", m->vexs[i]); q = initQueue(); enQueue(q, i); while(q->size != 0) { } return TRUE; i = deQueue(q); for(j=0; j<m->n; j++) if(visited[i] == FALSE && m->edges[i][j] == 1) { } enQueue(q, j); printf("BFSM: node %c\n", m->vexs[j]); visited[j] = TRUE; return FALSE; Queue* q = NULL;

数据结构,C语言实现,图的遍历

}

int i; if(m == NULL) for(i=0; i<m->n; i++) for(i=0; i<m->n; i++) if(visited[i] == FALSE) BFSM(m, i); visited[i] = FALSE; return FALSE; q = initQueue(); return TRUE;

/************************************************************************/ /* 初始化队列 */ /*********************************************************************** …… 此处隐藏：3185字，全部文档内容请下载后查看。喜欢就下载吧 ……