实验报告实验六图的应用及其实现一、实验目的1．进一步功固图常用的存储结构。

2．熟练掌握在图的邻接表实现图的基本操作。

3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。

二、实验内容一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。

[题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。

试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。

测试数据：教材图7.29【题目五】连通OR 不连通描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作：D x y 从原图中删除连接x，y节点的边。

Q x y 询问x，y节点是否连通输入第一行两个数n,m（5<=n<=40000,1<=m<=100000）接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。

保证没有重复的边。

接下来一行一个整数 q（q<=100000）以下q行每行一种操作，保证不会有非法删除。

输出按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D样例输入3 31 21 32 35Q 1 2D 1 2Q 1 2D 3 2Q 1 2样例输出CCD【题目六】 Sort ProblemAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.【Input】Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.【Output】For each problem instance, output consists of one line. This line should be one of the following three:Sorted sequence determined: y y y… y.Sorted sequence cannot be determined.Inconsistency found.y y y… y is the sorted, ascending sequence.Sample Input Sample Output4 6 Sorted sequence determined: A B C D. A<B Inconsistency found.A<C Sorted sequence cannot be determined. B<CC<DB<DA<B3 2A<BB<A26 2A<ZD<S0 0设计要求：1、上机前，认真学习教材，熟练掌握AOV网、AOE网的构造和拓扑排序算法。

2、上机前，认真独立地写出本次程序清单，流程图，该程序包括图类型以及每一种操作的具体的函数定义和主函数。

有关算法分别参阅讲义和参考教材事例三、实验步骤㈠、数据结构与核心算法的设计描述#define MAX_VERTEX_NUM 20//变量声明typedef struct ArcNode//弧结点定义{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;}ArcNode;typedef struct VNode//顶点结点定义{char data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图的定义{AdjList vertices;int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的种类标志}ALGraph;ALGraph G; //定义图变量bool visited[MAX_VERTEX_NUM]; //访问标志数组int indegree[MAX_VERTEX_NUM]；//入度数组struct Stack//栈类型定义{int s[21];int top;};Stack stack;//定义一个栈相关函数声明：void CreateGraph(MGraph &G)// 输入图的顶点和边的信息,建立图void DFSTraverse(Graph G, int v)//深度优先搜索遍历图void BFSTraverse(Graph G, int v)//广度优先搜索遍历图int LocateVertices(ALGraph G,char a)//查找字符a在图中的位置int FirstAdjVex(ALGraph G,int v)//查找图中位置v的第一个邻接点在图中所在的位置int NextAdjVex(ALGraph G,int v,int w)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置void DestroyGraph(ALGraph &G)//销毁图void InitStack(Stack &stack)//初始化栈void PushStack(Stack &stack,int i)//元素i入栈void PopStack(Stack &stack,int &i)//栈顶元素出栈int StackEmpty(Stack stack)//判断栈是否为空，若为空则返回1，否则返回0void FindInDegree(ALGraph G,int *indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]int TopologicalSort(ALGraph G)//对图进行拓扑排序，并输出相应的拓扑序列㈡、函数调用及主函数设计㈢程序调试及运行结果分析由于以前已经做过了关于图的一些算法设计，例如：图的深度优先遍历，广度优先遍历等，因此，这次试验基本没有什么错误。

㈣实验总结这次的实验使得我对图的定义及其更多的操作有了更深入的了解，运用起来更加地熟练，掌握了拓扑排序的书写，利用栈实现图的拓扑排序的算法与分析问题的能力，让我能够对以前的知识有所复习，例如：栈的使用。

对以前的知识有了更深入的理解，例如：图的数据结构及算法实现，图的存储结构。

这是我收获最大的地方。

四、主要算法流程图及程序清单1、主要算法流程图：查找相对于图中位置v的邻接点w的下一邻接点在图中的位置int NextAdjVex(ALGraph G,int v,int w)利用邻接有向图voidCreateGraph(ALGraph &G)否是查找图中位置v的第一个邻接点在图中所在的位置int FirstAdjVex(ALGraph G,int v)对图进行拓扑排序，并输出相应的拓扑序列#include<iostream.h>#include<stdlib.h>#define MAX_VERTEX_NUM 20typedef struct ArcNode//弧结点定义{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;}ArcNode;typedef struct VNode//顶点结点定义{char data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图的定义{AdjList vertices;int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的种类标志}ALGraph;ALGraph G; //定义图变量bool visited[MAX_VERTEX_NUM]; //访问标志数组int indegree[20]; //各结点入度数组struct Stack//栈类型定义{int s[21];int top;};Stack stack; //定义一个栈int LocateVertices(ALGraph G,char a)//查找字符a在图中的位置{for(int i=0;i<G.vexnum;i++)if(G.vertices[i].data==a)return i;return -1;}void CreateGraph(ALGraph &G)//利用邻接表存储结构构造有向图{int a,b;char s;ArcNode *p;cout<<endl<<"现在要构造一个有向图"<<endl;cout<<"请输入顶点个数和图中弧的个数"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<<endl;for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"请输入图中各个弧"<<endl<<"（每一个弧用其所依附的两个顶点值表示，先输入弧尾顶点值，再输入弧头顶点值）"<<endl;for(i=1;i<=G.arcnum;i++){cin>>s;a=LocateVertices(G,s);cin>>s;b=LocateVertices(G,s);p=new ArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}int FirstAdjVex(ALGraph G,int v)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;return -1;}int NextAdjVex(ALGraph G,int v,int w)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置{ArcNode *p;p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc;if(p->nextarc)return p->nextarc->adjvex;return -1;}void DestroyGraph(ALGraph &G)//销毁图{ArcNode *p,*p1;for(int i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){delete p;p=p1;if(p1)p1=p1->nextarc;}}}void InitStack(Stack &stack)//初始化栈{stack.top=0;}void PushStack(Stack &stack,int i)//元素i入栈{stack.s[stack.top++]=i;}void PopStack(Stack &stack,int &i)//栈顶元素出栈{i=stack.s[--stack.top];}int StackEmpty(Stack stack)//判断栈是否为空，若为空则返回1，否则返回0{if(!stack.top)return 1;return 0;}void FindInDegree(ALGraph G,int *indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[] {ArcNode *p;for(int i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}int TopologicalSort(ALGraph G)//对图进行拓扑排序，并输出相应的拓扑序列{int count=0,w;FindInDegree(G,indegree);for(int i=0;i<G.vexnum;i++)if(!indegree[i])PushStack(stack,i);while(!StackEmpty(stack)){PopStack(stack,i);cout<<G.vertices[i].data<<" ";count++;for(w=FirstAdjVex(G,i);w>=0;w=NextAdjVex(G,i,w)) if(!(--indegree[w]))PushStack(stack,w);}if(count<G.vexnum)return -1;return 1;}void main(){CreateGraph(G);cout<<endl<<"拓扑排序的结果如下："<<endl;if(!TopologicalSort(G))cout<<"图中存在有环"<<endl;cout<<endl;DestroyGraph(G);}题目二：#include<iostream.h>#include<stdlib.h>#define MAX_VERTEX_NUM 20typedef struct ArcNode//弧结点定义{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针int info;}ArcNode;typedef struct VNode//顶点结点定义{char data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图的定义{AdjList vertices;int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的种类标志}ALGraph;ALGraph G; //定义图变量bool visited[MAX_VERTEX_NUM]; //访问标志数组int indegree[20]; //各结点入度数组int ve[20]; //定义顶点最早开始时间存储数组int vl[20]; //定义顶点最迟开始时间存储数组struct Stack//栈类型定义{int s[21];int top;};Stack stack; //定义一个栈，用于拓扑排序时存储入度为0的顶点Stack stack1; //存储逆拓扑排序有序序列Stack stack2; //存储关键路径int LocateVertices(ALGraph G,char a)//查找字符a在图中的位置{for(int i=0;i<G.vexnum;i++)if(G.vertices[i].data==a)return i;return -1;}void CreateGraph(ALGraph &G)//利用邻接表存储结构构造有向图{int a,b;char s;ArcNode *p;cout<<endl<<"现在要构造一个有向图"<<endl;cout<<"请输入顶点个数和图中弧的个数"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<<endl;for(int i=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"请输入图中各个弧"<<endl<<"（每一个弧用其所依附的两个顶点值表示，先输入弧尾顶点值，再输入弧头顶点值）"<<endl;for(i=1;i<=G.arcnum;i++){cin>>s;a=LocateVertices(G,s);cin>>s;b=LocateVertices(G,s);p=new ArcNode;if(!p)return;p->adjvex=b;cout<<"请输入该弧的长度"<<endl;cin>>p->info;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}void DestroyGraph(ALGraph &G)//销毁图{ArcNode *p,*p1;for(int i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){delete p;p=p1;if(p1)p1=p1->nextarc;}}}void InitStack(Stack &stack)//初始化栈{stack.top=0;}void PushStack(Stack &stack,int i)//元素i入栈{stack.s[stack.top++]=i;}void PopStack(Stack &stack,int &i)//栈顶元素出栈{i=stack.s[--stack.top];}int StackEmpty(Stack stack)//判断栈是否为空，若为空则返回1，否则返回0 {if(!stack.top)return 1;return 0;}int GetTopStack(Stack stack)//获得栈顶元素{return stack.s[stack.top-1];}void FindInDegree(ALGraph G,int *indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]{ArcNode *p;for(int i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}int TopologicalSort(ALGraph G)//对图进行拓扑排序，并输出相应的拓扑序列{int count=0;ArcNode *p;FindInDegree(G,indegree);InitStack(stack);InitStack(stack1);for(int i=0;i<G.vexnum;i++)ve[i]=0;for(i=0;i<G.vexnum;i++)if(!indegree[i])PushStack(stack,i);while(!StackEmpty(stack)){PopStack(stack,i);PushStack(stack1,i);count++;for(p=G.vertices[i].firstarc;p;p=p->nextarc){if(!(--indegree[p->adjvex]))PushStack(stack,p->adjvex);if(ve[i]+p->info>ve[p->adjvex])ve[p->adjvex]=ve[i]+p->info;}}if(count<G.vexnum)return -1;return 1;}int CriticalPath(ALGraph G)//求关键活动，并输出所有活动，关键活动用*标志，同时获得关键路径的逆序序列{char tag;int j,sum=0;ArcNode *p;InitStack(stack2);PushStack(stack2,0);if(TopologicalSort(G)==-1)return -1;for(int i=0;i<G.vexnum;i++)vl[i]=ve[G.vexnum-1];while(!StackEmpty(stack1))for(PopStack(stack1,j),p=G.vertices[j].firstarc;p;p=p->nextarc) if(vl[p->adjvex]-p->info<vl[j])vl[j]=vl[p->adjvex]-p->info;for(j=0;j<G.vexnum;j++)for(p=G.vertices[j].firstarc;p;p=p->nextarc){tag=(ve[j]==vl[p->adjvex]-p->info)?'*':' ';cout<<G.vertices[j].data<<""<<G.vertices[p->adjvex].data<<" "<<p->info<<" "<<ve[j]<<" "<<vl[p->adjvex]-p->adjvex<<" "<<tag<<endl;if(j==GetTopStack(stack2)&&tag=='*'){PushStack(stack2,p->adjvex);sum+=p->info;}}cout<<endl<<"关键路径的长度为："<<sum<<endl;return 1;}void main(){CreateGraph(G);CriticalPath(G);cout<<"该图其中之一的关键路径为："<<endl;int i;while(!StackEmpty(stack2)){PopStack(stack2,i);cout<<G.vertices[i].data<<" ";}cout<<endl;DestroyGraph(G);}题目五：#include<iostream.h>#include<stdlib.h>#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;}ArcNode;typedef struct VNode{char data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的种类标志}ALGraph;ALGraph G; //定义图变量bool visited[MAX_VERTEX_NUM]; //访问标志数组int num=0;bool found=false;int LocateVertices(ALGraph G,char a)//查找字符a在图中的位置{for(int i=0;i<G.vexnum;i++)if(G.vertices[i].data==a)return i;return -1;}int LocateArc(ALGraph G,char a,char b)//判断弧ab是否已经存在于图中，若已经存在则返回1，否则返回0 {ArcNode *p;if(LocateVertices(G,a)>=0){p=G.vertices[LocateVertices(G,a)].firstarc;while(p&&p->adjvex!=LocateVertices(G,b))p=p->nextarc;if(p)return 1;return 0;}return 0;}void CreateGraph(ALGraph &G)//利用邻接表存储结构构造有向图{int a,b;char s1,s2;ArcNode *p;for(int i=0;i<G.vexnum;i++){G.vertices[i].data='#';G.vertices[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cin>>s1;a=LocateVertices(G,s1);if(a<0){num++;G.vertices[num-1].data=s1;a=LocateVertices(G,s1);}cin>>s2;b=LocateVertices(G,s2);if(b<0){num++;G.vertices[num-1].data=s2;b=LocateVertices(G,s2);}if(!LocateArc(G,s1,s2)){p=new ArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;p=new ArcNode;if(!p)return;p->adjvex=a;p->nextarc=G.vertices[b].firstarc;G.vertices[b].firstarc=p;}}}int FirstAdjVex(ALGraph G,int v)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;return -1;}int NextAdjVex(ALGraph G,int v,int w)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置{ArcNode *p;p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc;if(p->nextarc)return p->nextarc->adjvex;return -1;}void DestroyGraph(ALGraph &G)//销毁图{ArcNode *p,*p1;for(int i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){delete p;p=p1;if(p1)p1=p1->nextarc;}}}void DFSearch(ALGraph G,int i,int s)//查找i与s之间是否有路径，以此来判断二者是否连通，若连通found=true，否则found=false{int w;// for(int x=0;x<G.vexnum;x++)// visited[x]=false;visited[i]=true;for(w=FirstAdjVex(G,i);w>=0&&!found;w=NextAdjVex(G,i,w) ){if(w==s){found=true;visited[s]=true;}else if(!visited[w])DFSearch(G,w,s);}}void DeleteArc(ALGraph &G,char a,char b)//删除有向边ab{ArcNode *p,*p1;if(LocateVertices(G,a)>=0){p1=G.vertices[LocateVertices(G,a)].firstarc;while(p1&&p1->adjvex!=LocateVertices(G,b)){p=p1;p1=p1->nextarc;}if(!p1)return;if(p1==G.vertices[LocateVertices(G,a)].firstarc){G.vertices[LocateVertices(G,a)].firstarc=p1->nextarc;free(p1);}else{p->nextarc=p1->nextarc;free(p1);}}return;}void main(){char a,b,k;int n;cin>>G.vexnum>>G.arcnum;CreateGraph(G);cin>>n;for(int i=1;i<=n;i++){found=false;cin>>k;switch(k){case 'Q':cin>>a>>b;int x;for(x=0;x<G.vexnum;x++)visited[x]=false;DFSearch(G,LocateVertices(G,a),LocateVertices(G,b));if(found){cout<<"C"<<endl;}else{cout<<"D"<<endl;}break;case 'D':cin>>a>>b;DeleteArc(G,a,b);DeleteArc(G,b,a);break;default:cout<<"输入有误"<<endl;break;}}DestroyGraph(G);}题目六：#include<iostream.h>#include<stdlib.h>#define MAX_VERTEX_NUM 28typedef struct ArcNode//弧结点定义{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针//InfoType *info;}ArcNode;typedef struct VNode//顶点结点定义{char data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct//图的定义{AdjList vertices;int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的种类标志}ALGraph;ALGraph G; //定义图变量bool visited[MAX_VERTEX_NUM]; //访问标志数组int indegree[28]; //各结点入度数组int num=0; //记录顶点字符种类数char a[28]; //存储拓扑排序序列struct Stack//栈类型定义{int s[21];int top;};Stack stack; //定义一个栈int LocateVertices(ALGraph G,char a)//查找字符a在图中的位置{for(int i=0;i<G.vexnum;i++)if(G.vertices[i].data==a)return i;return -1;}int LocateArc(ALGraph G,char a,char b)//判断弧ab是否已经存在于图中，若已经存在则返回1，否则返回0 {ArcNode *p;if(LocateVertices(G,a)>=0){p=G.vertices[LocateVertices(G,a)].firstarc;while(p&&p->adjvex!=LocateVertices(G,b))p=p->nextarc;if(p)return 1;return 0;}return 0;}void CreateGraph(ALGraph &G)//利用邻接表存储结构构造有向图{int a,b;char s1,s2;ArcNode *p;for(int i=0;i<G.vexnum;i++){G.vertices[i].data='#';G.vertices[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cin>>s1;a=LocateVertices(G,s1);if(a<0){num++;G.vertices[num-1].data=s1;a=LocateVertices(G,s1);}cin>>s2;cin>>s2;b=LocateVertices(G,s2);if(b<0){num++;G.vertices[num-1].data=s2;b=LocateVertices(G,s2);}if(!LocateArc(G,s1,s2)){p=new ArcNode;if(!p)return;p->adjvex=b;p->nextarc=G.vertices[a].firstarc;G.vertices[a].firstarc=p;}}}int FirstAdjVex(ALGraph G,int v)//查找图中位置v的第一个邻接点在图中所在的位置{if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;return -1;}int NextAdjVex(ALGraph G,int v,int w)//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置{ArcNode *p;p=G.vertices[v].firstarc;while(p->adjvex!=w)p=p->nextarc;if(p->nextarc)return p->nextarc->adjvex;return -1;}void DestroyGraph(ALGraph &G)//销毁图{ArcNode *p,*p1;for(int i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;if(p)p1=p->nextarc;while(p){delete p;p=p1;if(p1)p1=p1->nextarc;}}}void InitStack(Stack &stack)//初始化栈{stack.top=0;}void PushStack(Stack &stack,int i)//元素i入栈{stack.s[stack.top++]=i;}void PopStack(Stack &stack,int &i)//栈顶元素出栈{i=stack.s[--stack.top];}int StackEmpty(Stack stack)//判断栈是否为空，若为空则返回1，否则返回0{if(!stack.top)return 1;return 0;}void FindInDegree(ALGraph G,int *indegree)//求图中各个顶点的入度，并相应的存入入度数组中indegree[]{ArcNode *p;for(int i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}int TopologicalSort(ALGraph G)//对图进行拓扑排序，并存储相应的拓扑序列{int count=0,w;FindInDegree(G,indegree);for(int i=0;i<G.vexnum;i++)if(!indegree[i])PushStack(stack,i);while(!StackEmpty(stack)){PopStack(stack,i);a[count]=G.vertices[i].data;count++;for(w=FirstAdjVex(G,i);w>=0;w=NextAdjVex(G,i,w)) if(!(--indegree[w]))PushStack(stack,w);}if(count<G.vexnum)return -1;return 1;}void SortProblem(ALGraph G)//解决问题的函数{if(TopologicalSort(G)==-1)cout<<"Inconsistency found."<<endl;elseif(num<G.vexnum)cout<<"Sorted sequence cannot be determined."<<endl; else{cout<<"Sorted sequence determined: ";for(int i=0;i<G.vexnum;i++)cout<<a[i]<<" ";cout<<"."<<endl;}}void main(){G.vexnum=1;G.arcnum=1;while(G.vexnum&&G.arcnum){num=0;cin>>G.vexnum>>G.arcnum;CreateGraph(G);if(G.vexnum&&G.arcnum){SortProblem(G);}DestroyGraph(G);}}。