定义 图是一组顶点和一组能够将两个顶点相连的边组成的。而把边仅仅是两个顶点的连接的图称为无向图。
无向图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];
}
}
