算法之美-java有权图的表示
直接表示法
测试用例
8 16 4 5 .35 4 7 .37 5 7 .28 0 7 .16 1 5 .32 0 4 .38 2 3 .17 1 7 .19 0 2 .26 1 2 .36 1 3 .29 2 7 .34 6 2 .40 3 6 .52 6 0 .58 6 4 .93 import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Scanner; /** //int num = (new Double(0.999999)).intValue(); //0 //int num = (int）0.999999;//0 Double db = new Double(1);//1.0 int num = db.intValue(); System.out.println(num);//1 * @author Administrator *18:57:03 18:58:26 18:59:06 19:19:52 */ public class ListWeigthGraph { static List<List<Double[]>> totallist; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int M = scanner.nextInt(); totallist = new ArrayList<>(); for(int i=0;i<N;i++) { totallist.add(new LinkedList<>()); } for(int i=0;i<M;i++) { int s = scanner.nextInt(); Double ds = Double.valueOf(s); int e = scanner.nextInt(); Double de = Double.valueOf(e); double w = scanner.nextDouble(); totallist.get(s).add(new Double[] {ds,de,w}); //无向图 //totallist.get(e-1).add(new Double[] {de,ds,w}); } //遍历图的信息 for(int i=0;i<totallist.size();i++) { for(int j=0;j<totallist.get(i).size();j++) { Double[] item = totallist.get(i).get(j); int startIndex = item[0].intValue(); int toIndex = item[1].intValue(); double weight = item[2]; ....//业务信息 } } } }输出：
面向对象表示法
定义有权图的接口
/** * 18:32:34 18:33:22 18:33:48 18:34:43 18:36:33 18:36:51 18:37:51 18:38:19 * 18:38:56 18:39:56 18:40:29 18:43:18 4:19:45 4:21:38 4:45:25 * @author Administrator * */ public interface WeightedGraph<Weight extends Number & Comparable> { public int V(); public int E(); public void addEdge(Edge<Weight> e); void show(); public Iterable<Edge<Weight>> adj(int v); }定义边
public class Edge <Weight extends Number & Comparable> implements Comparable<Edge>{ private int a,b; private Weight weight; public Edge(int a, int b, Weight weight) { super(); this.a = a; this.b = b; this.weight = weight; } public Edge() { super(); } public Edge(Edge<Weight> e) { super(); this.a = e.a; this.b = e.b; this.weight = e.weight; } public int getV() { return a; } public int getW() { return b; } public Weight getWeight() { return weight; } public int other(int x) { assert x==a||x==b; return x==a?b:a; } @Override public String toString() { return "Edge [a=" + a + ", b=" + b + ", weight=" + weight + "]"; } @Override public int compareTo(Edge that) { // TODO Auto-generated method stub if(weight.compareTo(that.getWeight())<0) { return -1; }else if(weight.compareTo(that.getWeight())>0) { return 1; }else return 0; } }定义图
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /** * 4:56:59 4:58:00 4:59:44 5:02:54 5:05:41 5:06:10 5:07:38 5:08:56 5:09:42 * @author Administrator * @param <Weight> * */ public class SparseWeightedGraph<Weight extends Number & Comparable> implements WeightedGraph{ private int n;//结点数 private int m;//边数 private boolean isdirected; private List<List<Edge<Weight>>> totallist; public SparseWeightedGraph(int n, boolean isdirected) { super(); this.n = n; this.m = 0; this.isdirected = isdirected; totallist = new ArrayList<>(); for(int i=0;i<n;i++) { totallist.add(new LinkedList()); } } @Override public int V() { // TODO Auto-generated method stub return n; } @Override public int E() { // TODO Auto-generated method stub return m; } @Override public void addEdge(Edge e) { // TODO Auto-generated method stub totallist.get(e.getV()).add(new Edge(e)); if(e.getV()!=e.getW()&&!isdirected) { totallist.get(e.getW()).add(new Edge(e.getW(),e.getV(),e.getWeight())); } m++; } // 验证图中是否有从v到w的边 public boolean hasEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; for( int i = 0 ; i < totallist.get(v).size() ; i ++ ) if( totallist.get(v).get(i).other(v) == w ) return true; return false; } @Override // 显示图的信息 public void show(){ for( int i = 0 ; i < n ; i ++ ){ System.out.print("vertex " + i + ":\t"); for( int j = 0 ; j < totallist.get(i).size() ; j ++ ){ Edge e =totallist.get(i).get(j); System.out.print( "( to:" + e.other(i) + ",wt:" + e.getWeight() + ")\t"); } System.out.println(); } } @Override public Iterable<Edge<Weight>> adj(int v) { // TODO Auto-generated method stub return null; } }读图
import java.io.BufferedInputStream; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.util.Scanner; import java.util.Locale; import java.util.InputMismatchException; import java.util.NoSuchElementException; /* * 4:44:46 */ // 通过文件读取有全图的信息 public class ReadWeightedGraph{ private Scanner scanner; // 由于文件格式的限制，我们的文件读取类只能读取权值为Double类型的图 public ReadWeightedGraph(WeightedGraph<Double> graph, String filename){ readFile(filename); try { int V = scanner.nextInt(); if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative"); assert V == graph.V(); int E = scanner.nextInt(); if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be nonnegative"); for (int i = 0; i < E; i++) { int v = scanner.nextInt(); int w = scanner.nextInt(); Double weight = scanner.nextDouble(); assert v >= 0 && v < V; assert w >= 0 && w < V; graph.addEdge(new Edge<Double>(v, w, weight)); } } catch (InputMismatchException e) { String token = scanner.next(); throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\""); } catch (NoSuchElementException e) { throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available"); } } private void readFile(String filename){ assert filename != null; try { File file = new File("src/"+filename); if (file.exists()) { FileInputStream fis = new FileInputStream(file); scanner = new Scanner(new BufferedInputStream(fis), "UTF-8"); scanner.useLocale(Locale.ENGLISH); } else throw new IllegalArgumentException(filename + " doesn't exist."); } catch (IOException ioe) { throw new IllegalArgumentException("Could not open " + filename, ioe); } } } public class Main { // 测试通过文件读取图的信息 public static void main(String[] args) { // 使用两种图的存储方式读取testG1.txt文件 String filename = "testG1.txt"; SparseWeightedGraph<Double> g1 = new SparseWeightedGraph<Double>(8, false); ReadWeightedGraph readGraph1 = new ReadWeightedGraph(g1, filename); System.out.println("test G1 in Sparse Weighted Graph:"); g1.show(); System.out.println(); } }输出：
