无向图（一）

定义 图是一组顶点和一组能够将两个顶点相连的边组成的。而把边仅仅是两个顶点的连接的图称为无向图。

---

无向图API  
public class Graph
            Graph(int v)        //创建一个含有v个顶点但不含有边的图
            Graph(In in)        //从标准输入流in读入一幅图
       int  V()          //返回顶点数
       int  E()          //返回边数
       void addEdge(int v, int w)    //向图中添加一条边v-w
       Iterable<Integer> adj(int v)      //和v相邻的所有顶点
       String  toString()    //对象的字符串表示

API中包含两个构造函数，两个方法分别返回顶点数和边数，一个方法用来添加一条边，toString()和adj()遍历给定顶点的所有相邻顶点。
常用的图处理代码：

//计算v的度数
public static int degree(Graph G, int v){
    int degree = 0;
    for( int w; G.adj(v)) degree++;
    return degree;
}
//计算所有顶点的最大度数
public static int maxDegree(Graph G){
    int max = 0;
    for(int v= 0; v<G.v(); v++)
        if( degree(G,v) > max)
            max = degree(G, v);
    return max;
}
//计算所有顶点的平均度数
public static int aveDegree(Graph G){
    return 2.0 * G.E() / G.V();
}
//计算自环的个数
public static int numberOfSelfLoops(Graph G){
    int count;
    for(int v = 0; v<G.V();v++)
        for(int w : G.adj(v))
            if( v == w)  count++;
    return count/2;
}
//图的邻接表的字符串表示
public String toString(){
    String s = V + " verticles, " + E + " edges\n";
    for( int v = 0; v < V; v++){
        s += v + ": ";
        for(int w: this.adj(v))
            s += w+ " ";
        s += "\n";
    }
    return s;
}

---

** 图的表示方式 **
存储图并实现API的的数据结构需要满足一些要求：
1.它必须为可能在应用中碰到的各种类型的图保留出足够的空间；
2.Graph的实例方法实现速度要快。
基于以上两点我们可以考虑邻接表矩阵——使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表。

public class Graph{
    private final int V;          \\ 顶点数目
    private int E;                 \\ 边的数目
    private Bag<Integer>[]  adj;  \\邻接表
    public Graph(int V){
        this.V = V ; this.E = 0;
        adj = (Bag<Integer>[])  new Bag[V];      //创建邻接表
        for( int v = 0; v<V; v++){                    //将所有链表初始化为空
            adj[v] = new Bag<Integer>();
    }
    public Graph(In in){
        this(in.readInt());                  //读取v并将图初始化
        int E = in.readInt();              //读取E
        for(int i=0; i<E; i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v,w);
        }
    }
    public int V(){ return V;}
    public int E(){ return E;}
    public void addEdge(int v, int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
}