자바로 위상정렬을 구현한 소스입니다
델파이로 바꾸고 싶은데 어렵네요..
좀 도와주세요
class List {
private int front; // 큐의 삭제 장소
private int rear; // 큐의 삽입 장소
private int count; // 큐의 원소 수
private int Size; // 큐(배열)의 크기
private int[] itemArray; // Java 객체 타입의 큐 원소를 위한 배열
public List(){ // 무인자 큐 생성자
front = 0; // 초기화
rear = 0;
count = 0;
Size = 50; // 초기 큐 크기
itemArray = new int[Size];
}
public boolean isEmpty(){
return (count == 0);
}
public void insert(int x){
itemArray[rear++] = x; // 새로운 원소를 삽입
count++;
} // end enqueue( )
public int remove( ){// 큐에서 원소를 삭제해서 반환
int item = itemArray[front++];
count --;
return item;
} //end dequeue()
}
class Queue {
private int front; // 큐의 삭제 장소
private int rear; // 큐의 삽입 장소
private int count; // 큐의 원소 수
private int queueSize; // 큐(배열)의 크기
private int increment; // 배열의 확장 단위
private int[] itemArray; // Java 객체 타입의 큐 원소를 위한 배열
public Queue(){ // 무인자 큐 생성자
front = 0; // 초기화
rear = 0;
count = 0;
queueSize = 50; // 초기 큐 크기
increment = 10; // 배열의 확장 단위
itemArray = new int[queueSize];
}
public boolean isEmpty(){
return (count == 0);
}
public void enqueue(int x){
if (count == queueSize) queueFull();
itemArray[rear] = x; // 새로운 원소를 삽입
rear = (rear + 1) % queueSize;
count++;
} // end enqueue( )
public void queueFull() { // 배열이 만원이면 increment만큼 확장
int oldsize = queueSize; // 현재의 배열 크기를 기록
queueSize += increment; // 새로운 배열 크기
int[] tempArray = new int[queueSize]; //확장된크기의임시배열
for (int i=0; i<count; i++) {
// 임시 배열로 원소들을 그대로 이동
tempArray[i] = itemArray[front];
front = (front + 1) % oldsize;
}
itemArray = tempArray; // 배열 참조 변수를 변경
front = 0;
rear = count;
} // end queueFull()
public int dequeue( ){// 큐에서 원소를 삭제해서 반환
int item = itemArray[front];
front = (front + 1) % queueSize;
count --;
return item;
} //end dequeue()
} //end ArrayQueue class
class Graph {
Queue[] Q; // 정점 i의 직속 후속자를 저장하는 큐
Queue zeroPredQ; // 선행자가 없는 정점들을 저장하는 큐
List sortedList; // 위상 정렬 결과를 보관하는 리스트
int[] indegree; // 정점 i의 진입 차수
int n; // 정점들의 개수
public Graph(int vertices) { // 생성자
n = vertices;
Q = new Queue[n]; // 큐 배열
zeroPredQ = new Queue();
sortedList = new List();
for (int i=0; i<n; i++) {
Q[i] = new Queue(); // 각 Q[i]에 대해 초기화
}
indegree = new int[n];
}
public void topologicalSort(){
int i, v, successor;
for (i=0; i<n; i++) {
if (indegree[i]==0) // 선행자 없음
zeroPredQ.enqueue(i);
}
if (zeroPredQ.isEmpty()) {
System.out.println("network has a cycle");
return;
}
while (!zeroPredQ.isEmpty()) {
// indegree가 0인 정점들을 큐에서 하나씩 삭제해 처리
v = zeroPredQ.dequeue();
// indegree가 0인 정점들을 결과 리스트에 삽입
sortedList.insert(v);
if (Q[v].isEmpty()) continue; // 정점 v의 후속자가 없으면
// 밖의 while 루프로
else successor = Q[v].dequeue(); // 후속자가 있으면,
// 그 후속자를 successor로 설정
while (true) { // v의 후속자 정점의 진입차수를 감소시킴.
indegree[successor]--;
if (indegree[successor]==0) // 0이 되면 zeroPredQ에 삽입
zeroPredQ.enqueue(successor);
if (!Q[v].isEmpty()) successor = Q[v].dequeue();
else break;
}
} // end while
System.out.println("Topological Order is : ");
while (!sortedList.isEmpty())
System.out.print(sortedList.remove() + " ");
System.out.println();
System.out.println("End.");
} // end topologicalSort()
public void insertEdge(int i, int j){ // 인접 리스트를 큐 배열로 표현
Q[i].enqueue(j);
indegree[j]++;
} // end insertEdge()
} // end Graph class
class AOV_Topological_Sort {
public static void main(String args[]){
Graph AOV = new Graph(6);
// 그림 10.14의 AOV 네트워크
AOV.insertEdge(0,1); // 정점 0의 간선들을 삽입
AOV.insertEdge(0,2);
AOV.insertEdge(1,3); // 정점 1의 간선들을 삽입
AOV.insertEdge(1,4);
AOV.insertEdge(2,3); // 정점 2의 간선들을 삽입
AOV.insertEdge(2,4);
AOV.insertEdge(3,5); // 정점 3의 간선들을 삽입
AOV.insertEdge(4,5); // 정점 4의 간선들을 삽입
AOV.topologicalSort(); // 위상 정렬 함수 호출
} // end main()
} // end AOV_Topological_Sort
TQueue 클래스 참조하세요.. 유닛은 Contnrs에 있어요..
여기서 필요한 부분을 조금만 구현하시면 될거 같은데..
도움이 되었으면 하는데 .. ^^ 그럼 휘리릭