图的遍历1.doc

图的遍历及其应用实现
一、实验目的
。
。
。
二、实验内容
从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。
1
2
5
3
4
三、实验步骤
㈠、数据结构与核心算法的设计描述
自己定义的数据类型
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码,如OK 等*/
typedef int Boolean;
//Boolean 是布尔类型,其值是TRUE 或FALSE */
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef char VertexType[MAX_NAME]; /* 字符串类型*/
#define ElemType int
typedef struct Qnode
{ ElemType data; //数据域
Qnode *next; //指针域
}Qnode ,*Queueptr;

typedef struct
{
Queueptr front; //头指针
Queueptr rear; //尾指针
}LinkQueue;
在广度遍历中需要需要用到队列,下面就是对队列的基本应用
void InitQueue(LinkQueue & Q)//初始化队列
void EnQueue(LinkQueue & Q,ElemType x)//插入值为X的结点到队列中
ElemType DeQueue (LinkQueue & Q,int &x)
int QueueEmpty(LinkQueue & Q)
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*/
/* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */}
Status CreateGraph(ALGraph &G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G}
void DestroyGraph(ALGraph &G)
{ /* 初始条件: 图G 存在。操作结果: 销毁图G */}
void DestroyGraph(ALGraph &G)
{ /* 初始条件: 图G 存在。操作结果: 销毁图G */}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点*/
/* 操作结果: 返回v 的第一个邻接顶点的序号。若顶点在G 中没有邻接顶点,则返回-1 */}
int NextAdjVex(ALGraph G,Ve