루프 없 는 데이터 구조 와 토폴로지 정렬 이 있 습 니 다.

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

/**
 * 

 *   ：
 *   ：    
 *   ：@author huangpeng
 *   ：@create 2018-09-02   1:07
 *   : Bag
 * 
**/
public class Bag implements Iterable {
private int N;
private Node first;
public int getN() {
return N;
}
public Item getFirstItem() {
return first.item;
}
private class Node{
private Item item;
private Node next;
public Item getItem() {
return item;
}
public Node getNext() {
return next;
}
}
public Bag(){
first = null;
N = 0;
}
public boolean isEmpty(){
return first ==null;
}
public int size(){
return N;
}
public void add(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
@Override
public Iterator iterator() {
return new ListIterator(first);
}
private class ListIterator implements Iterator{
private Node current;
public ListIterator(Node first){
current = first;
}
@Override
public boolean hasNext() {
return current!=null;
}
@Override
public Item next() {
if(!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Bag bag = new Bag();
while(!sc.hasNext("0")){
bag.add(sc.next());
}
System.out.println("size of bag = "+bag.size());
for (String s:bag){
System.out.println(s);
}
}
}
그림 에 대한 데이터 구 조 를 정의 합 니 다:
import java.io.File;
import java.io.IOException;
import java.util.*;

/**
 * 

 *   ：
 *   ：        ，    
 *   ：@author huangpeng
 *   ：@create 2018-09-02   1:50
 *   : Diagraph
 * 
**/
public class Diagraph {
public int V;
public int E;
public Bag[] adj;
public int[] indegree;
public int[] outdegree;
int[] num ;
public Diagraph(int V){
if(V < 0) throw new IllegalArgumentException();
this.V = V;
this.E = 0;
adj = (Bag[]) new Bag[V];
for(int v=0;v();
}
this.indegree = new int[V];
this.outdegree = new int[V];
this.num = new int[V];
}
public Diagraph(String inputFile){
try {
File file = new File(inputFile);
if (file.exists()) {
Scanner sc = new Scanner(file);
this.V = sc.nextInt();
this.indegree = new int[V];
this.outdegree = new int[V];
this.num = new int[V];
if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
adj = (Bag[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag();
}
int E = sc.nextInt();
if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative");
for (int i = 0; i < E; i++) {
int v = sc.nextInt();
int w = sc.nextInt();
addEdge(v, w);
}
return;
}
}catch(IOException e){
System.out.println("couldn't open file "+inputFile);
}
}
public int V(){
return V;
}
public int E(){
return E;
}
public int[] getIndegree(){
return indegree;
}
public int[] getOutdegree(){
return outdegree;
}
public void addEdge(int v, int w){
adj[v].add(w);
indegree[w]++;
outdegree[v]++;
E++;
}
public Iterable adj(int v){
return adj[v];
}
public Diagraph reverse(){
Diagraph R = new Diagraph(V);
for(int v=0;v queue = new LinkedList();
int counter = 0;
for(int i=0;i