首页 > 代码库 > 算法7-2:图论接口
算法7-2:图论接口
本节介绍如何在程序中表示一张图。
顶点
在程序中,顶点用整数表示就可以了。因为整数可以作为数组的下标,也可以作为哈希表的键。所以用整数是最方便的。
当然,在一张图中可能会出现一些异常情况,比如自己连接自己,两个顶点之间存在多个边。这些异常情况也是要考虑的。
接口
为了表示一张图,就要创建专门的对象来保存图。这个对象起名叫做Graph好了。它的接口是下面这样的。
public class Graph { // 创建一个带有V个顶点的图 Graph(int V); // 从输入流创建一张图,输入流的格式下文有介绍 Graph(In in); // 在两个顶点之间创建一条边。 void addEdge(int v, int w); // 获取一个顶点的邻居顶点 Iterable<Integer> adj(int v); // 获取这张图中顶点的数量 int V(); // 获取这张图中边的数量 int E(); // 将这张图表示成一个字符串,用于显示 String toString(); }
输入格式
接口中提到了可以从一个输入流创建一张图。那么这个输入流的格式应该怎样呢?首先第一行是一个整数,表示这个图顶点的数量,第二行是一个整数,表示边的数量,后面的每一行中都有两个整数,表示两个顶点之间有一条边。
设施
图论中有一些简单的操作,比如计算一个顶点的度(邻居节点数量),自连接的数量等。这些操作在后面的算法中都会用到。它们的代码如下:
public static int degree(Graph G, int v) { int count = 0; for (Integer e : G.adj(v)) count++; return count; } public static int maxDegree(Graph G) { int max = 0; for (int v = 0; v < G.V(); v++) { int d = degree(G, v); if (d > max) max = d; } return max; } public static int averageDegree(Graph G) { return G.E() * 2 / G.V(); } public static int numberOfSelfLoops(Graph G) { int count = 0; for (int v = 0; v < G.V(); v++) { for (int w : G.adj(v)) { if (v == w) { count++; } } } return count; }
数据结构
图主要有两种表示方法,一种是邻接矩阵,一种是邻接表。同学们别被这样的怪名字吓到,其实它们的本质都是数组或者链表。
邻接矩阵
邻接矩阵就是一个很大的二维数组a,它的维度和顶点数量相同。如果顶点数量是V,那么这个二维矩阵就是V×V大小。其中a[v][w]就表示了顶点v和顶点w是否相连,0表示没有连接,1表示相连。
邻接表
邻接表其实就是一个数组,数组中的每个元素都用来记录某个顶点有哪些邻居。
邻接表表示法的代码如下:
public class Graph { private List<Integer>[] adj; public Graph(int V) { adj = new LinkedList[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkedList<Integer>(); } } public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } public Iterable<Integer> adj(int v) { return adj[v]; } public int V() { return adj.length; } public int E() { int result = 0; for (List<Integer> each : adj) { result += each.size(); } return result; } @Override public String toString() { String result = ""; for (int i = 0; i < adj.length; i++) { result += i + ":"; for (int v : this.adj(i)) { result += " " + v; } result += "\n"; } return result; } }
实际应用中一般使用最多的就是邻接表,因为一般的应用顶点多而边数少。如果用邻接矩阵,内存浪费会很严重,因此实际应用中更加偏向于使用邻接表。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。