vemy.zip_seasont97_人工智能/神经网络/深度学习

#include <stdio.h> #include <malloc.h> #define Null 0 #define MAX_VERTEX_NUM 20 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef int ElemType; typedef struct { SElemType *base,*top; int stacksize; }SqStack; typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode,*AdjList; typedef struct Graph { AdjList elem[MAX_VERTEX_NUM]; int vexnum,arcnum; //图的顶点数和弧数 }Graph; void InitStack(SqStack *S)//栈的初始化 { S->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!S->base) { printf("分配不成功!");} else {S->top=S->base; S->stacksize=STACK_INIT_SIZE; } } int Push(SqStack *S,SElemType e) { if(S->top-S->base>=S->stacksize)//判断栈是否满了,如果满了 { S->base=(SElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT) *sizeof(ElemType));//堆分配 if(!S->base) printf("分配不成功!"); else S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } else {*(++S->top)=e;//把值付给栈顶指针 return 1; } } int Pop(SqStack *S)//出栈 { SElemType e; if(S->top==S->base) return 0;//判断是否栈为空 else { e=*(S->top); S->top--; return e; } } void create(Graph *G) { int i,j,k; AdjList p; printf("请输入该图的顶点和弧的数目:\n"); scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); for(k=1;k<=(*G).vexnum;k++) (*G).elem[k]=Null;//顶点信息付空 for(k=1;k<=(*G).arcnum;k++) { printf("输入弧的信息(i,j):\n"); scanf("%d,%d",&i,&j); p=(AdjList)malloc(sizeof(ArcNode)); p->adjvex=j;//p的数据为j p->nextarc=(*G).elem[i];//p的指针指向i (*G).elem[i]=p; } } int TopoSort(Graph G) { int i, count, indegree[20]; AdjList p; SqStack *S; S=(SqStack *)malloc(1000*sizeof(SqStack)); for(i=1;i<=G.vexnum;i++) indegree[i]=0; InitStack(S);//建一个空栈 for(i=1;i<=G.vexnum;i++) for(p=G.elem[i];p;p=p->nextarc) ++indegree[p->adjvex];//顶点度的计算 for(i=1;i<=G.vexnum;i++) if(!indegree[i]) Push(S,i); count=0; while(S->top!=S->base) { i=Pop(S); printf("%d",i); ++count; for(p=G.elem[i];p;p=p->nextarc) if(!(--indegree[p->adjvex])) Push(S,p->adjvex); } if(count<G.vexnum) return 0; else return 1; } main() { Graph G; create(&G); printf("该拓扑排序如下:\n"); if(!TopoSort(G)) printf("\n该图存在环!!!\n"); else printf("\n不存在环!!!\n") ; }