Q&A

  • 자바 소스를 델파이로..
자바로 위상정렬을 구현한 소스입니다
델파이로 바꾸고 싶은데 어렵네요..
좀 도와주세요

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

1  COMMENTS
  • Profile
    손희석 2003.12.05 19:53





    TQueue 클래스 참조하세요.. 유닛은 Contnrs에 있어요..
    여기서 필요한 부분을 조금만 구현하시면 될거 같은데..

    도움이 되었으면 하는데 .. ^^ 그럼 휘리릭