首页 > 代码库 > 算法7-8:有向图接口
算法7-8:有向图接口
有向图和无向图在编程中的表示方法是差不多的,本问介绍邻接表表示方法。
有向图对象的代码轮廓如下:
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; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。