姓名

学号

实验图的创建及应用（I） 项目 实验内容 1．编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接矩阵和邻接表存储结构并输出显示。（题集150页5.3扩充） 存储结构定义分别参见教材第161页和第163页。 2．试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。（题集第49页7.27） 算法设计与程序实现： 算法分析 本次实验主函数采用循环选择结构，主函数调用自己编写的头文件DataStructure_Graph.h中的相关功能函数，完成实验要求。 主程序结构： 1、邻接矩阵表示法： 1、创建有向图； //调用CreateGraph(MG)创建有向图 2、显示图信息； //调用DisplayGraph(MG) 显示图信息 3、返回上一界面； 2、邻接表表示法： 1、创建有向图； //调用CreateGraph(ALG)创建有向图 2、显示图信息；//调用DisplayGraph(ALG) 显示图信息 3、返回上一界面； 3、基于深度优先搜索判断是否存在指定位置的路径： 1、使用已创建的邻接表表示的图进行搜索判断;//调用exist_path_DFS(ALG, i, j)搜索 2、创建新的图进行搜索判断；//创建新的有向图，并调用exist_path_DFS(R_ALG, i, j)搜索 3、返回上一界面； 4、退出程序 创建图的算法分析 ? 邻接矩阵结构创建图： 首先由键盘输入待创建的图的顶点数，弧数以及是否含有弧信息，然后由顶点数控制循环构造顶点向量,接着由顶点数控制循环初始化邻接矩阵(adj=0,info=NUll)，再次输入弧信息，此时将输入的弧的弧头和弧尾与顶点信息进行匹配，从而确定弧在邻接矩阵中的位置(有弧时为1)，如果输入的弧有信息的话，在进行有无弧的判断写邻接矩阵时进行绑定，有键盘输入即可。 1

? 邻接表结构创建图： 首先由键盘输入待创建的图的顶点数，弧数，然后由顶点数控制循环初始化顶点信息(顶点数据信息及顶点第一条弧指针(firstarc = NULL)),接着由弧数控制循环输入弧头和弧尾顶点，与之前建立的顶点信息进行匹配，从而确定弧头和弧尾的位置信息，此时生成一个弧结点类型的存储空间，采用单链表中在表头插入新结点的方法，将弧的信息插入到顶点的第一条弧之后，如同此法，对每个顶点都进行以上操作，这就建立了图的邻接表结构。 深度优先搜索判断是否存在指定位置的路径算法分析 首先判断指定的两个位置向量是否相等，如果相等，则肯定有路径相连，否则从指定的弧头结点开始搜索，将该顶点访问过的弧的访问标志置1，任何到该弧的弧头顶点进行如上操作，当搜索该顶点的所有弧都没有找到则返回0，然后返回上一顶点，对该顶点的其他弧进行访问。当指定顶点的所有弧都被搜索访问过都没有找到，此时程序返回0。 核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #include \ //输入输出流库头文件 #include \ //文件操作流库头文件 #include \ //cmd窗口设置函数头文件 #include \ //数据结构中相关结构体类型定义及相关数据类型定义 #include \ //数据结构第七章图相关函数的定义及声明 using namespace std; void main_menu(void); void minor_menu1(void); void minor_menu2(void); void minor_menu3(void); int main(void) { system(\数据结构实验 实验六：图的创建及应用（I）\); //设置cmd窗口标题 system(\); //设置控制台窗口的背景色和前景色 system(\); //输出当前的日期 while (1) { main_menu(); //主菜单显示 MGraph MG; //邻接矩阵表示图 ALGraph ALG; //邻接表表示图 ALGraph &G = ALG; char ch; //主菜单输入选择 cout << \请选择功能： \; cin >> ch; switch (ch) { case '1': { system(\); while (1) { minor_menu1(); //二级菜单显示 char ch1; //二级菜单输入选择 2

} case'2': {

system(\); while (1) {

minor_menu2();

char ch1;//二层菜单输入选择 cout << endl << \请选择功能：\; cin >> ch1; switch (ch1) {

case '1'://创建图信息 { }

system(\); CreateGraph(ALG);

cout << \操作完毕！\ << endl; system(\); system(\); continue;

} break;

cout << endl << \请选择功能：\; cin >> ch1; switch (ch1) {

case '1': //创建有向图 { }

case '2': //显示图信息 { }

case '3': //返回上一界面 { } default: { } }

system(\); break;

system(\);

cout << \输入错误，请重新输入！\ << endl; continue; break; system(\); DisplayGraph(MG);

cout << \操作完毕！\ << endl; system(\); system(\); continue; system(\); CreateGraph(MG);

cout << \操作完毕！\ << endl; system(\); system(\); continue;

3