-
实验六
图的应用及其实现
一、实验目的
1
．进一步功固图常用的存储结构。
2
．熟练掌握在图的邻接表实现图的基本操作。
3
．理解掌握
AOV
网、
AOE
网在邻接表上的实现以及解决简单
的应用问题。
二、实验内容
[
题目一
]
：从键
盘上输入
AOV
网的顶点和有向边的信息
,
建立其邻接表存储结构
,
然
后对该图拓扑排序
,
并输出拓扑序列
.
试设计程序实现上述
AOV
网的类型定义和基本操
作
,
完
成上述功能。
测试数据：教材图
7.28
[
题目二
]
：从键盘上输入
< br>AOE
网的顶点和有向边的信息
,
建立其邻接表存储结构
,
输
出其关键
路径和关键路径长度。
试设计程序实现上述
< br>AOE
网类型定义和基本操作
,
完成
上述功能。
测试数据：教材图
7.29
三、实验步骤
㈠、数据结构与核心算法的设计描述
基本数据结构：
#define
TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status
是函数的类型
,
其值是函数结果状态代码，如
OK
等
*/
#define INFINITY
INT_MAX
//
定义无穷大
∞
#define MAX_VERTEX_NUM
20
typedef int V
ertexType;
typedef int InfoType;
typedef
struct
ArcNode
//
表结点定义
{
InfoType info;
int
adjvex;
//
邻接点域，存放与
V
i
邻接的点在表头数组中的位置
< br>
ArcNode
*nextarc;
//
链域，指示依附于
vi
的下一条边或弧的结点，
}ArcNode;
typedef
struct
VNode
//
表头结点
{
int data;
//
存放顶点信息
struct
ArcNode
*firstarc;
//
指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
//
图的结构定义
AdjList
vertices;
//
顶点向量
int
vexnum, arcnum;
int
Isquan;//
是否含有权值
} MGraph;
typedef struct
{
int *top;
int *base;
int stacksize;
}Sqstack;
typedef int ElemType;
Status Initstack(Sqstack &s)
{
=(int*)malloc(sizeof(int)*25);
}
if (!)
return ERROR;
=;
ize=25;
return
OK;
int indegree[MAX_VERTEX_NUM];
int ve[MAX_VERTEX_NUM];//e
各顶
点的最早发生时间
int vl[MAX_VERTEX_N
UM];//
各顶点发生的最晚发生时间
调用的函数
Status
Initstack(Sqstack &s)
Status
Pop(Sqstack &s,int &e)
//
若栈
不空，则删除
S
的栈顶元素，
//
用
e
返回其值，
并返回
OK
；否则返回
ERROR
int Push(Sqstack &s,int &e)
int StackEmpty(Sqstack s)
//
若栈
为空栈，则返回
TRUE,
否则返回
F
LASE
Status
CreateGraph(MGraph &G)
void
Display(MGraph &G)
/*
输出图
G
的信息
*/
void FindDegree(MGraph g,int
indegree[])
//
对
=<
/p>
图中的各个顶点的入度进行统计，
并将第
i
//
个顶点的入度数放入
indegree[i]
int LocateVex(MGraph
G,VertexType u)
/*
初始条件
:
图
G
存在
,u
和
G
中顶点有相同特征
*/
/*
操作结果
:
若
G
中存在顶点
u,
则返回该顶点在图中位置
;
否
则返回
-1 */
Status
ToopologicalSort (MGraph
g)
//
对图进行拓扑排序，并输出拓扑排序的结果
Status ToopologicalOrder
(MGraph
g,Sqstack
&T)//
拓扑序列
Status
CriticalPath(MGraph g,Sqstack
T)//
关键路径
㈡、函数调用及主函数设计（
可用函数的调用关系图说明）
void main()
{
}
MGraph g;
Sqstack T;
cout<<
创建图
:n
Cr
eateGraph(g);
cout<<
输出图的信息
:n
Display(g);
cout<
<
拓扑排序
:n
Toopologic
alSort(g);
cout<<
求关键历经：
n
ToopologicalOrder(g,T);
CriticalPath(g,T);
Main
函数
创建图
拓扑排序
输出图信息
求最小路径
㈢
程序调试及运行结果分析
（
1
）在创建图的过程中需要考虑输入的方便，这就需要标记根据用户选择
是
否需要输入权值，选择不需要权值时就不会有关权值信息的操作。所以这就在图
的结构体中加
ISquan
标记（
0
表示无权值，其他表示有权值）
（
2
）
FindIndeg
ree
（）函数调用过程就是一个对邻接表遍历的过程，在遍历
过程中需要将弧指向的结点进行入度数组的标记。便定义了一个
Indegree
『』数
组。
（
3
）在求关键路径时，需要两次用到拓扑排序（其中一次是逆拓扑排
序）
，
在拓扑排序时还需要注意看看是否有环，若有环则输出提
示信息。
㈣
实验总结
通过对拓扑排序和求最小路径的操作，首先加强了对图的存储
结构和图的遍
历的进一步的熟悉和应用，在拓扑排序中还让我们去应用到以前学习的栈的
知识，
温故的同时也在实践的新的理论。
对图的应用是在生活中应用很广泛，同时图的知识点和算法也是我们这学期
学习的精
华，例如求关键路径，用到栈，拓扑排序等经典算法，让我们受益匪浅。
四、主要算法流程图及程序清单
1
、主要算法流程图：
创建图
开始
输入顶点数和边数
输入顶点信息
创建顶点向量的数组
输入弧的信息
创建了图的邻接表
结束
拓扑排序
开始
<
/p>
将入度为
0
的压入栈
栈
是
否
为空
否
弹出栈顶元素，输出结点信息并将其邻
接结点的
入度减一，入度为
0
的入栈
结束
2
、程序清单
程序过长，可附主要部分）
#include
#include
等
*/
#include
等
*/
#include
#include
#define TRUE 1
#define FALSE
0
#define OK 1
#define ERROR
0
#define INFEASIBLE -1
typedef int Status; /* Status
是函数的类型
,
其值是函数结果状态代码，如
OK
等
*/
#define INFINITY
INT_MAX
//
定义无穷大
∞
#define MAX_VERTEX_NUM
20
typedef int V
ertexType;
typedef int InfoType;
typedef
struct
ArcNode
//
表结点定义
{
InfoType info;
int
adjvex;
//
邻接点域，存放与
V
i
邻接的点在表头数组中的位置
< br>
ArcNode
*nextarc;
//
链域，指示依附于
vi
的下一条边或弧的结点，
}ArcNode;
typedef
struct
VNode
//
表头结点
{
int data;
//
存放顶点信息
struct
ArcNode
*firstarc;
//
指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
//
图的结构定义
AdjList
vertices;
//
顶点向量
int
vexnum, arcnum;
int
Isquan;//
是否含有权值
}
MGraph;
int indegree[MAX_VERTEX_NUM];
int ve[MAX_VERTEX_NUM];//e
各顶
点的最早发生时间
int vl[MAX_VERTEX_N
UM];//
各顶点发生的最晚发生时间
/*
图的邻接表存储
(
存储结构定义
)
的基本操
作
*/
int
LocateV
ex(MGraph
G
,V
ertexType u)
{
/*
初始条件
:
图
G
存在
,u
和
G
中顶点有相同特征
*/
/*
操作结果
:
若
G
中存在顶点
u,
则返回该顶点在图中位置
;
否
则返回
-1 */
int i;
-
-
-
-
-
-
-
-
-
上一篇：OBJ文件格式内幕详解
下一篇：二分法和牛顿迭代法求解方程的比较