文档介绍:-
. z.
实验报告
实验六 图的应用及其实现
一、实验目的
1.进一步功固图常用的存储构造。
2.熟练掌握在图的邻接表实现图的根本操作。
3.理解掌握AOV网、A z.
Sorted sequence determined: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found.
yyy…yis the sorted, ascending sequence.
Sample Input Sample Output
4 6Sorted sequence determined: ABCD.
A<B Inconsistency found.
A<C Sorted sequence cannot be determined.
B<C
C<D
B<D
A<B
3 2A<B
B<A
26 2A<Z
D<S0 0
设计要求:
1、上机前,认真学****教材,熟练掌握AOV网、AOE网的构造和拓扑排序算法。
2、上机前,认真独立地写出本次程序清单,流程图,该程序包括图类型以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和参考教材事例
三、实验步骤
㈠、数据构造与核心算法的设计描述
*define MA*_VERTE*_NUM 20
//变量声明
typedef struct Arode
//弧结点定义
{
int adjve*; //该弧所指向的顶点的位置
struct Arode *ne*tarc;//指向下一条弧的指针
//InfoType *info;
}Arode;
typedef struct VNode
//顶点结点定义
{
char data; //顶点信息
Arode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MA*_VERTE*_NUM];
-
. z.
typedef struct
//图的定义
{
AdjList vertices;
int ve*num,arum; //图的当前顶点数和弧数
int kind; //图的种类标志
}ALGraph;
ALGraph G; //定义图变量
bool visited[MA*_VERTE*_NUM]; //标志数组
int indegree[MA*_VERTE*_NUM]; //入度数组
struct Stack
//栈类型定义
{
int s[21];
int top;
};
Stack stack;
//定义一个栈
相关函数声明:
void CreateGraph(MGraph &G)
// 输入图的顶点和边的信息,建立图
void DFSTraverse(Graph G, int v)
//深度优先搜索遍历图
void BFSTraverse(Graph G, int v)
//广度优先搜索遍历图
int LocateVertices(ALGraph G,char a)
//查找字符a在图中的位置
int FirstAdjVe*(ALGraph G,int v)
//查找图中位置v的第一个邻接点在图中所在的位置
int Ne*tAdjVe*(ALGraph G,int v,int w)
//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
void DestroyGraph(ALGraph &G)
//销毁图
void InitStack(Stack &stack)
//初始化栈
void PushStack(Stack &stack,int i)
//元素i入栈
void PopStack(Stack &stack,int &i)
//栈顶元素出栈
int StackEmpty(Stack stack)
//判断栈是否为空,假设为空则返回1,否则返回0
void FindInDegree(ALGraph G,int *indegree)
//求图中各个顶点的入度,并相应的存入入度数组中indegree[]
int TopologicalSort(ALGraph G)
//对图进展拓扑排序,并输出相应的拓扑序列
㈡、函数调用及主