void TopologicalSort(ALGraph G) { Stack S, OutCome; InitStack(&S); InitStack(&OutCome); //寻找入读为0的顶点入栈 for (int i = 0; i < G.VexNum; i++) { if (!G.InDegree[i]) { S.Vertics[S.tail++] = i; } } while (0 < S.tail) { int tmp = OutCome.Vertics[OutCome.tail++] = S.Vertics[--S.tail]; for (ArcNode* p = G.Vertics[tmp].FirstArc; NULL != p; p = p->Next) { G.InDegree[p->AdjVex]--; if (0 == G.InDegree[p->AdjVex]) S.Vertics[S.tail++] = p->AdjVex; } } if (OutCome.tail != G.VexNum) { printf("课程的先决条件有误！\n"); exit(EXIT_FAILURE); } printf("请输入分配课程要求(各学期负担集中:1 尽可能集中前几个学期:2)："); int Command; scanf("%d", &Command); switch (Command) { case 1: Method1(G, OutCome); break; case 2: Method2(G); break; default: { printf("命令错误！"); exit(EXIT_FAILURE); } } getch(); main(); }代码流程思路

该函数的主要功能是对给定的有向图G进行拓扑排序，并根据用户输入的要求进行课程分配。

具体流程如下：

1. 初始化两个栈S和OutCome，用于存储拓扑排序的结果和已经处理的顶点。

2. 遍历有向图G中的每个顶点，将入度为0的顶点入栈S中。

3. 当栈S不为空时，循环执行以下操作：

- 取出栈S中的一个顶点tmp，将其加入栈OutCome中。

- 遍历顶点tmp的所有邻接点p->AdjVex，并将其入度减1。

- 如果邻接点p->AdjVex的入度为0，将其加入栈S中。

4. 如果栈OutCome的元素个数不等于有向图G的顶点数，说明有向图中存在环，拓扑排序失败，输出错误信息并退出程序。

5. 提示用户输入分配课程的要求（1代表各学期负担集中，2代表尽可能集中前几个学期）。

6. 根据用户输入的要求，调用相应的方法，进行课程分配。

7. 循环结束后，通过getch()等待用户按下任意键后重新进入main函数。

相关问题

试实现拓扑排序算法。函数void findindegree(algraph g,int indegree[])实现图中各个顶点入度的统计；函数int topologicalsort(algraph g , int topo[])获取拓扑序列。

题目要求实现拓扑排序算法。函数void findindegree(algraph g,int indegree[])实现统计图中各个顶点入度的功能，函数int topologicalsort(algraph g , int topo[])获取拓扑序列。

逐行翻译代码：typedef struct node { int adjvex; struct node *next; }node, *pointer; typedef struct node1 { int vex; int in; pointer link; }ALGraph; void createadlist(ALGraph G[], int n, int e) { int i, k, j; pointer q; for (i = 1; i <= n; i++) { G[i].vex = i; G[i].in=0; G[i].link = null; } for (k = 1; k <= e; k++) { scanf("%d%d", &i, &j); q = (pointer)malloc(sizeof(struct node)); q->adjvex = j; q->next = G[i].link; G[i].link = q; G[j].in++; } } void fun(ALGraph G[], int n, int v, int visit[]) { pointer p; int w; visit[v] = 1; printf("%3d", v); p = G[v].link; while (p != null) { w = p->adjvex; if (visit[w] == 0) { fun(G, n, w, visit); } p = p->next; } } int TopologicalSort(ALGraph G[],int &n) { SqStack S; InitSatack(S); for(int i=1;i<n;i++) { if(!G[i].in) Push(S,i); int count=0; while(!StackEmpty(S)) { Pop(S,i); printf(" %d ",i); ++count; pointer p; p=(pointer)malloc(sizeof(struct node)); for(p=G[i].link;p;p=p->next) { int k=p->adjvex; if(!(--G[k].in)) Push(S,k); } } if(count<G[i].in) printf("存在循环"); } return ok; }

这段代码是一个图的邻接表存储结构的实现。下面是逐行的代码翻译：

typedef struct node {
    int adjvex;
    struct node *next;
}node, *pointer;

typedef struct node1 {
    int vex;
    int in;
    pointer link;
}ALGraph;

定义了两个结构体，一个是邻接表中的节点，一个是邻接表中的图。

void createadlist(ALGraph G[], int n, int e) {
    int i, k, j;
    pointer q;
    for (i = 1; i <= n; i++)
    {
        G[i].vex = i;
        G[i].in=0;
        G[i].link = null;
    }
    for (k = 1; k <= e; k++)
    {
        scanf("%d%d", &i, &j);
        q = (pointer)malloc(sizeof(struct node));
        q->adjvex = j;
        q->next = G[i].link;
        G[i].link = q;
        G[j].in++;
    }
}

这个函数用于创建邻接表。首先对于每个节点，分别给它们赋值。然后遍历每一条边，读取起点和终点，为终点节点的入度加1，同时将起点节点作为终点节点的邻接表的头节点。

void fun(ALGraph G[], int n, int v, int visit[]) {
    pointer p;
    int w;
    visit[v] = 1;
    printf("%3d", v);
    p = G[v].link;
    while (p != null)
    {
        w = p->adjvex;
        if (visit[w] == 0)
        {
            fun(G, n, w, visit);
        }
        p = p->next;
    }
}

这个函数是深度优先遍历的实现。从给定的起点开始，访问该节点，并标记为已访问。然后遍历该节点的邻接表，如果邻接节点未被访问，则递归地访问该节点。

int TopologicalSort(ALGraph G[],int &n) {
    SqStack S;
    InitSatack(S);
    for(int i=1;i<n;i++)
    {
        if(!G[i].in)
            Push(S,i);
        int count=0;
        while(!StackEmpty(S))
        {
            Pop(S,i);
            printf(" %d ",i);
            ++count;
            pointer p;
            p=(pointer)malloc(sizeof(struct node));
            for(p=G[i].link;p;p=p->next)
            {
                int k=p->adjvex;
                if(!(--G[k].in))
                    Push(S,k);
            }
        }
        if(count<G[i].in)
            printf("存在循环");
    }
    return ok;
}

这个函数是拓扑排序的实现。首先建立一个栈，将所有入度为0的节点入栈。然后弹出栈顶元素，输出该节点，并将该节点指向的邻接节点的入度减1。如果邻接节点入度为0，则入栈。当栈为空时，如果输出的节点数小于节点总数，则说明存在环。最后返回ok表示排序完成。