有向图和无向图在编程中的表示方法是差不多的,本问介绍邻接表表示方法。
有向图对象的代码轮廓如下:
public class Digraph { public Digraph(int v) { } // 创建v到w的边 public void addEdge(int v, int w) { } // 获取v能直接到达的顶点 public Iterable<Integer> adj(int v){ } // 获取整张图的顶点数量 public int V() { } // 获取整张图的边数 public int E() { } // 将整整图的方向反转 public Digraph reverse() { } @Override public String toString() { } }
这次用邻接表方法进行实现,代码和无向图是差不多的。
import java.util.LinkedList; import java.util.List; public class Digraph { private List<Integer>[] adj; private int v; public Digraph(int v) { adj = (List<Integer>[]) new LinkedList[v]; this.v = v; } // 创建v到w的边 public void addEdge(int v, int w) { adj[v].add(w); } // 获取v能直接到达的顶点 public Iterable<Integer> adj(int v) { return adj[v]; } // 获取整张图的顶点数量 public int V() { return v; } // 获取整张图的边数 public int E() { int result = 0; for (List<Integer> e : adj) { result += e.size(); } return result; } // 将整整图的方向反转 public Digraph reverse() { Digraph G = new Digraph(this.v); for (int v = 0; v < this.v; v++) { for (int w : adj(v)) { G.addEdge(w, v); } } return G; } @Override public String toString() { String result = ""; for (int v = 0; v < this.v; v++) { result += v + ":"; for (int w : adj(v)) { result += " " + w; } result += "\n"; } return result; } }
原文:http://blog.csdn.net/caipeichao2/article/details/32157577