拓撲圖為：（圖不好粘貼）
運用拓撲概念排序的結果：
C1 , C9 , C3 , C2 , C7 , C4, C5 , C8 , C6
C1計算機應用基礎 C2 C語言 C3 VB語言 C4 JSP C5數字邏輯電路 C6軟件工程
C7計算機網絡基礎 C8 Java語言 C9計算機數學基礎
/*-------------------------------主類-----------------------------*/
public class Navy1 {
public static void main(String[] args) {
topology(); //調用拓撲的構造方法
}
public static void topology() { //構造拓撲方法
/**
聲明拓撲圖中的元素
定義節點和節點之間的關系
Entry(a,b)a為b的前導
**/
Entry[] relations = { new Entry(9, 2), new Entry(3,7),
new Entry(7, 5), new Entry(5, 8), new Entry(8, 6),
new Entry(4, 6), new Entry(1, 3), new Entry(7, 4),
new Entry(9, 5), new Entry(2, 8) };
int n = 9;
int n1 = 9;
/*計算拓撲圖中節點數*/
int[] count = { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
/*開辟內存空間*/
Node[] top = { null, null, null, null, null, null, null, null, null, null };
Node p = null;
for (int i = 0; i < relations.length; i++) {
count[relations[i].k]++;
p = new Node();
p.suc = relations[i].k;
p.next = top[relations[i].j];
top[relations[i].j] = p;
}
int r = 0;
int[] qlink = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 1; i <= n; i++) {
if (count[i] == 0) {
qlink[r] = i;
r = i;
}
}
int f = qlink[0];
System.out.println("題目及要求:");
System.out.println("課程排課程序。寫壹個程序，實現對某個專業的課程進行排課的功能。");
System.out.println("已知某專業的課程和它們的前導和後續關系（以有向圖的形式表示），");
System.out.println("請用拓撲排序算法求出這些課程的優先關系並輸出壹種排課結果");
System.out.println("--------------------------------------");
System.out.println("08信息工程系軟件技術課程表（拓撲排序）");
while (true)
{
System.out.println(f);
if (f == 0) //結束條件
{
break;
}
else
{
n1--;
p = top[f];
while (true)
{
if (p == null)
{
break;
}
else
{
count[p.suc]--;
if (count[p.suc] == 0)
{
qlink[r] = p.suc;
r = p.suc;
}
p = p.next;
}
}
f = qlink[f];
}
}
System.out.println("結束的標誌為：" + n1);
System.out.println("--------------------------------------------");
System.out.println("註釋（數字對應的課程）：");
System.out.println("1 計算機應用基礎 2 C語言 3 VB語言 ");
System.out.println("4 JSP 5 數字邏輯電路 6 軟件工程");
System.out.println("7 計算機網絡基礎 8 Java語言 9 計算機數學基礎");
System.out.println("--------------------------------------------");
}
/*構造元素類*/
private static class Entry
{
public Entry(int begin, int end) //定義開始元素和結束元素
{
this.j = begin;
this.k = end;
}
int j;
int k;
}
/*聲明節點的後繼*/
private static class Node
{
public Node(int suc, Node next)
{
this.suc = suc;
this.next = next;
}
public Node()
{
}
int suc;
Node next;
}
}