topological.java~120~

拓扑排序实现排课功能 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 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);

            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);
            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);
            }
        }
        return (a == n);
    }

    public static void main(String[] args) {
        Topological top = new Topological();
    }
}