有向無環(huán)圖的拓?fù)渑判?，首先定義有向圖的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，鄰接鏈表Bag，實(shí)現(xiàn)Iterable接口。
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;
/**
* <pre>
* 任務(wù)：
* 描述：鏈表結(jié)構(gòu)
* 作者：@author huangpeng
* 時(shí)間：@create 2018-09-02 下午1:07
* 類名: Bag
* </pre>
**/
public class Bag<Item> implements Iterable<Item> {
private int N;
private Node<Item> first;
public int getN() {
return N;
}
public Item getFirstItem() {
return first.item;
}
private class Node<Item>{
private Item item;
private Node<Item> next;
public Item getItem() {
return item;
}
public Node<Item> 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<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
N++;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
private class ListIterator<Item> implements Iterator<Item>{
private Node<Item> current;
public ListIterator(Node<Item> 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<String> bag = new Bag<String>();
while(!sc.hasNext("0")){
bag.add(sc.next());
}
System.out.println("size of bag = "+bag.size());
for (String s:bag){
System.out.println(s);
}
}
}
定義有向圖的數(shù)據(jù)結(jié)構(gòu)：
import java.io.File;
import java.io.IOException;
import java.util.*;
/**
* <pre>
* 任務(wù)：
* 描述：有向無環(huán)圖的存儲(chǔ)，拓?fù)渑判? * 作者：@author huangpeng
* 時(shí)間：@create 2018-09-02 下午1:50
* 類名: Diagraph
* </pre>
**/
public class Diagraph {
public int V;
public int E;
public Bag<Integer>[] 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<Integer>[]) new Bag[V];
for(int v=0;v<V;v++){
adj[v] = new Bag<Integer>();
}
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<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
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<Integer> adj(int v){
return adj[v];
}
public Diagraph reverse(){
Diagraph R = new Diagraph(V);
for(int v=0;v<V;v++){
for(int w:adj(v)){
R.addEdge(w,v);
}
}
return R;
}
public String toString(){
StringBuilder s = new StringBuilder();
s.append(V+ " vertices, "+ E +" edges "+"\n");
for(int v=0;v<V;v++){
s.append(String.format("%d: ",v));
for(int w:adj[v]){
s.append(String.format("%d ",w));
}
s.append("\n");
}
return s.toString();
}
public int indegree(int nodeNumber){
return indegree[nodeNumber];
}
public int outDegree(int nodeNumber){
return outdegree[nodeNumber];
}
public void topologySort(){
Queue<Integer> queue = new LinkedList<Integer>();
int counter = 0;
for(int i=0;i<V;i++){
if(indegree[i]==0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int v = queue.poll();
num[v] = counter++;
for(int i=0;i<V;i++){
if(v!=i&&check(v,i)&&--indegree[i]==0){
queue.offer(i);
}
}
}
}
public boolean check(int v,int i){
Iterator iter = adj(v).iterator();
while(iter.hasNext()){
int value = (Integer) iter.next();
if(value == i){
return true;
}
}
return false;
}
public static void main(String[] args) {
Diagraph G = new Diagraph("/Users/huangpeng/workspace/javaproj/huangpengProj/src/com/algors/sap/maps/tinyDG1.txt");
System.out.println(G);
System.out.println("indegree:"+ Arrays.toString(G.getIndegree()));
System.out.println("outdegree:"+ Arrays.toString(G.getOutdegree()));
G.topologySort();
System.out.println("topology sort:"+Arrays.toString(G.num));
}
}
