图的建立和应用

一、实验目的

熟悉图的存储方式，实现图的邻接矩阵或者邻接表的存储方式下的基本运算，特别是深度遍历和广度遍历；掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等 二、需求分析

1、定义图的邻接表存储结构。

2、在定义的存储结构下实现下面的操作： （1）图的创建操作； （2）图的销毁操作；

（3）图的深度遍历的递归算法； （4）图的广度遍历算法；

（5）求图的最小生成树算法； （6）求图的最短路径算法。

3、图的深度遍历算法的非递归算法；应用图的拓扑排序求关键路径的算法（选做） 。

#include \#include \

#define EdgeType int #define VertexType char #define MaxVerNum 10 #define MAXSIZE 20 #define DataType int #define MAX 1000

#define true 1 #define false 0

int visited[MaxVerNum];

//定义的一个标志图的顶点是否已经被访问的全局数组

int tag;

//用于标识图的边是否具有权值,有则tag=true,否则为false

typedef struct enode{ int adjvertex; EdgeType info; struct enode *next; }EdgeNode;

//定义边的信息

typedef struct vnode{ VertexType vertex; EdgeNode * fristEdge; }VertexNode; //顶点的信息

typedef struct tnode{ char vertex1,vertex2; EdgeType info; struct tnode *next; }*PlowestTree,lowestTree;

//prim需要的最小生成树边的数据结构

typedef struct{ int ver1,ver2; EdgeType info; }edgeInfo;

//kruskal法需要的数据结构

typedef struct{ VertexNode adjlist[MaxVerNum]; int n,e; }ALGraph;

//定义邻接表存储的图

typedef struct{ int data[MAXSIZE]; int front,rear;

}sepQueue,*PsepQueue; //队的数据结构

typedef struct{ DataType data[MAXSIZE]; int top;

}sepStack, *PsepStack; //栈的数据结构

typedef struct node{

int data; struct node * next; }Linkstack,*PLinkstack;

typedef struct{ PLinkstack top; }stack,*Pstack;

//链栈,用于求解拓扑序列

Pstack Init_stack();

/*函数功能:初始化一个栈*/

int empty_stack(Pstack s); //判断一个栈是否为空

int push_stack(Pstack s,int data); //入栈

int pop_stack(Pstack s,int *data); //出栈

void Destory_stack(Pstack *s); //销毁栈

PsepStack Init_sepStack(); //初始化一个栈

int push_sepStack(PsepStack p,DataType data);

//入栈,返回0表示入栈失败,返回1表示入栈成功

int pop_sepStack(PsepStack p,DataType *data); //出栈,返回0表示出栈失败,返回1表示出栈成功

int empty_sepStack(PsepStack p);

//判断栈是否为空,返回0表示栈空,返回1表示出栈非空

void Destory_sepStack(PsepStack *p); //销毁栈

PsepQueue Init_sepQueue(); //队的初始化

int empty_sepQueue(PsepQueue Q);

//判断队是否为空

int push_sepQueue(PsepQueue Q,int data); //新队员入队

int pop_sepQueue(PsepQueue Q ,int *data); //队员出队

void Destory_sepQueue(PsepQueue *Q); //销毁队列

ALGraph create_undALGraph(); //创建一个无向图

void printf_ALGraph(ALGraph ALG); //输出采用邻接表存储的图

void depth_Graph(ALGraph ALG);

//深度遍历图(可以计算图有几个连通分量)

void DFS(ALGraph ALG,int v);

//深度遍历图(为 depth_Graph 的子函数)

void bread_Graph(ALGraph ALG);

//广度遍历图(可以计算图有几个连通分量)

void BFS(ALGraph ALG,int v);

//广度遍历图(为 bread_Graph 的子函数)

void catch_values(ALGraph *ALG); //为图中的边带权

void uncatch_values(ALGraph *ALG);

//不为图中的边带权,即创建图时,边没有带权

void unDepth_Graph(ALGraph ALG); //非递归法深度遍历图

void select_min(int list[],int *min,int size); //从指定的数组中选择最小值的数组下标

PlowestTree search_prim_lowestTree(ALGraph ALG); //找无向带权图的最小生成树