topological.java

拓扑排序实现排课功能 8学期任意多门课程排序

package course;

import java.util.Stack;

/**
 * <p>Title: 拓扑排序</p>
 *
 * <p>Description: 实现拓扑排序</p>
 *
 * <p>Copyright: Copyright (c) 2007 </p>
 *
 * <p>Company: www.bchine.com</p>
 *
 * @author 李丕绩
 * @version 1.0
 */
public class Topological extends Adjacency {
    Stack S = new Stack();
    Adjacency ad = new Adjacency();
    Field fi[];//Field类型的数组
    Field eld = new Field();//用来接由堆栈弹书来的对象


    public static int t;

    public boolean Topo(Field v[], int n, int aa[][]) {
        fi = new Field[n];
        ad.InitializePos(n); //初始化数组pos作为中间桥梁的作用
        int InDegree[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            InDegree[i] = 0; //初始化入度

        }
        for (int i = 1; i <= n; i++) {
            int u = ad.Begin(i, aa);//i邻接的顶点

            while (u != 0) {
                InDegree[u]++;//初始化各点入度
                u = NextVertex(i, aa);

            }
        }

        for (int i = 1; i <= n; i++) {
            fi[i - 1] = new Field();//初始化
            if (InDegree[i] == 0) {//如果入度为零
                fi[i - 1].index = i;//赋上课序号
                fi[i - 1].term = 1;//赋上学期号
                S.push(fi[i - 1]);//压栈

            }

        }

        int a = 0;
        while (!S.empty()) {//当栈不为空时
            eld = (Field) S.pop();//弹出
            v[a++] = eld;//存入数组，最后用来输出
            int w = eld.index;//可序号
            int u = Begin(w, aa);//和w邻接的点
            while (u != 0) {//若不为零
                InDegree[u]--;
                if (InDegree[u] == 0) {
                    fi[u - 1].index = u;//赋上可序号
                    fi[u - 1].term = eld.term + 1;//将上点的学期号加一
                   // System.out.println(u + "入栈");
                    S.push(fi[u - 1]);//入栈
                }
                u = NextVertex(w, aa);//判断与w邻接的下一个顶点
            }
        }
        return (a == n);
    }


}