adjacency.java

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

package course;

/**
 * <p>Title:邻接矩阵 </p>
 *
 * <p>Description: 建立邻接矩阵及其基本方法</p>
 *
 * <p>Copyright: Copyright (c) 2007</p>
 *
 * <p>Company:www.bchine.com </p>
 *
 * @author lipiji
 * @version 1.0
 */
public class Adjacency {
    int noEdge = 0;//没有边
    public static int n;//点的个数
    int e = 0;//边的条数
    public static int pos[];//过度数组


    void InitializePos(int i) {
        pos = new int[i + 1];//初始化
    }

    void DeactivatePos(int n) {
        for (int i = 0; i <= n; i++) {
            pos[i] = 0;
        }

    }

    public void makeAdjacency(int Vertices, int noEdge, int a[][]) {
        this.n = Vertices;//顶点数

        e = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = noEdge;//初始化邻接矩阵
            }
        }
    }


//检查是否已经存在
    public Boolean Exist(int i, int j, int a[][]) {
        if (i < 1 || j < 1 || i > n || j > n
            || a[i][j] == noEdge) {
            return false;
        }
        return true;
    }

    public void Add(int i, int j, int w, int a[][]) {//添加边，代表前者是后者的先行课
        if (i < 1 || j < 1 || i > n ||
            j > n || i == j || a[i][j] != noEdge) {
            System.out.println("Add throw BadInput();");//不合法输入
        }
        a[i][j] = w;//赋权值
        e++;//边数
    }

    public void Delete(int i, int j, int a[][]) {//删除
        if (i < 1 || j < 1 || i > n ||
            j > n || a[i][j] == noEdge) {
            System.out.println("Delete throw BadInput();");
        }
        a[i][j] = noEdge;
        e--;
    }

    public int OutDegree(int i, int a[][]) {//出度
        if (i < 1 || i > n) {
            System.out.println("OutDegree throw BadInput();");
        }
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] != noEdge) {//和i邻接的顶点
                sum++;
            }
        }
        return sum;
    }

    public int InDegree(int i, int a[][]) {//入度
        if (i < 1 || i > n) {
            System.out.println("InDegree throw BadInput();");
        }
        int sum = 0;
        for (int j = 1; j <= n; j++) {
            if (a[j][i] != noEdge) {
                sum++;
            }
        }
        return sum;

    }


    int Begin(int i, int a[][]) {
//获取和当前点邻接的顶点
        if (i < 1 || i > n) {
            System.out.println("Begin throw BadInput();" + i);
        }
        int j = 0;
        for (j = 1; j <= n; j++) {
            if (a[i][j] != noEdge) {
                pos[i] = j;//中间变量
                return j;//返回点
            }

        }
        pos[i] = n + 1;
        return 0;//若没有电则返回 0

    }

    public int NextVertex(int i, int a[][]) {//下一个顶点
        if (i < 1 || i > n) {
            System.out.println("NextVertex throw BadInput();" + i);
        }

        for (int j = pos[i] + 1; j <= n; j++) {
            if (a[i][j] != noEdge) {
                pos[i] = j;
                return j;
            }
        }
        pos[i] = n + 1;
        return 0;

    }

    public void Output(int a[][]) {//输出邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(a[i][j] + "  ");

            }
            System.out.println();
        }

    }

    public static void main(String[] args) {
        Adjacency adjacency = new Adjacency();
    }
}