什么是图？
图是一种复杂的非线性结构。
在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。
也就是相互之间都可能有联系的一个关系网
图的表示
表示图有2个方法：邻接矩阵和邻接表
无向图表示
邻接矩阵
邻接表
有向图表示
邻接表
邻接表适合稀疏图，邻接矩阵适合稠密图
这是稀疏图，因为它并不是每个点都能与其他点构成关系，密度不够
稠密图或完全图，每个点之间几乎都构成关系
邻接矩阵的方式
//稠密图
//邻接矩阵方法
public class DenseGraph {
private int n; // 节点数
private int m; // 边数
private boolean directed;//是否为有向图
private boolean[][] g;//图的具体数据
public DenseGraph(int n , boolean directed){
assert n >= 0;//断言函数（用于强制必须有节点）
this.n = n;
this.m = m;//初始化没有边
this.directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
// false为boolean型变量的默认值
g = new boolean[n][n];
}
public int V(){
return n;//返回节点个数
}
public int E(){
return m;//返回边的个数
}
//向图添加边
//v,w是分别不同的顶点
public void addEdge(int v,int w){
assert v >=0 && v < n;//相对应边数小于节点数
assert w >=0 && w < n;//相对应边数小于节点数
if (hasEdge(v,w)){
return;
}
g[v][w] = true;
if (!directed){
g[w][v]=true;
}
m++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;//相对应边数小于节点数
assert w >= 0 && w < n ;//相对应边数小于节点数
return g[v][w];//判断边是否存在
}
}
邻接表方式
Vector 类实现了一个动态数组。和 ArrayList 很相似，
但是两者是不同的：
1、Vector 是同步访问的。
2、Vector 包含了许多传统的方法，这些方法不属于集合框架。
Vector 主要用在事先不知道数组的大小，或者只是需要一个可以改变大小的数组的情况。
import java.util.Vector;
//稀疏图
//邻接表
public class SparseGraph {
private int n;
private int m;
private boolean directed;
private Vector<Integer>[] g;
public SparseGraph(int n,boolean directed){
assert n >= 0;
this.n = n;
this.m = m;
this.directed = directed;
g = new Vector[n];//有n个边 所以有n个集合的数组
for (int i = 0;i<n;i++){
g[i] = new Vector<Integer>();//每个节点又有i个指向其他节点的值（划分为一个Vector）
}
}
public int V(){ return n;} // 返回节点个数
public int E(){ return m;} // 返回边的个数
// 向图中添加一个边
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// 验证图中是否有从v到w的边
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}
遍历邻边
邻接矩阵需要O(n)的复杂度
而邻接表需要O(1)
图的遍历
深度优先遍历（从一个点不停地寻找下一个节点，直到最后）
