原有邻接表存储结构加入入度数据项

#define MAXV 4
typedef int ElemType;
typedef int InfoType;
struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
    InfoType info;
};
struct VNode {
    ElemType data;
int count; //此处增加一个入度
ArcNode *firstarc;
};
typedef VNode AdjList[MAXV];
struct AGraph {
    AdjList adjlist;
    int n,e;
};
void CreateAdj(AGraph *&G,int A[][MAXV],int n) {
    int i,j;
    ArcNode *p;
    G=(AGraph *)malloc(sizeof(AGraph));
    G->n=n;
    G->e=0;
    for(i=0; i<n; i++) {
        G->adjlist[i].firstarc=NULL;
G->adjlist[i].count=0; //此处初始入度
}
for(i=0; i<n; i++) {
    for(j=n-1; j>=0; j--)
        if(A[i][j]!=0) {
G->adjlist[j].count++; //此处统计入度
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
G->e++;
}
}
}
void DispAdj(AGraph *G) {
    int i;
    ArcNode *p;
    for(i=0; i<G->n; i++) {
        cout<<i<<"->";
        p=G->adjlist[i].firstarc;
        while(p!=NULL) {
            cout<<p->adjvex<<"->";
            p=p->nextarc;
        }
        cout<<"^"<<endl;
    }
}

拓扑排序

int TopSort(AGraph *G,int Topsq[]) {
    int i,j,n=0;
    int St[MAXV],top=-1;
    ArcNode *p;
    for(i=0; i<G->n; i++)
        if(G->adjlist[i].count==0) {
            top++;
            St[top]=i;
        }
        while(top>-1) {
            i=St[top];
            top--;
            Topsq[n]=i;
            n++;
            p=G->adjlist[i].firstarc;
            while(p!=NULL) {
                j=p->adjvex;
                G->adjlist[j].count--;
                if(G->adjlist[j].count==0) {
                    top++;
                    St[top]=j;
                }
                p=p->nextarc;
            }
        }
        if(n<G->n)
            return 0;
        else
            return 1;
    }