题目8：全国铁路运输网最佳经由问题 - 图文

课程设计报告

课程：学号：姓名：班级：教师：时间：（本科）

数据结构

1210441019、1210441004

1210441020

葛程、徐双双 杜明辉

2012级物联网工程班

程敏

2014.01.02

计算机科学与技术系

设计名称： 全国铁路运输网最佳经由问题 设计内容、目的与要求： 实验内容： 铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。 铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。 火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。 实验要求： （1）查询某站所属的铁路线 （2）要求具备新增铁路线的管理功能 （3）要求具备新增车站的管理功能 （4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序 计划与进度安排： 11.1 ——11.10大体规划几部分函数，设计基本的铁路图，今后在基本图上实验铁路的基本管理功能。 11.11——11.30各组员完成自己的功能函数，并尽量达到要求。 12.1——12.15 组员一起完成函数的组建及基本辅助函数功能的实现。 12.16——12.25 组员各自拿到所有的程序，开始个人调试与完善。 12.26——12.30 组员一起讨论最后的方案，并做最后的优化。 设计过程、步骤（可加页）： 一：设计过程： 将铁路网抽象成图，然后查询中国现有的铁路网结构图，选取合适的站点数目，构造一个简单的铁路图，在构造的铁路图上实现设计的要求。用结构体创建图，然后再图的基础上实现算法要求。通过对题目的分析我们觉得会用到会用到数据结构的邻接矩阵的存储图的定义，图的遍历算法（深度优先遍历），两点间最短路径查询（迪杰斯特拉算法）。使用文件的存储方式，对数据进行存储。

1

现行的铁路图： 最后简单化的铁路网如下： typedef struct { int id; char name[20]; char des[100]; }vinfo;//站点 typedef struct { int distance;

2

int kind; }ArcCell, AdjMatrix[MAX_V_NUM][MAX_V_NUM];//邻接矩阵 typedef struct { vinfo vexs[MAX_V_NUM];//站点数组 AdjMatrix arcs; int vexnum,arcnum; }MGraph;//图 主函数 客货运及两站点查询站点、铁 个站点的最介绍函数 路线的管 短路径查询理函数 函数 客货两路站 运运站线点 查查间管管 询 询 查理 理 询 二：函数的声明和调用: void welcome();//欢迎界面 void search_vex_info();//站点信息介绍 void search_rantwo_short();//查询任意两个站点之间的一条最短简单路径 void map_manage();//站点线路修改扩充 void search_two_allpath();//查询两站点间所有路径 void search_kh_path();//客货运类别路径查询 void about();//关于 void create_map();//初始化地图 void save_map();//将程序中的图结构体写入数据文件 int input_num_check(int min,int max);//数字输入检验 void shortest_path_ota(int begin);//生成某一站点到所有其它站点的最短路径数据 void print_fgx();//输出独占一行的分割线

3

void map_add_vex();//新增站点 void map_add_road();//新增道路 void map_revise_vex();//修改站点 void map_revise_road();//修改道路(引导界面) void map_reroad_in(int vid);//修改道路(公用嵌入函数) void map_delete_vex();//删除站点 void map_delete_road();//删除道路(引导界面) void map_re_arc(int bid,int fid,int kind,int xid);//修改道路(模块函数) 若修改终点:调用前需确保xid(新终点)与原终点不相同 void map_de_arc(int bid,int fid);//删除道路(模块函数) void DFS_allpath(int bid,int fid,int k);//寻找两点间所有路径并输出 void search_kh_kh(int kind);//查找所有符合类别的路径 void DFS_allpath_kh(int bid,int fid,int k,int kind);//寻找两点间所有路径并判断该路径上到道路是否全为客/货运线路 int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);//人客/货运线路 判断较长路径是否完全包含较短路径 int DFS_allpath_kh_test(int a_i,int b_i) 结果与分析（可以加页）： 4

设计体会与建议： 这次的程序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求全国铁路运输网最佳经由。但是程序较小，功能不全面，只是理论，并未实践。 经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和 5

对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。 在整个课程程序中，我们充分应用和调用各个程序模块，从而实现了此次程序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让我们感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们自主的去学习。

6

附录：

#include #include #include #include #include #include #include

#define MAX_V_NUM 100 #define MAX 60000

typedef struct {

int id; char name[20]; char des[100]; }vinfo;//站点

typedef struct { int distance; int kind;

}ArcCell, AdjMatrix[MAX_V_NUM][MAX_V_NUM];//邻接矩阵

typedef struct { vinfo vexs[MAX_V_NUM];//站点数组 AdjMatrix arcs; int vexnum,arcnum; }MGraph;//图

MGraph G;//图G

int input_exit = 0;//退出操作

//ota最短路径存储用变量

int P[MAX_V_NUM][MAX_V_NUM]; //最短路径中间点记录 int D[MAX_V_NUM]; //到各点的最短路径

int Sorder[MAX_V_NUM]; //最短路径根点由小到大排序

//路径探寻存储用变量(使用前后必须重置为0)

7

int path[MAX_V_NUM]; //路径站点 int visited[MAX_V_NUM]; //访问标志 int path_num; //所有路径数 int best_l; //目前最短的总长度

int bestl_num; //目前总长度最短的路径途经站点个数

//客运货运路径函数用存储数组

int path_kh[MAX_V_NUM][MAX_V_NUM];//存储暂时满足条件的客货运路径 int path_kh_vnum[MAX_V_NUM];//记录每条路径途经的站点数 int path_num_bak;//备份所有路径数

/**************************************** 函数声明

****************************************/

void welcome();//欢迎界面

void search_vex_info();//站点信息介绍

void search_rantwo_short();//查询任意两个站点之间的一条最短简单路径 void map_manage();//站点线路修改扩充

//void search_two_allpath();//查询两站点间所有路径 void search_kh_path();//客货运类别路径查询

void create_map();//初始化地图

void save_map();//将程序中的图结构体写入数据文件 int input_num_check(int min,int max);//数字输入检验

void shortest_path_ota(int begin);//生成某一站点到所有其它站点的最短路径数据 void print_fgx();//输出独占一行的分割线 void map_add_vex();//新增站点 void map_add_road();//新增道路 void map_revise_vex();//修改站点

void map_revise_road();//修改道路(引导界面)

void map_reroad_in(int vid);//修改道路(公用嵌入函数) void map_delete_vex();//删除站点

void map_delete_road();//删除道路(引导界面)

void map_re_arc(int bid,int fid,int kind,int xid);//修改道路(模块函数) 若修改终点:调用前需确保xid(新终点)与原终点不相同

void map_de_arc(int bid,int fid);//删除道路(模块函数)

void DFS_allpath(int bid,int fid,int k);//寻找两点间所有路径并输出 void search_kh_kh(int kind);//查找所有符合类别的路径

void DFS_allpath_kh(int bid,int fid,int k,int kind);//寻找两点间所有路径并判断该路径上到道路是否全为客/货运线路

int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);//人客/货运线路 判断较长路径是否完全包含较短路径

8

int DFS_allpath_kh_test(int a_i,int b_i);//输出前检测 判断较长路径是否完全包含较短路径

void main() { int step = -1,choose = 1; create_map(); do { welcome(); printf(\请输入功能序号:\ step = input_num_check(0,3); if(input_exit == 1) { input_exit = 0; step = -1; choose = 0; } else { switch(step) { case 1:search_vex_info();break; case 2:map_manage();break; case 3:search_kh_path();break; default:choose = 0; } } }while(choose != 0); printf(\您已成功退出,欢迎下次使用,再见!\\n[按任意键关闭窗口]\ getch();//在你需要暂停的位置暂停一下，当你按一下任意键它又会继续往下执行！ }

void welcome() { int i; printf(\ printf(\ \\n\ printf(\ 全国铁路网最佳经由系统 \\n\

9

printf(\ \\n\ printf(\ <功能选择列表> \\n\ printf(\ 1.站点介绍查询 \\n\ printf(\ 2.站点道路修改扩充 \\n\ printf(\ 3.客货查询 \\n\ printf(\ 0.退出系统 \\n\ printf(\ \\n\ printf(\// printf(\共有%d个站点 %d条道路 [最大值MAX为%d 最多%d个顶点]\.vexnum,G.arcnum,MAX,MAX_V_NUM); print_fgx(); printf(\可供查询的站点:\\n\ for(i=0;i

void search_vex_info() { int vid; do { printf(\请输入站点ID(e:退出):\ vid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ return; } print_fgx(); printf(\站点【%s】介绍:%s\.vexs[vid].name,G.vexs[vid].des); print_fgx(); }while(1); }

10

void search_rantwo_short() { int bid,fid,i,j; do { printf(\请输入起点ID(e:退出):\ bid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ return; } printf(\请输入终点ID(e:退出):\ fid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ return; } shortest_path_ota(bid); print_fgx(); printf(\【%d】%s 到 【%d】%s 的最径:\.vexs[bid].name,G.vexs[fid].id,G.vexs[fid].name); print_fgx(); for(i=0;i\.vexs[j].name); } printf(\全程共%dkm\ print_fgx(); }while(1); }

void map_manage() {

短路11

int select; do { printf(\新增站点 2.新增线路 3.修改站点 4.修改线路 5.删除站点 6.删除线路 e:退出)\\n请输入操作编号:\ select = input_num_check(1,6); if(input_exit == 1) { input_exit = 0; system(\ return; } switch(select) { case 1:map_add_vex();break; case 2:map_add_road();break; case 3:map_revise_vex();break; case 4:map_revise_road();break; case 5:map_delete_vex();break; case 6:map_delete_road();break; default:exit(1); } }while(1); }

void search_kh_path() { int select; int sign=0; do { printf(\货运 2.客运 3两站间最短路径查询 e:退出)\\n请输入操作编号:\ select = input_num_check(1,3); if(input_exit == 1) { input_exit = 0; system(\ return; } switch(select)

12

{ case 1:search_kh_kh(1);break; case 2:search_kh_kh(2);break; case 3:search_rantwo_short();break; default:exit(1); } }while(1); }

//初始化地图 void create_map() { if(access(\ { FILE *fp; fp = fopen(\ if(!fp) { printf(\数据文件打开失败!\\n\ } fread(&G,sizeof(MGraph),1,fp); fclose(fp); } else { int i,j; //站点数与道路数赋值 G.vexnum = 16; G.arcnum = 20; //站点编号赋值 for(i=0;i

13

strcpy(G.vexs[8].name,\九龙站\strcpy(G.vexs[9].name,\包头站\

strcpy(G.vexs[10].name,\乌鲁木齐站\strcpy(G.vexs[11].name,\兰州站\strcpy(G.vexs[12].name,\宝鸡站\strcpy(G.vexs[13].name,\成都站\strcpy(G.vexs[14].name,\昆明站\strcpy(G.vexs[15].name,\贵阳\

//站点介绍赋值

strcpy(G.vexs[0].des,\京广线、京九线、京哈线等、\strcpy(G.vexs[1].des,\京广线\strcpy(G.vexs[2].des,\京广线\strcpy(G.vexs[3].des,\京广线\strcpy(G.vexs[4].des,\有待补充\strcpy(G.vexs[5].des,\有待补充\strcpy(G.vexs[6].des,\有待补充\strcpy(G.vexs[7].des,\京九线\strcpy(G.vexs[8].des,\京九线\strcpy(G.vexs[9].des,\京包线\strcpy(G.vexs[10].des,\有待补充\strcpy(G.vexs[11].des,\有待补充\strcpy(G.vexs[12].des,\有待补充\strcpy(G.vexs[13].des,\有待补充\strcpy(G.vexs[14].des,\有待补充\strcpy(G.vexs[15].des,\有待补充\

for(i=0;i

G.arcs[0][1].distance=300;G.arcs[0][1].kind=1; G.arcs[0][4].distance=100;G.arcs[0][4].kind=2; G.arcs[0][9].distance=300;G.arcs[0][9].kind=2; G.arcs[1][5].distance=400;G.arcs[1][5].kind=1; G.arcs[1][12].distance=200;G.arcs[1][12].kind=1; G.arcs[1][2].distance=300;G.arcs[1][2].kind=1; G.arcs[2][3].distance=400;G.arcs[2][3].kind=1; G.arcs[2][7].distance=300;G.arcs[2][7].kind=2; G.arcs[2][15].distance=250;G.arcs[2][15].kind=2; G.arcs[4][5].distance=200;G.arcs[4][5].kind=2; G.arcs[5][6].distance=300;G.arcs[5][6].kind=2; G.arcs[6][7].distance=200;G.arcs[6][7].kind=2; G.arcs[7][8].distance=500;G.arcs[7][8].kind=2; G.arcs[9][11].distance=350;G.arcs[9][11].kind=2;

14

G.arcs[10][11].distance=800;G.arcs[10][11].kind=1; G.arcs[11][12].distance=200;G.arcs[11][12].kind=1; G.arcs[12][13].distance=300;G.arcs[12][13].kind=2; G.arcs[13][14].distance=200;G.arcs[13][14].kind=2; G.arcs[14][15].distance=350;G.arcs[14][15].kind=2; for(i=0;ij) G.arcs[i][j] = G.arcs[j][i]; save_map(); } }

//将程序中的图结构体写入数据文件 void save_map() { FILE *fp; fp = fopen(\ if(!fp) { printf(\数据文件打开失败!\\n\ } fwrite(&G,sizeof(MGraph),1,fp); fclose(fp); }

//数字输入检验

int input_num_check(int min,int max) { int id,isright=0; do { scanf(\ if(id<=max && id>=min) isright = 1; else { if(getchar() == 'e') { input_exit = 1; return 0; }

15

printf(\输入有误,请重新输入(e:退出):\ } }while(isright != 1); return id; }

void print_fgx() { printf(\}

void shortest_path_ota(int begin) { //Dijkstra(迪杰斯特拉)算法

int i,k=0,v,w,final[MAX_V_NUM],min,m; //初始化 for(v=0;v

16

D[w] = min + G.arcs[v][w].distance; for(m=0;m

void DFS_allpath(int bid,int fid,int k) { int i,j; if(path[k] == fid) { for(i=0;i\.vexs[path[i]].id,G.vexs[path[i]].name); } printf(\【%d】%s\.vexs[path[k]].id,G.vexs[path[k]].name); print_fgx(); path_num++; } else { for(j=0;j

void map_add_vex() { int vid=G.vexnum; int ifgo,order,nearid,newroad=0; do { if(vid>=MAX_V_NUM) {

17

printf(\站点数已达到最大值%d,按任意键返回!\ getchar(); getchar(); system(\ welcome(); return; } printf(\新站点的编号为【%d】,是否继续?(1.继续 e:退出):\ ifgo = input_num_check(1,1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } G.vexs[vid].id = vid; printf(\请输入新站点的名称:\ scanf(\.vexs[vid].name); printf(\请输入新站点的介绍:\ scanf(\.vexs[vid].des); printf(\添加站点成功!\ print_fgx(); G.vexnum++; G.arcnum+=newroad; save_map(); vid++; }while(1); }

void map_add_road() { int bid,fid; do { printf(\请输入新增道路起始站点ID(e:退出):\ bid = input_num_check(0,G.vexnum-1); if(input_exit == 1) {

18

input_exit = 0; system(\ welcome(); return; } printf(\请输入新增道路终止站点ID(e:退出):\ fid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } if(fid == bid) { printf(\终点与起点重复!\\n\ continue; } if(G.arcs[bid][fid].distance

%s ->

19

void map_revise_vex() { int vid,choose,i; do { printf(\请输入需要修改的站点ID(e:退出):\ vid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } print_fgx(); printf(\站点信息预览:【%d】%s 介绍:%s \\n\.vexs[vid].id,G.vexs[vid].name,G.vexs[vid].des); print_fgx(); for(i=0;i【%d】%s 道路信息:[长度] %dkm \.vexs[i].id,G.vexs[i].name,G.arcs[vid][i].distance); if(G.arcs[vid][i].kind == 1) printf(\类型] 货运\ else printf(\类型] 客运\ print_fgx(); } printf(\请输入需要修改的对象(1.名称 2.信息 3.线路):\ scanf(\ if(choose == 1) { printf(\请输入新的站点名称:\ scanf(\.vexs[vid].name); } else if(choose == 2) { printf(\请输入新的站点信息:\ scanf(\.vexs[vid].des); } else if(choose == 3) {

20

map_reroad_in(vid); } else { printf(\输入错误!\\n\ continue; } save_map(); print_fgx(); printf(\修改成功!\\n\ }while(1); }

//修改道路(引导界面) void map_revise_road() { int vid; do { printf(\请输入需要修改的道路的起点(e:退出):\ vid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } map_reroad_in(vid); save_map(); print_fgx(); printf(\修改成功!\\n\ }while(1); }

//修改道路

void map_reroad_in(int vid) { int fid,ekind,pass=0,passt=1;

21

do { printf(\请输入需要修改的道路的终点(e:退出):\ fid = input_num_check(0,G.vexnum-1); if(input_exit == 1) input_exit = 0; else if(G.arcs[vid][fid].distance == MAX || fid == vid) printf(\道路不存在或端点重复!\\n\ else pass = 1; }while(pass != 1); if(pass == 1) pass = 0; do { printf(\您需要修改线路【%d】%s ->【%d】%s 的\\n(1.终点 2.长度 3.类型):\.vexs[vid].id,G.vexs[vid].name,G.vexs[fid].id,G.vexs[fid].name); scanf(\ if(ekind == 1) { int xid; do { printf(\请输入道路的新终点:\ xid = input_num_check(0,G.vexnum-1); if(input_exit == 1) input_exit = 0; else if(G.arcs[vid][xid].distance < MAX || xid == vid) printf(\新道路已存在或端点重复!\\n\ else pass = 1; }while(pass != 1); map_re_arc(vid,fid,3,xid); } else if(ekind == 2) { map_re_arc(vid,fid,1,-1); } else if(ekind == 3) { map_re_arc(vid,fid,2,-1); } else

22

{ printf(\输入错误!\\n\ passt = 0; } }while(passt == 0); }

//删除站点

void map_delete_vex() {

int vid,i; do { printf(\请输入需要删除的站点编号(e:退出):\ vid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } print_fgx(); printf(\站点信息预览:【%d】%s 信息:%s \\n\.vexs[vid].id,G.vexs[vid].name,G.vexs[vid].des); print_fgx(); for(i=0;i【%d】%s 道路信息:[长度] %dkm \.vexs[i].id,G.vexs[i].name,G.arcs[vid][i].distance); if(G.arcs[vid][i].kind == 1) printf(\类型] 货运\ else printf(\类型] 客运\ print_fgx(); } printf(\按任意键确认删除(按e退出):\\n\ if(getch() == 'e') { system(\ welcome(); return;

23

} else { //删除顶点向量(用编号最大的顶点覆盖) G.vexs[vid] = G.vexs[G.vexnum-1]; G.vexs[vid].id = vid; //编号最大顶点清空 strcpy(G.vexs[G.vexnum-1].name,\ strcpy(G.vexs[G.vexnum-1].des,\ //删除与已删除顶点相连的边 for(i=0;i

void map_delete_road() { int bid,fid,pass; do { pass = 0; printf(\请输入需要删除的道路的起点(e:退出):\

24

bid = input_num_check(0,G.vexnum-1); if(input_exit == 1) { input_exit = 0; system(\ welcome(); return; } do { printf(\请输入需要删除的道路的终点:\ fid = input_num_check(0,G.vexnum-1); if(input_exit == 1) input_exit = 0; else if(G.arcs[bid][fid].distance == MAX || fid == bid) printf(\道路不存在或端点重复!\\n\ else pass = 1; }while(pass != 1); map_de_arc(bid,fid); }while(1); }

void map_re_arc(int bid,int fid,int kind,int xid) { if(G.arcs[bid][fid].distance == MAX) { printf(\无此道路!\ exit(1); } if(kind == 1) //修改长度 { printf(\原始值:%dkm \\n请输入新长度值（km）:\ scanf(\.arcs[bid][fid].distance); G.arcs[fid][bid] = G.arcs[bid][fid]; } else if(kind == 2) //修改类型 { printf(\原值:%d 请输入新类型值(0.人行道 1.车行道):\.arcs[bid][fid].kind); scanf(\.arcs[bid][fid].kind); G.arcs[fid][bid] = G.arcs[bid][fid];

25

} else if(kind == 3) //修改终点(道路长度、类型、等级信息直接复制过去) { if(bid == fid || bid == xid || fid == xid) { printf(\错误:起点、旧终点、新终点三者中有两者相同!\\n\ return; } else { G.arcs[bid][xid] = G.arcs[bid][fid]; G.arcs[bid][fid].distance = MAX; G.arcs[fid][bid].distance = MAX; G.arcs[xid][bid] = G.arcs[bid][xid]; } } else { printf(\发生错误!\ exit(1); } save_map(); printf(\修改成功!\\n\}

//删除道路(模块函数)

void map_de_arc(int bid,int fid) { printf(\正在删除道路【%d】【%d】%s...\\n\.vexs[fid].id,G.vexs[fid].name); G.arcs[bid][fid].distance = MAX; G.arcs[fid][bid].distance = MAX; G.arcnum--; save_map(); printf(\删除成功!\\n\}

void search_kh_kh(int kind) {

%s->26

int i,j,c,u; for(c=0;c

27

if(path_kh_vnum[i] \.vexs[path_kh[i][j]].name); printf(\【%d】%s\.vexs[path_kh[i][j]].id,G.vexs[path_kh[i][j]].name); print_fgx(); } } for(c=0;c

//输出前检测 判断较长路径是否完全包含较短路径

int DFS_allpath_kh_test(int a_i,int b_i) //[a_i]:较短路径的i值 [b_i]:较长路径的i值 { int m,i,l_num,s_num,l_road[MAX_V_NUM],s_road[MAX_V_NUM],match=0,first;

28

//赋值两种路径各自的信息 l_num = path_kh_vnum[b_i]; s_num = path_kh_vnum[a_i]; for(m=0;m

//寻找两点间所有路径并判断该路径上到道路是否全为要求类型void DFS_allpath_kh(int bid,int fid,int k,int kind) {

29

int i,j,x_c,y_c; if(path_num>=MAX_V_NUM) return; if(path[k] == fid) { int match=1; if(k>1) //道路数至少两条 { //判断是否全是人/车行道 for(i=1;i<=k;i++) if(G.arcs[path[i-1]][path[i]].kind != kind) { match = 0; break; } if(match == 1) { int m,can_stop=0,can_go=0,is_include; if(path_num == 0)//如果全局路径数组里没有路径 { for(m=0;m<=k;m++) path_kh[0][m] = path[m]; path_kh_vnum[0] = k+1; path_num++; } else { for(i=0;i

30

if(can_go != 1)//path数组作为新路径覆盖 { for(m=0;m

31

该条路径顶点数 path_num++; } }//end if }//end if }//end if } else { for(j=0;j

//类别判断较长路径是否完全包含较短路径

int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind) //[bz_i]:当前进行比较的标准数组的i值 [pa_k]:path数组的k值 [kind]:较长(0:标准路径 1.path路径) { int m,i,l_num,s_num,l_road[MAX_V_NUM],s_road[MAX_V_NUM],match=0,first; //赋值两种路径各自的信息 if(kind == 0) { l_num = path_kh_vnum[bz_i]; s_num = pa_k+1; for(m=0;m

32

}

//判断较长路径中包含较短路径顶点的个数 for(m=0;m

else return 0;

}

33

本文来源：https://www.bwwdw.com/article/crug.html