#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MaxSize 50typedef struct ArcNode{int adjvex;ArcNode *next;};struct VNode{char value;ArcNode *first;};struct AdGraph{VNode vertices[MaxSize];int vexnum,arcnum;};//求图中每个顶点的入度void getAllNodeDegree(AdGraph G,int *indegree){for(int i = 0;i < G.vexnum;i++){ArcNode *p = G.vexnum[i].first;while(p){indegree[p->adjvex]++;p = p->next;}}}//算法思想：/**首先，先用一个indegree数组把所有顶点的入度都初始化为0，再用一个函数(getAllNodeDegree())来得到整个图中所有顶点的入度。遍历整个数组，将入度为0的元素序列保存到栈中(stack[MaxSize]),当栈不为空的时候(top != -1),将最后一个元素出栈，然后将其发到其他顶点的边也删除(这里的删除是逻辑删除，更改的是indegree[]),直到p走到空，(当p走到空的过程中，可能会有p->adjvex的顶点的入度被删完了，所以如果每一轮while(p){}循环里面都要设置if(indegree[p->adjvex] == 0;),来检测这一轮while循环删除里是否有元素的入度被删为0了，如果为0，就将此时的p->adjvex入栈。)然后再出栈下一个元素。ps:这里用count 来记录了toposequence里面元素的个数，当这个图是无环的，count == G.vexnum;如果是有环的, count < G.vexnum,所以这里用bool 来判定这个图是否是有向无环图，就是直接看count是否等于G.vexnum.**//**解释定义的数组：stack[MaxSize]:保存入度为0的数组indegree[MaxSize]:保存每个顶点入度的度数topoSequence[MaxSize]:保存拓扑排序 输出的数组**///Topo//判断有向连通图是否有环bool Topo(AdGraph G){int stack[MaxSize],top = -1;indegree[MaxSize],toposequence[MaxSize];for(int i = 0;i < G.vexnum;i++){indegree[i] = 0;}getAllNodeDegree(G,indegree);for(int i = 0;i < G.vexnum;i++){if(indegree[i] == 0){stack[++top] = i;}}int v;int count = 0;while(top != -1){v = stack[top--];toposequence[count++] = v;ArcNode *p = G.vertices[v].first;while(p){--indegree[p->adjvex];if(indegree[p->adjvex] == 0){stack[++top] = p->adjvex;}p = p->next;}}if(count == G.vexnum)return true;elsereturn false;}//总结：//采用邻接表存储时，Topo排序的时间复杂度是O(|v|+|e|)// 邻接矩阵 ， O(|V|^2).//空间复杂度：O(|v|).//如果一个图按照三角矩阵存储，那么一定无环
