发布时间 : 星期三 文章图的建立和应用更新完毕开始阅读4e3cc4d776a20029bd642dc7
一、实验目的
熟悉图的存储方式，实现图的邻接矩阵或者邻接表的存储方式下的基本运算，特别是深度遍历和广度遍历；掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等 二、需求分析
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); //找无向带权图的最小生成树