/* 头文件：graph1.h:邻接表,中的遍历,生成树,关键路径 */int menu_netselect1(){ /* 邻接表菜单选择系统 */char s[8];int c;clrscr(); /* 清屏 */printf("\n");printf("\n");printf(" ************************************ \n");printf(" * * \n");printf(" * 邻接表结构操作窗口 *\n");printf(" * * \n");printf(" * 无向网:a1.txt; ..... i1.txt; * \n");printf(" * 有向网:a2.txt; ..... i2.txt; * \n");printf(" * 无环网:a3.txt; ..... i3.txt; * \n");printf(" * * \n");printf(" ************************************ \n");printf("\n");printf(" 01:建立邻接表(无向网)\n");printf(" 02:建立邻接表(有向网)\n");printf(" 03:输出邻接表结构\n");printf(" 04:深度遍(连通-非连通)\n");printf(" 05:广度遍(连通-非连通)\n");printf(" 06:邻接表 DFS 树\n");printf(" 07:邻接表 BFS 树\n");printf(" 08:深度遍历建生成树(无向网)\n");printf(" 09:拓扑排序(有向无环网)\n");printf(" 10:关键路径(有向无环网)\n");printf(" 11:销毁当前邻接表\n");printf(" 12:返回主窗口\n");do {printf("\n");printf(" 输入你的选择号:1---12: ");gets(s);c=atoi(s);}while(c<0||c>12);return(c);}int LocateVex1(ALGraph G,VertexType u){ /* 若G中存在顶点u，则返回该顶点在邻接表中位置；否则返回-1 */ int i;for(i=1;i<=G.vex;++i)if(strcmp(u,G.ver[i].data)==0) return i;return -1;}void DestroyGraph1(ALGraph *G){ /* 销毁图(邻接表)G */int i;LNode *p,*q;for(i=1;i<=G->vex;++i) /* 对于所有顶点 */{p=G->ver[i].first;while(p){q=p->next;free(p);p=q;}}G->vex=0; /* 顶点数为0 */G->arc=0; /* 边或弧数为0 */}void setlistunnetwork1(ALGraph *G){ /* 建立邻接表无向网 */int i,j,k,w,l=0; /* w是权值 */VertexType va,vb; /* 连接边或弧的2顶点 */LNode *p;char str[13];FILE *fp;clrscr(); /* 清屏 */printf("\n");printf("\n");printf(" ************************************ \n");printf(" * * \n");printf(" * * \n");printf(" * 邻接表(无向网)文件载入窗口 *\n");printf(" * * \n");printf(" * * \n");printf(" * * \n");printf(" ************************************ \n");printf("\n");printf("\n");printf(" 输入邻接表文件名(可带路径) : ");gets(str);fp=fopen(str,"r");while(fp==NULL){ l++;if(l==3){printf("\n");printf("\n");printf("\n");printf("\n");printf("************************************ \n");printf(" * * \n");printf(" * * \n");printf(" * 请建立图文件后存盘保存* \n");printf(" * * \n");printf(" * 选择新磁盘文件载入* \n");printf(" * * \n");printf(" * * \n");printf("************************************ \n");printf("\n");printf("\n");scanf("%*c");exit(0);}printf(" 邻接表文件 %s 不存在!\n",str);printf(" 输入邻接表文件名(可带路径) : ");gets(str);fp=fopen(str,"r");}fscanf(fp,"%d",&G->vex);fscanf(fp,"%d",&G->arc);for(i=1;i<=G->vex;i++) /* 构造顶点向量 */{fscanf(fp,"%s",G->ver[i].data);G->ver[i].first=NULL; /* 初始化与该顶点有关的出弧链表 */}for(k=1;k<=G->arc;k++) /* 构造相关弧链表 */{fscanf(fp,"%s%s%d",va,vb,&w);i=LocateVex1(*G,va); /* 起点,弧尾 */j=LocateVex1(*G,vb); /* 终点,弧头 */p=(LNode *)malloc(sizeof(LNode)); /* 有向网 */p->wig=w; /* 给待插表结点s赋值，图权 */p->adj=j; /* 弧头 */p->next=G->ver[i].first;G->ver[i].first=p;p=(LNode *)malloc(sizeof(LNode)); /* 无向网 */p->wig=w; /* 给待插表结点s赋值，图权 */p->adj=i; /* 弧头 */p->next=G->ver[j].first;G->ver[j].first=p;}printf("\n 邻接表文件 %s 装入内存成功!!!\n",str);fclose(fp); /* 关闭数据文件 */printf("\n\n");printf("\n按任意键返回..........");scanf("%*c");}void setlistnetwork1(ALGraph *G){ /* 建立邻接表有向网 */int i,j,k,w,l=0; /* w是权值 */VertexType va,vb; /* 连接边或弧的2顶点 */LNode *p;char str[13];FILE *fp;clrscr(); /* 清屏 */printf("\n");printf("\n");printf(" ************************************ \n");printf(" * * \n");printf(" * * \n");printf(" * 邻接表(有向网)文件载入窗口 *\n");printf(" * * \n");printf(" * * \n");printf(" * * \n");printf(" ************************************ \n");printf("\n");printf("\n");printf(" 输入邻接表文件名(可带路径) : ");gets(str);fp=fopen(str,"r");while(fp==NULL){ l++;if(l==3){printf("\n");printf("\n");printf("\n");printf("\n");printf("************************************ \n");printf(" * * \n");printf(" * * \n");printf(" * 请建立图文件后存盘保存* \n");printf(" * * \n");printf(" * 选择新磁盘文件载入* \n");printf(" * * \n");printf(" * * \n");printf("************************************ \n");printf("\n");printf("\n");scanf("%*c");exit(0);}printf(" 邻接表文件 %s 不存在!\n",str);printf(" 输入邻接表文件名(可带路径) : ");gets(str);fp=fopen(str,"r");}fscanf(fp,"%d",&G->vex);fscanf(fp,"%d",&G->arc);for(i=1;i<=G->vex;++i) /* 构造顶点向量 */{fscanf(fp,"%s",G->ver[i].data);G->ver[i].first=NULL; /* 初始化与该顶点有关的出弧链表 */}for(k=1;k<=G->arc;++k) /* 构造相关弧链表 */{fscanf(fp,"%s%s%d",va,vb,&w);i=LocateVex1(*G,va); /* 起点,弧尾 */j=LocateVex1(*G,vb); /* 终点,弧头 */p=(LNode *)malloc(sizeof(LNode)); /* 有向网 */p->wig=w; /* 给待插表结点s赋值，图权 */p->adj=j; /* 弧头 */p->next=G->ver[i].first;G->ver[i].first=p;}printf("\n 邻接表文件 %s 装入内存成功!!!\n",str);fclose(fp); /* 关闭数据文件 */printf("\n\n");printf("\n按任意键返回..........");scanf("%*c");}void printetwork1(ALGraph G){ /* 输出图的邻接表G */int i;Link p;printf("%d个顶点：\n",G.vex);printf("图顶点值：");for(i=1;i<=G.vex;++i)printf("[%3s]",G.ver[i].data);printf("\n");printf("图下标值：");for(i=1;i<=G.vex;++i)printf("[%3d]",i);printf("\n\n该无向图的邻接表结构:\n");printf("[下标][ 表头]→[ 结点]→[ 结点]→[ 结点]→[ 结点]→[ 结点]→[ 结点 ]\n");for(i=1;i<=G.vex;i++){printf("[%4d][ %4s ]",i,G.ver[i].data);p=G.ver[i].first;while(p!=NULL){printf("→[%2d, %2d]",p->adj,p->wig);p=p->next;}printf("\n");}printf("\n");}/*以下为无头单链表中的相关算法*/int LocateElem1(Link L,ElemTypese,int(*compare)(ElemTypes,ElemTypes)){ /* 返回L中第1个与e满足关系compare()的数据元素的位序。