java开发经验-面向接口编程中迭代器的妙用
使用接口进行编程
定义接口
/** * 5:36:11 5:37:02 5:37:15 5:37:45 6:19:54 6:21:04 6:22:22 6:23:04 * @author Administrator * 访问权限 类 包 子类 其他包 描述 public ∨ ∨ ∨ ∨ 其它楼房的人也能用我, 外星人不能用我 protect ∨ ∨ ∨ × 只有我自己和与我住在同一个楼房里的人以及我的子孙能用我 default ∨ ∨ × × 只有我自己和与我住在同一个楼房里的人能用我 private ∨ × × × 只有我自己可以用我 * */ public interface Graph { public int V(); public int E(); public void addEdge(int v,int w); void show(); public boolean hasEdge(int v,int w); public Iterable<Integer> adj(int v); }通过定义迭代器对邻接矩阵和邻接表图的遍历操作进行了统一
邻接矩阵实现Graph
public class DenseGraph implements Graph{ private int[][] map; private int N; private int M; private boolean isdirected; public DenseGraph (int n, boolean isdirected) { super(); map = new int[N][N]; N = n; M = 0; this.isdirected = isdirected; } @Override public int V() { // TODO Auto-generated method stub return N; } @Override public boolean hasEdge(int v, int w) { // TODO Auto-generated method stub if(map[v-1][w-1]!=0) return true; return false; } @Override public Iterable<Integer> adj(int v) { // TODO Auto-generated method stub List<Integer> list = new ArrayList<>(); for(int i=0;i<N;i++) { if(map[v][i]==1) { list.add(i); } } return list; } @Override public int E() { // TODO Auto-generated method stub return M; } @Override public void show() { // TODO Auto-generated method stub for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { System.out.print(map[i][j]+"\t"); System.out.println(); } } } @Override public void addEdge(int v, int w) { // TODO Auto-generated method stub if(hasEdge(v,w)) return; map[v][w] =1; if(!isdirected) map[w][v] =1; M++; } }邻接表实现Graph
public class ListSparseGraph implements Graph{ private int N; private int M; private List<LinkedList<Integer>> totallist; private boolean isDirected; public ListSparseGraph(int n, boolean isDirected) { super(); N = n; this.M = 0; this.isDirected = isDirected; totallist = new ArrayList<>(); for(int i=0;i<N;i++) { totallist.add(new LinkedList<Integer>()); } } @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(int v, int w) { // TODO Auto-generated method stub if(hasEdge(v, w)) return; totallist.get(v).add(w); if(!isDirected) totallist.get(w).add(v); } @Override public void show() { // TODO Auto-generated method stub for(int i=0;i<N;i++) { /*for(int j =0;j<totallist.get(i).size();j++) { System.out.println(totallist.get(i)); }*/ System.out.print("vertex"+ i+":\t"); for(Integer item:totallist.get(i)) { System.out.print(item+"\t"); } System.out.println(); } } @Override public boolean hasEdge(int v, int w) { // TODO Auto-generated method stub for(Integer m:totallist.get(v)) { if(m==w) return true; } return false; } @Override public Iterable<Integer> adj(int v) { // TODO Auto-generated method stub return totallist.get(v); } }面向接口编程，传入不同实现的引用
public class Main { public static void main(String[] args) { // TestG1.txt String filename1 = "testG1.txt"; ListSparseGraph g1 = new ListSparseGraph(13, false); ReadGraph readGraph1 = new ReadGraph(g1, filename1); Compents component1 = new Compents(g1); System.out.println("TestG1.txt, Component Count: " + component1.count()); System.out.println(); // TestG2.txt String filename2 = "testG2.txt"; DenseGraph g2 = new DenseGraph(6, false); ReadGraph readGraph2 = new ReadGraph(g2, filename2); Compents component2 = new Compents(g2); System.out.println("TestG2.txt, Component Count: " + component2.count()); } }接受一个图的引用，因为迭代器可以使得对不同图的遍历操作达到了统一
public class Compents { Graph graph; private boolean[] visited; private int count; private int[] ids; public Compents(Graph graph) { this.graph = graph; int V = graph.V(); visited = new boolean[V]; ids = new int[V]; count = 0; for(int i=0;i<V;i++) { ids[i] = -1; } //connect numbers for(int i=0;i<V;i++) { if(!visited[i]) { DFS(i); count++; } } } private void DFS(int i) { // TODO Auto-generated method stub visited[i] = true; ids[i] = count; for(int item :graph.adj(i)) { //迭代器遍历图 if(!visited[item]) DFS(item); } } }
