Graph的基本表示

邻接矩阵和邻接表

1 邻接矩阵

邻接矩阵： A[i][j] = 1 代表i点和j点之间存在边， A[i][j]= 0 代表i点和j点不存在边。邻接矩阵是一个A[V][V]的数组，空间占用O(v*v)。 其代码表示方法：

private int V; private int E; private int[][] adj; public AdjMatrix(String fileName) { File file = new File(fileName); try { Scanner scanner = new Scanner(file); V = scanner.nextInt(); Preconditions.checkArgument(V > 0, "V must be positive"); E = scanner.nextInt(); Preconditions.checkArgument(E > 0, "E must be postive"); adj = new int[V][V]; for (int i = 0; i < E; i++) { int a = scanner.nextInt(); validVertex(a); int b = scanner.nextInt(); validVertex(b); Preconditions.checkArgument(a != b, "Self edge detected"); Preconditions.checkArgument(adj[a][b] != 1, "平行边detected"); adj[a][b] = 1; adj[b][a] = 1; } } catch (FileNotFoundException e) { e.printStackTrace(); } } private void validVertex(int a) { Preconditions.checkArgument(a >= 0 && a < V, "vertex id invalid"); }

2 邻接表

邻接表在稀疏图的情况下，将极大减少内存占用空间， 而往往现实生活中绝大部分都是稀疏图。邻接表其存储是通过链表存储邻接点信息。根据邻接表的数据结结构不同，有不同的实现方式， 分别可以是HashSet, LinkedList, TreeSet HashSet代码如下图所示

private int V; private int E; private HashSet<Integer>[] adj; public AdjHashSet(String fileName) { File file = new File(fileName); try { Scanner scanner = new Scanner(file); V = scanner.nextInt(); Preconditions.checkArgument(V > 0, "V must be positive"); E = scanner.nextInt(); Preconditions.checkArgument(E > 0, "E must be postive"); adj = new HashSet[V]; for (int i = 0; i < V; i++) { adj[i] = new HashSet<>(); } for (int i = 0; i < E; i++) { int a = scanner.nextInt(); validVertex(a); int b = scanner.nextInt(); validVertex(b); Preconditions.checkArgument(a != b, "Self edge detected"); Preconditions.checkArgument(!adj[a].contains(b), "平行边detected"); adj[a].add(b); adj[b].add(a); } } catch (FileNotFoundException e) { e.printStackTrace(); } } private void validVertex(int a) { Preconditions.checkArgument(a >= 0 && a < V, "vertex id invalid"); }

LinkedList代码如下

private int V; private int E; private LinkedList<Integer>[] adj; public AdjLinkedList(String fileName) { File file = new File(fileName); try { Scanner scanner = new Scanner(file); V = scanner.nextInt(); Preconditions.checkArgument(V > 0, "V must be positive"); E = scanner.nextInt(); Preconditions.checkArgument(E > 0, "E must be postive"); adj = new LinkedList[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkedList<>(); } for (int i = 0; i < E; i++) { int a = scanner.nextInt(); validVertex(a); int b = scanner.nextInt(); validVertex(b); Preconditions.checkArgument(a != b, "Self edge detected"); Preconditions.checkArgument(!adj[a].contains(b), "平行边detected"); adj[a].add(b); adj[b].add(a); } } catch (FileNotFoundException e) { e.printStackTrace(); } } private void validVertex(int a) { Preconditions.checkArgument(a >= 0 && a < V, "vertex id invalid"); }

TreeSet如下

private int V; private int E; private TreeSet<Integer>[] adj; public AdjTreeset(String fileName) { File file = new File(fileName); try { Scanner scanner = new Scanner(file); V = scanner.nextInt(); Preconditions.checkArgument(V > 0, "V must be positive"); E = scanner.nextInt(); Preconditions.checkArgument(E > 0, "E must be postive"); adj = new TreeSet[V]; for (int i = 0; i < V; i++) { adj[i] = new TreeSet<>(); } for (int i = 0; i < E; i++) { int a = scanner.nextInt(); validVertex(a); int b = scanner.nextInt(); validVertex(b); Preconditions.checkArgument(a != b, "Self edge detected"); Preconditions.checkArgument(!adj[a].contains(b), "平行边detected"); adj[a].add(b); adj[b].add(a); } } catch (FileNotFoundException e) { e.printStackTrace(); } } private void validVertex(int a) { Preconditions.checkArgument(a >= 0 && a < V, "vertex id invalid"); }