/* 拓扑排序：可以用来判断有向图中是否存在环。
思路：
a：先遍历图，将图中入度为0的结点入栈
b：栈非空，循环，每次出栈一个结点，进行计数。
c：对出栈的结点的邻接结点的度进行-1，在此过程中如果发现结点度减少之后，入度为0，则入栈
d：循环结束，用刚刚的计数去判断是否有n个结点，由此来判断图中是否有环
*/
typedef struct Arcnode{
int adjvex;
struct Arcnode *nextarc;
}Arcnode;
typedef struct{
Arcnode *firstarc;
int info;
int count://记录每个结点的入度；
}Vnode;
typedef struct{
Vnode adjlist[maxsize];
int e;
int n;
}AGraph;
bool isCircle(AGraph *G){
int no=0,w;
Arcnode *p;
int stack[maxsize],top=-1;
for(int i=0;i<G->n;i++)
if(G->adjlist[i].count==0)
stack[++top]=i;
while(top!=-1){
w=stack[top--];
no++;
p=G->adjlist[w].firstarc;
while(p!=NULL){
w=p->adjvex;
G->adjlist[w].count--;
if(G->adjlist[w].count==0)
stack[++top]=w;
p=p->nextarc;
}
}
if(no==n)return true;
else return false;
}
评论 (0)
