图应用实验报告.doc

文档介绍：图应用实验报告
图应用实验报告
1/12
图应用实验报告
实验六图的应用及其实现
一、实验目的
1．进一步功固图常用的储藏构造。
2．熟练掌握在图的毗邻表实现图的基本操作base;
=25;
returnOK;
}
intindegree[MAX_VERTEX_NUM];
intve[MAX_VERTEX_NUM];//e
各极点的最早发生时间
intvl[MAX_VERTEX_NUM];//
各极点发生的最晚发生时间
调用的函数
StatusInitstack(Sqstack&s)
StatusPop(Sqstack&s,int&e)
若栈不空，则删除S的栈顶元素，
用e返回其值，并返回OK；不然返回ERRORintPush(Sqstack&s,int&e)
intStackEmpty(Sqstacks)//若栈为空栈，则返回TRUE,不然返回FLASE
StatusCreateGraph(MGraph&G)
voidDisplay(MGraph&G)/*输出图G的信息*/
voidFindDegree(MGraphg,intindegree[])//对=图中的各个极点的入度进行统计，并
将第i
//个极点的入度数放入indegree[i]
intLocateVex(MGraphG,VertexTypeu)
/*初始条件:图G存在,u和G中极点有同样特点*/
/*操作结果:若G中存在极点u,则返回该极点在图中地址;不然返回-1*/
StatusToopologicalSort(MGraphg)//对图进行拓扑排序，并输出拓扑排序的结果
StatusToopologicalOrder(MGraphg,Sqstack&T)//拓扑序列
StatusCriticalPath(MGraphg,SqstackT)//重点路径
图应用实验报告
图应用实验报告
16/12
图应用实验报告
㈡、函数调用及主函数设计（可用函数的调用关系图说明）
图应用实验报告
图应用实验报告
12/12
图应用实验报告
voidmain()
{
MGraphg;
SqstackT;
Main函数
cout<<"创办图:\n";
CreateGraph(g);
创办图
cout<<"输出图的信息:\n";
Display(g);
cout<<"拓扑排序:\n";
ToopologicalSort(g);
拓扑排序
输出图信息
求最小道径
cout<<"求重点历经：\n";
ToopologicalOrder(g,T);
CriticalPath(g,T);
}
㈢程序调试及运转结果解析
（1）在创办图的过程中需要考虑输入的方便，这就需要标志依据用户选择是
否需要输入权值，选择不需要权值时就不会相关权值信息的操作。因此这就在图
的构造体中加ISquan标志（0表示无权值，其余表示有权值）
（2）FindIndegree（）函数调用过程就是一个对毗邻表遍历的过程，在遍历
过程中需要将弧指向的结点进行入度数组的标志。便定义了一个
Indegree『』数
组。
（3）在求重点路径时，需要两次用到拓扑排序（此中一次是逆拓扑排序）
，
在拓扑排序时还需要注意看看可否有环，如有环则输出提示信息。
㈣实验总结
经过对拓扑排序和求最小道径的操作，第一增强了对图的储藏构造和图的遍历的进一步的熟****和应用，在拓扑排序中还让我们去应用到以前学****的栈的知识，温故的同时也在实践的新的理论。
对图的应用是在生活中应用很广泛，同时图的知识点和算法也是我们这学期学****的精华，比方求重点路径，用到栈，拓扑排序等经典算法，让我们得益匪浅。
四、主要算法流程图及程序清单
1、主要算法流程图：
图应用实验报告
图应用实验报告
18/12
图应用实验报告
创办图拓扑排序
图应用实验报告
图应用实验报告
19/12
图应用实验报告
开始
输入极点数和边数
输入极