当前位置：文档之家› 图的深度广度遍历(算法与数据结构课程设计)

图的深度广度遍历(算法与数据结构课程设计)

图的操作

一、问题描述

图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。

二、基本要求

1、选择合适的存储结构完成图的建立；

2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列；

3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；

三、测试数据

四、算法思想

1、邻接矩阵

顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。

2、邻接表

邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i 个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，

除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。

3、图的深度遍历

深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

4、图的广度遍历

广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个

曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

五、模块划分

一、基于邻接矩阵的深广度遍历

1．Status InitQueue(LinkQueue *Q)

根据已知Q初始化队列

2．Status QueueEmpty (LinkQueue Q)

判断队列是否为空

3．Status EnQueue(LinkQueue *Q, QElemType e)

将e压入队尾

4．Status DeQueue(LinkQueue *Q, QElemType *e)

取队头元素e

5．int LocateVex(MGraph G,VertexType v)

定位定点v

6．void CreateGraph(MGraph *G)

建立无向图的邻接矩阵

7．void PrintGraph(MGraph G)

输出邻接矩阵的无向图

8．int FirstAdjVex(MGraph G,int v)

第一个邻接点的定位

9．int NextAdjVex(MGraph G,int v,int w)

查找下一个邻接点

10．void Dfs(MGraph G, int v)

实现图的一次遍历

11．void DfsTraverse(MGraph G)

实现图的深度遍历

12．void BfsTraverse(MGraph G)

实现图的广度遍历

13．Main

主函数

二、基于邻接表实现图的深广度遍历

1．Status InitQueue(LinkQueue *Q)

根据已知Q初始化队列

2．Status QueueEmpty (LinkQueue Q)

判断队列是否为空

3．Status EnQueue(LinkQueue *Q, QElemType e)

将e压入队尾

4．Status DeQueue(LinkQueue *Q, QElemType *e) 取队头元素e

5．void createALGraph(ALGraph *G)

建立无向图的邻接矩阵

6．void PrintGraph(MGraph G)

输出邻接矩阵的无向图

7．int FirstAdjVex(MGraph G,int v)

第一个邻接点的定位

8．int NextAdjVex(MGraph G,int v,int w)

查找下一个邻接点

9．void Dfs(MGraph G, int v)

实现图的一次深度遍历

10．void DfsTraverse(MGraph G)

实现图的深度遍历

11．void BFS(ALGraph G, int v)

实现图的一次广度遍历

12．void BfsTraverse(MGraph G)

实现图的广度遍历

13．Void …………………………………Main

主函数

六、数据结构//(ADT)

1、基于邻接矩阵的图的类型定义

typedef struct ArcCell

{ VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/

} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{ VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/

AdjMatrix arcs; /*邻接矩阵*/

int vexnum,arcnum; /*图中当前顶点数和边数*/ } MGraph;

2、基于邻接表的图的类型定义

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode; /*表节点*/

typedef struct

{

TElemType data;

ArcNode *firstarc;

}VNode,AdjList[MAXVER]; /*表节点*/

typedef struct

{

AdjList vertices;

int vexnum,arcnum; /*图中当前顶点数和边数*/

} ALGraph;

七、源程序

一、基于邻接矩阵的图的深度、广度遍历

#include "stdlib.h"

#include "stdio.h"

#include "string.h"

#define TRUE 1

#define FALSE 0

#define OVERFLOW -2

#define OK 1

#define ERROR 0

typedef int Status;

#define INFINITY INT_MAX /*最大值“无穷”*/

#define MAX_VERTEX_NUM 20 /*最大顶点个数*/

typedef int Boolean;

typedef char VertexType[20];

typedef int VRType;

/**************以下为队列的操作************/

/****队列的类型定义****/

typedef int QElemType;

typedef struct QNode

{QElemType data;

struct QNode *next;

} QNode, *QueuePtr;

typedef struct

{

QueuePtr front;

QueuePtr rear;

} LinkQueue;

/****初始化队列****/

Status InitQueue(LinkQueue *Q)

{ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(OVERFLOW);

(*Q).front->next=NULL;

return OK; }

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

Status QueueEmpty (LinkQueue Q)

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

return TRUE;

else

return FALSE; }

/****入队列****/

Status EnQueue(LinkQueue *Q, QElemType e)

{ QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if (!p) exit(OVERFLOW);

p->data=e; p->next=NULL;

(*Q).rear->next=p;

(*Q).rear=p;

return OK; }

/****出队列****/

Status DeQueue(LinkQueue *Q, QElemType *e)

{ QueuePtr p;

if ((*Q).front==(*Q).rear) return ERROR;

p=(*Q).front->next;

*e=p->data;

(*Q).front->next=p->next;

if ((*Q).rear==p) (*Q).rear=(*Q).front;

free(p);

return OK; }

/**************以下为图的操作************/

/*图的类型定义*/

typedef struct ArcCell

{ VRType adj; /*图中有1/0表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/

} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{ VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/

AdjMatrix arcs; /*邻接矩阵*/

int vexnum,arcnum; /*图中当前顶点数和边数*/

} MGraph;

/* 顶点在顶点向量中的定位*/

int LocateVex(MGraph G,VertexType v)

{ int i;

for(i=0;i

if (strcmp(v,G.vexs[i])==0) break;

return i;

}

/*建立无向图的邻接矩阵*/

void CreateGraph(MGraph *G)

{ int i,j,k; VertexType v1,v2;

printf("\nInput MG vexnum,arcnum:");

scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);

printf("Input %d vexs:",(*G).vexnum);

for(i=0;i<(*G).vexnum;i++) /*输入顶点向量*/ { scanf("%s",(*G).vexs[i]); }

printf("vexs list\n");

for(i=0;ivexnum;i++) /*输出顶点向量*/

puts(G->vexs[i]);

for(i=0;i<(*G).vexnum;i++) /*邻接矩阵初始化*/ for(j=0;j<(*G).vexnum;j++)

(*G).arcs[i][j].adj=0;

printf("\nInput %d arcs(vi vj):\n",(*G).arcnum); for(k=0;k<(*G).arcnum;k++) /*输入无权图的边*/ { scanf("%s%s",v1,v2);

i=LocateVex(*G,v1); j=LocateVex(*G,v2);

(*G).arcs[i][j].adj=1;

(*G).arcs[j][i]=(*G).arcs[i][j];

}

/*按邻接矩阵方式输出无向图*/

void PrintGraph(MGraph G)

{ int i,j;

printf("\nMGraph:\n");

for(i=0; i

{ printf("%10s",G.vexs[i]);

for(j=0; j

printf("%4d",G.arcs[i][j].adj);

printf("\n");

}

/* 查找第1个邻接点 */

int FirstAdjVex(MGraph G,int v)

{ int j,p=-1;

for(j=0;j

if (G.arcs[v][j].adj==1) {p=j; break;}

return p;

}

/* 查找下一个邻接点 */

int NextAdjVex(MGraph G,int v,int w)

{ int j,p=-1;

for(j=w+1;j

if (G.arcs[v][j].adj==1) {p=j; break;}

return p;

}

/*深度遍历*/

Boolean visited[MAX_VERTEX_NUM]; /* 设置全局的访问标志数组 */

void Dfs(MGraph G, int v)

{ int w;

visited[v]=TRUE;

printf("%s",G.vexs[v]);

for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))

if(!visited[w]) Dfs(G,w);

}

void DfsTraverse(MGraph G)

{ int v;

for (v=0; v

visited[v]=FALSE;

for(v=0; v

if (!visited[v]) Dfs(G,v);

}

/* 广度遍历 */

void BfsTraverse(MGraph G)

{ int v,u,w; LinkQueue Q;

for(v=0; v

InitQueue(&Q);

for(v=0; v

if (!visited[v])

{ visited[v]=TRUE;

printf("%s",G.vexs[v]);

EnQueue(&Q,v);

while(!QueueEmpty(Q))

{ DeQueue(&Q,&u);

for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if (!visited[w])

{ visited[w]=TRUE;

printf("%s",G.vexs[w]);

EnQueue(&Q,w);

}

/*主函数*/

main()

{ int w;

MGraph G;

CreateGraph(&G);

PrintGraph(G);

printf("\nDfs:"); DfsTraverse(G); /* 深度遍历 */ printf("\nBfs:"); BfsTraverse(G); /* 广度遍历 */ }

二：基于邻接表的图的深度、广度遍历

#include "stdlib.h"

#include "stdio.h"

#include "string.h"

#define MAXVER 21

#define N 100

typedef char TElemType[10];

/*循环队列的操作*/

/****队列的类型定义****/

typedef int ElemType;

typedef struct

{

ElemType *base;

int front,rear;

}SqQueue;

/****初始化队列****/

void InitQueue(SqQueue *Q)

{Q->base=(ElemType *)malloc(N*sizeof(ElemType)); Q->front=Q->rear=0; }

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

int QueueEmpty(SqQueue Q)

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

return 1;

else

return 0;}

/****入队列****/

int EnQueue(SqQueue *Q,ElemType e)

{if((Q->rear+1)%N==Q->front)

return 0;

Q->base[Q->rear]=e;

Q->rear=(Q->rear+1)%N;

return 1;}

/****出队列****/

int DeQueue(SqQueue *Q,ElemType *e)

{if(Q->rear==Q->front)

return 0;

*e=Q->base[Q->front];

Q->front=(Q->front+1)%N;

return 1;}

/*图的操作*/

/*图的类型定义*/

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode;

typedef struct

{

TElemType data;

ArcNode *firstarc;

}VNode,AdjList[MAXVER];

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

} ALGraph;

/*建立无向图的邻接矩阵*/

void createALGraph(ALGraph *G)

{

int i, s, d;

ArcNode *p,*q;

printf("\nInput MG vexnum,arcnum:");

scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);

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

{

printf("\n输入第%d个顶点信息：",i);

scanf("%s",G->vertices[i].data);

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

} //输入第i个结点值并初始化第i个单链表为空

for(i=1; i<=G->arcnum; i++)

{

printf("\n输入第%d条边的始点和终点：",i);

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

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=d;

p->nextarc=G->vertices[s].firstarc;

G->vertices[s].firstarc=p;

//将新建的以d为信息的表结点p插入s单链表的头结点后

q=(ArcNode*)malloc(sizeof(ArcNode));

q->adjvex=s;

q->nextarc=G->vertices[d].firstarc;

G->vertices[d].firstarc=q;

//将新建的以s为信息的表结点q插入d单链表的头结点后

}

/*深度遍历*/

int visited[MAXVER];//定义全局数组遍历visited

void dfs(ALGraph G, int v)//被遍历的图G采用邻接表作为存储结构，v为出发顶点编号{

ArcNode *p;

printf("%s",G.vertices[v].data);

visited[v]=1;

p=G.vertices[v].firstarc;

while(p!=NULL)

{

if(visited[p->adjvex]==0) dfs(G,p->adjvex);

//若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfs

p=p->nextarc;

}

void dfsTraverse(ALGraph G)

{

int v;

//遍历图之前初始化各未访问的顶点

for(v=1; v<=G.vexnum; v++)

visited[v]=0;

//从各个未被访问过的顶点开始进行深度遍历

for(v=1;v<=G.vexnum;v++)

if(visited[v]==0) dfs(G,v);

}

/*广度遍历*/

void BFS(ALGraph G, int v)

//从顶点编号v出发，广度遍历邻接表存储的图G {

SqQueue Q; ArcNode *p;

InitQueue(&Q);

printf("%s",G. vertices[v].data);

visited[v]=1;

EnQueue(&Q,v);

while(!QueueEmpty(Q))

{

v=DeQueue(&Q,&v);

p=G.vertices[v].firstarc;

while(p!=NULL)

{

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

{

v=p->adjvex;

printf("%s",G.vertices[v].data);

visited[v]=1;

EnQueue(&Q,v);

}

p=p->nextarc;

}

void BFSTraverse(ALGraph G)

{

int v;

//遍历G以前，初始化visited数组为0

for(v=1;v<=G.vexnum;v++)

visited[v]=0;

for(v=1;v<=G.vexnum;v++)

if(visited[v]==0)

BFS(G,v);

}

void main()

{

ALGraph G;

createALGraph(&G);

printf("深度遍历结果为：\n");

dfsTraverse(G);

printf("\n广度遍历结果为：\n");

BFSTraverse(G);

system("pause");

}

八、测试情况

程序的测试结果如下：

1、基于邻接矩阵的图的深度、广度遍历

结果正确

2、基于邻接表的图的深度、广度遍历

结果正确

九、参考文献

1、严蔚敏，《数据结构 C语言》，清华大学出版社。

2、谭浩强，《c语言程序设计》，清华大学出版社。

小结

图的遍历是有关于图的算法中最常见、最典型的算法。与树的遍历相类似，图的遍历是从图中任意一个顶点出发，访问遍图中所有的顶点，且使每个顶点仅被访问一次。图的遍历算法是求解图的连通性、拓扑排序、和求关键路径等算法的基础。由于图本身结构的复杂性，因而使得图的遍历要比树的遍历复杂得多。首先，图中所有顶点没有主次之分，因此也就没有一个“自然”的起始点；其次，图中任意顶点均有可能与其它顶点相邻，在沿着某一路径依次搜索访问顶点时完全有可能又回到该顶点上；此外，图中某一顶点可能与多个顶点相邻，当访问过该结点后，如何选择下一个要访问的顶点，就成为一个决策问题。鉴于图的遍历的复杂性，遍历算法的设计就必须考虑图的结构特征。图的遍历算法通常有两条遍历路径：深度优先遍历和广度优先遍历。

通过学习了图的深度遍历和广度遍历，我们对邻接表和邻接矩阵进行深度遍历和广度遍历。图的深度遍历类似于树的先根遍历，广度遍历类似于树的层次遍历。在实际中，由于在图中各个结点的度数各个不同，最大度数和最小度数可能相差很多，如果按度数最大的顶点设计结点结构，就会浪费很多存储单元，反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。在实际应用中不宜采用这种结构，而应该根据具体的图和需要进行的操作，设计恰当的结点结构和表结构，这时我们就用邻接表来处理，邻接表是图的一种链式存储结构。在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。图遍历的过程实质上是对每个顶点查找其邻接点的过程，是通过边或弧找邻接点的过程在邻接表中，对图的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以vi为尾的弧）。邻接表中每一个表结点有两个域，其一为邻接点域adjvex，用以存放与顶点vi 相邻接的顶点vj的序号j，其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertex，另一个则是指针域(指向邻接表)link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个一维数组存储起来，其中第i个分量存储vi邻接表的表头指针邻接表中每一个表结点有两个域，其一为邻接点域adjvex，用以存放与顶点vi 相邻接的顶点vj的序号j，其二为指针域next，用来将邻接表的所有结点链在一起。如果要表示边上的权值，那么就要再增设一个数据域。另外，为每个顶点vi的邻接表设置一个具有两个域的表头结点：一个域是顶点信息域vertex，另一个则是指针域(指向邻接表)link，它是vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，需要把这n个表头指针用一个一维数组存储起来，其中第i个分量存储vi邻接表的表头指针。，一个图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。，一个图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边结点的链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。

广度遍历图的时间复杂度和深度遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。这两种遍历既适用于无向图，也适用于有向图。但无论何种算法都是建立在邻接表存储结构之上所展开的。

经过这次的程序设计让我们对邻接表和邻接矩阵有了更深度的了解，更对深度遍历和广度遍历的应用有了确切的明白，在以后的编程中也知道如何正确的运用。

二叉排序树的建立及遍历的实现

课程设计任务书题目: 二叉排序树的建立及遍历的实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）建立二叉排序树；（2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日排序二叉树的建立及其遍历的实现

摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归调用，这将极大的方便算法设计。 1．需求分析建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。

图的深度广度优先遍历操作代码

一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。二、实验内容实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include #include #define MAX_VERTEX_NUM 30 #define MAX_QUEUE_NUMBER 30 #define OK 1 #define ERROR 0 #define INFEASIBLE -1

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 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)

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

课程设计二叉树

安徽理工大学数据结构课程设计说明书题目: 二叉树的遍历集成院系：计算机科学与工程学院专业班级：学号：学生姓名：指导教师： 2015年 01 月 9 日

安徽理工大学课程设计（论文）任务书计算机科学与工程学院信息安全教研室 2014年 12 月 18 日

目录 1.需求分析 (1) 2、总体设计 (1) 2.1 程序目录 (1) 2.2 算法流程 (3) 3、详细设计 (3) 3.1 界面设计 (3) 3.2 详细代码设计 (5) 3.3 调试分析 (10) 4、总结 (15) 参考文献 (16) 代码详述 (16)

1.需求分析 “数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心,而且也成为其他理工类学科必修课程,所谓”数据结构”是相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的相互关系成为结构,结构一般有线性结构,树形结构,图状结构,本程序所做的就是树形结构的二叉树的遍历算法和线索化查找. 本程序使用VC6.0++编写,具体实现功能有二叉树的遍历,包括先序遍历,中序遍历,后序遍历的递归算法以及非递归算法.另外本程序还有可线索化二叉树的功能,由此可以得到二叉树某个节点的前驱和后继. 题目要求为: 1.实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。 2.要求能查找任一结点在某种遍历序列中的前驱和后继。 3.界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。由小组一起制作,本人做小组汇总工作,并在基础上加了查找某个节点是否存在二叉树,以及求二叉树总节点数等一些简单功能 2、总体设计 2.1 程序目录 (1)typedef struct node 二叉树的定义,包含数据域data,左孩子lchild,右孩子rchild,若二叉树为空,则头结

图的深度和广度优先遍历

数据结构课程实验报告课程名称数据结构班级计算123 实验日期2014年6月1日--3日姓名学号实验成绩实验名称实验四图的深度和广度优先遍历实验目的及要求【实验目的】熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。【实验要求】 1.图的存储可采用邻接矩阵或邻接表 2.GraphCreate(): 按从键盘的数据建立图 3.GraphDFS()：深度优先遍历图 4.GraphBFS()：广度优先遍历图 5.编写完整程序完成下面的实验内容并上机运行 6.整理并上交实验报告实验环境硬件平台：普通的PC机软件平台：Windows 7 操作系统编程环境：VisualC++ 6.0 实验内容1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。

算法描述及实验步骤算法： 1)定义图的邻接表存储结构 2）实现图的邻接表存储，即建立图的存储结构 3）实现图的深度优先遍历 4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。伪代码： 1）定义邻接矩阵和队列的存取结构； 2）创建图L： 1.置空图L->num=0； 2.输入顶点数目num； 3.i++,输入结点L->vexs[i]直到L->num; 3）输出图L的各顶点； 4）深度优先遍历图g中能访问的各个顶点 1.输入起点的下标qidian； 2.标志数组初始化mark[v]=0; 3.for(v=qidian;v

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

合肥学院计算机科学与技术系课程设计报告 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;

数据结构课程设计二叉树遍历查找

课程设计任务书 2011 —2012 学年第一学期电子与信息工程系计算机专业09计算机一班班级课程设计名称：数据结构课程设计设计题目：排序二叉树的遍历完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。四、参考文献

1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 #include using namespace std; int num; //-----------排序二叉树节点--------------// struct tree //定义二叉树节点结构 { int data; //节点数据域 tree *right,*left; //右，左子树指针 }; //-----------排序二叉树类----------------// class Btree { tree *root;//根节点 public: Btree()

实验四：图的深度优先与广度优先遍历

实验报告

再从这些顶点出发，访问它们还未访问过的邻接点，…，如此做下去，直到图中所有顶点都被访问过为止。 2、（1）将没有前驱（入度为零）的顶点进栈。（2）从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1，同时将当前已输出的顶点个数加1. （3）将新的入度为零的顶点再进栈。（4）重复（2）、（2）两步，直到栈为空为止。此时或者已经输出前部顶点，或者剩下的顶点中没有入度为零的顶点。 3、设置一个n*n的矩阵A（k），其中除对角线元素为0外，其他元素A(k)[i][j]表示顶点i到顶点j的路径长度，k表示运算步骤。开始时k = -1,A(-1)[i][j] = arcs[i][j],即A为图的邻接矩阵。以后逐步尝试在原路径中加入其他顶点作为中间点，如果增加中间点顶点后，得到的路径比原来的路径短，则以此新路径代替原来路径，修改矩阵元素。具体做法为：第0步让所有路径上加入中间点0，去A[i][j]与A[i][0] + A[o][j]中较小的值作A[i][j]的新值，完成后得到A(0)如此进行下去，当第n-1步完成后，得到A(n-1),A(n-1)即为所求的结果，A(n-1)[i][j]表示从i 到j路径上的中间顶点的序号小于或等于n-1的最短路径的长度，即A(n-1)[i][j]表示从i到j 的最短路径的长度。算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 1、

2、

3、

算法时间复杂度分析 1、深度优先遍历：O（n*n）. 广度优先遍历：O（n*n）. 2、 O（n+e）. 3、 O(n*n*n). 四、收获与体会不想说什么，这章的程序太难了，每次一想起来数据结构还没做就烦，前两个题基本上一天能做一道题，第三题也就是骗骗OJ，实际上还有个小BUG，等有空再写个真正符合题意的程序吧。五、源代码清单

图的深度遍历

#include #include #define n 4 //图的顶点数 #define e 5 //图的边数 typedef struct node { int adjvex; struct node *next; } edgenode;//边表节点 typedef struct { char vertex; edgenode *link; }vexnode;//顶点表节点 vexnode ga[n]; int visited[n]; void Creatadjlist(vexnode ga[])//建立无向图的邻接表{ int i,j,k; edgenode *s; printf("请输入各个顶点："); for(i=0;iadjvex=j; s->next=ga[i].link; ga[i].link=s; s=malloc(sizeof(edgenode)); s->adjvex=i; s->next=ga[j].link; ga[j].link=s; } } void Dfsl(int i)//邻接表的深度遍历 {

edgenode *p; printf("node:%c\n",ga[i].vertex); visited[i]=1; p=ga[i].link; while(p!=NULL) { if(!visited[p->adjvex]) { Dfsl(p->adjvex); } p=p->next; } } void main() { int i; Creatadjlist( ga); printf("请输入需要遍历的顶点：\n"); scanf("%d",&i); Dfsl(i); }

人工智能深度优先算法课程设计报告

人工智能课程报告题目：深度优先算法班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX

【摘要】结合生活中解决搜索问题所常用的思考方法与解题方法，从深度优先探讨了提高程序效率的适用技巧。【关键词】1搜索顺序；2搜索对象；3搜索优化；一、深度优先搜索的优化技巧我们在做事情的时候，经常遇到这类问题——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。二、搜索的顺序及对象：在解决约束满足问题的时候，问题给出的约束条件越强，对于搜索就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行优化，达到提高程序效率的目的。显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件优化效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。三、搜索特点 1.由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。 2.深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。

3.由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。 4.深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。 5.适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。四、算法数据结构描述深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN 表，直到搜索到目标结点或OPEN栈空为止。具体算法如下： ①把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。 ②如果OPEN为一空表，则搜索失败退出。 ③取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。 ④如果结点ｎ的深度等于最大深度，则转向２。 ⑤否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。 ⑥如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。

二叉树遍历课程设计心得【模版】

目录一．选题背景 (1) 二．问题描述 (1) 三．概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四．详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五．测试数据与分析 (6) 六．源代码 (6) 总结 (10) 参考文献: (11)

一．选题背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。二．问题描述对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。

三．概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图图3.3二叉树中序遍历示意图

图地深度广度遍历(算法与大数据结构课程设计)

图的操作一、问题描述图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。二、基本要求 1、选择合适的存储结构完成图的建立； 2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列； 3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列；三、测试数据四、算法思想 1、邻接矩阵顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。 2、邻接表邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i 个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，

除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。 3、图的深度遍历深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 4、图的广度遍历广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。五、模块划分一、基于邻接矩阵的深广度遍历 1．Status InitQueue(LinkQueue *Q) 根据已知Q初始化队列 2．Status QueueEmpty (LinkQueue Q) 判断队列是否为空 3．Status EnQueue(LinkQueue *Q, QElemType e) 将e压入队尾 4．Status DeQueue(LinkQueue *Q, QElemType *e) 取队头元素e 5．int LocateVex(MGraph G,VertexType v) 定位定点v 6．void CreateGraph(MGraph *G) 建立无向图的邻接矩阵 7．void PrintGraph(MGraph G) 输出邻接矩阵的无向图 8．int FirstAdjVex(MGraph G,int v) 第一个邻接点的定位 9．int NextAdjVex(MGraph G,int v,int w) 查找下一个邻接点

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

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