数据结构中图的全部运算

#include<stdio.h> #include<malloc.h> typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ int data; int indegree; ArcNode *firstarc; }VNode; typedef struct{ VNode *elem; int vexnum; }ALGraph; int InitGraph(ALGraph &G){ G.elem=(VNode *)malloc(27 *sizeof(VNode)); if(!G.elem) return 0; G.vexnum=0; for(int i=0;i<27;i++){ G.elem[i].data=0; G.elem[i].indegree=0; G.elem[i].firstarc=NULL; } return 1; } typedef struct{ int *base; int *top; int stacksize; }SqStack; int InitStack(SqStack &S){ S.base=(int *)malloc(300 *sizeof(int)); if(!S.base) return 0; S.top=S.base; S.stacksize=300; return 1; } int Push(SqStack &S,int k){ if(S.top-S.base>=S.stacksize){ S.base=(int *)realloc(S.base,(S.stacksize+10)*sizeof(int)); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize+=10; } *S.top++=k; return 1; } int Pop(SqStack &S,int &k){ if(S.top==S.base) return 0; k=*--S.top; return 1; } int StackEmpty(SqStack S){ if(S.top==S.base) return 1; return 0; } int d=0,l=0; int a[26]={0}; char b[1000][3]; int TopologicalSort(ALGraph G,int n){ int flag=0; int j=0; int i; int s=0; int t=0; int indegree[27]={0}; SqStack S; InitStack(S); for(i=1;i<=G.vexnum;i++){ indegree[i]=G.elem[i].indegree; // printf("%d",G.elem[i].indegree); if(!indegree[i]) { Push(S,i); s++; } } if(s>1) flag=1; int count=0; while(StackEmpty(S)==0){ Pop(S,i); a[j]=G.elem[i].data+64; j++; count++; ArcNode *p; if(!G.elem[i].firstarc) { continue; } s=0; for(p=G.elem[i].firstarc;p;p=p->nextarc){ int k=p->adjvex; if(!(--indegree[k])) { Push(S,k); s++; } } if(s>1) flag=1; } int q; for(q=0;q<n;q++){ if(a[q]==0) break; // printf("%c",a[q]); } // printf("%d",flag); // printf("%d",q); if(count<G.vexnum) return 2; if(flag!=1&&q==n) return 3; return 1; } int CreateGraph(ALGraph &G,int n,int m){ d=0; l=0; int i; for(i=0;i<m;i++){ scanf("%s",b[i]); } for(i=0;i<m;i++){ G.vexnum=n; if(d==0&&l==0){ int x=b[i][0]-64; int y=b[i][2]-64; G.elem[x].data=x; G.elem[y].data=y; G.elem[y].indegree++; //入度++; ArcNode *p; p=(ArcNode *)malloc(sizeof(ArcNode)); if(!p) return 0; p->adjvex=y; p->nextarc=G.elem[x].firstarc; G.elem[x].firstarc=p; int t=TopologicalSort(G,n); if(t==2) d=i; if(t==3) l=i; } } if(d>0) printf("Inconsistency found after %d relations.\n",d+1); else if(l>0){ printf("Sorted sequence determined after %d relations: ",l+1); for(int k=0;k<n;k++) printf("%c",a[k]); printf(".\n"); } else printf("Sorted sequence cannot be determined.\n"); for(int j=1;j<=n;j++){ if(G.elem[j].data==0) return 3; } return -1; } int main(){ int n,m; do{ scanf("%d%d",&n,&m); if(n==0&&m==0) break; else{ for(int i=0;i<26;i++){ a[i]=0; } ALGraph G; InitGraph(G); int s=CreateGraph(G,n,m); // printf("%d",c); } }while(n>0&&m>0); return 1; }