一.无向图 1.邻接表数据结构
1） 图中顶点用一个一维数组存储，当然也可以用单链表来存储，不过用数组可以较容易的读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2） 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为以vi为弧尾的出边表。
package sort; import edu.princeton.cs.algs4.Bag; import edu.princeton.cs.algs4.In; import edu.princeton.cs.algs4.StdOut; import java.util.NoSuchElementException; import java.util.Stack; public class Graph { private static final String NEWLINE = System.getProperty("line.separator"); private final int V; private int E; private Bag<Integer>[] adj; //创建一个含有V个顶点但不含有边的图 public Graph(int V) { if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative"); this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } } //从标准输入流in读入一幅图 public Graph(In in) { if (in == null) throw new IllegalArgumentException("argument is null"); try { this.V = in.readInt(); if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative"); adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } int E = in.readInt(); if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be nonnegative"); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); validateVertex(v); validateVertex(w); addEdge(v, w); } } catch (NoSuchElementException e) { throw new IllegalArgumentException("invalid input format in Graph constructor", e); } } //深拷贝一幅图 public Graph(Graph G) { this.V = G.V(); this.E = G.E(); if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative"); // update adjacency lists adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack<Integer> reverse = new Stack<Integer>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } //返回顶点数 public int V() { return V; } //返回边数 public int E() { return E; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } //向图中添加一条边v-w public void addEdge(int v, int w) { validateVertex(v); validateVertex(w); E++; adj[v].add(w); adj[w].add(v); } //和v相邻的所有顶点 public Iterable<Integer> adj(int v) { validateVertex(v); return adj[v]; } //返回顶点v的度数 public int degree(int v) { validateVertex(v); return adj[v].size(); } public String toString() { StringBuilder s = new StringBuilder(); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(v + ": "); for (int w : adj[v]) { s.append(w + " "); } s.append(NEWLINE); } return s.toString(); } public static void main(String[] args) { In in = new In(args[0]); Graph G = new Graph(in); StdOut.println(G); } }