java拓扑排序问题实例源码。

n个人排队， 每个人都有要求Request， 具体每个要求是希望排在某个人之前或者之后， 用类RequestItem表示。

例如有 1， 2， 3三个人， 1希望排在2之后3之前， 2希望排在1之前， 3希望排在1， 2之后。输出一个合理的排列
[java] view plaincopy在CODE上查看代码片派生到我的代码片
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

class RequestItem{
String name;
boolean front;
}

class Request{
String name;
List<RequestItem> items;
}
public class FindValidOrder {
static List<String> validOrder(List<String> names, List<Request> requests){
HashMap<String, List<String>> maps = new HashMap<String, List<String>>();
for(String name: names){
maps.put(name, new LinkedList<String>());
}
for(Request re: requests){
for(RequestItem item: re.items){
if(item.front){
List<String> tmp = maps.get(item.name);
if(!tmp.contains(re.name)){
tmp.add(re.name);
}
}else{
List<String> tmp = maps.get(re.name);
if(!tmp.contains(item.name)){
tmp.add(item.name);
}
}

}
}
HashMap<String, Integer> counts = new HashMap<String, Integer>();
for(String name: names){
counts.put(name, 0);
}
for(String name: names){
List<String> tmp = maps.get(name);
for(String s: tmp){
int tmpcount = counts.get(s)+1;
counts.put(s, tmpcount);
}
}
List<String> queue = new LinkedList<String>();
while(!counts.isEmpty()){
boolean found = false;
String next = null;
for(String name: counts.keySet()){
if(counts.get(name)==0){
next = name;
found = true;
}
}
if(!found) break;
counts.remove(next);
for(String s: maps.get(next)){
int tmpcount = counts.get(s)-1;
counts.put(s, tmpcount);
}
queue.add(next);
}
if(queue.size() == names.size()) return queue;
return null;
}
public static void main(String [] args){
List<String> names = new LinkedList<String>();
names.add(“1″);
names.add(“2″);
names.add(“3″);
List<Request> requests = new LinkedList<Request>();

Request r = new Request();
r.name = “1″;
r.items = new LinkedList<RequestItem>();
RequestItem item = new RequestItem();
item.name = “2″;
item.front = true;
r.items.add(item);
RequestItem item2 = new RequestItem();
item2.name = “3″;
item2.front = false;
r.items.add(item2);
requests.add(r);

Request r2 = new Request();
r2.name = “2″;
r2.items = new LinkedList<RequestItem>();
RequestItem item3 = new RequestItem();
item3.name = “1″;
item3.front = false;
r2.items.add(item3);
requests.add(r);

Request r3 = new Request();
r3.name = “3″;
r3.items = new LinkedList<RequestItem>();
RequestItem item4 = new RequestItem();
item4.name = “2″;
item4.front = true;
r3.items.add(item4);
RequestItem item5 = new RequestItem();
item5.name = “1″;
item5.front = true;
r3.items.add(item5);
requests.add(r3);

List<String> order = validOrder(names, requests);
System.out.println(order);
}

}