#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|).//如果一个图按照三角矩阵存储,那么一定无环
200字范文,内容丰富有趣,生活中的好帮手!