前言
图是非常重要的一种数据结构，它是一种多对多的关系，相比线性表、树等，它是最复杂的一种数据结构。
图由顶点和边组成，顶点之间由边连接，如果边有方向，则称为有向图，反之则为无向图。
图的作用非常大，常用于计算最短路径，或者拓扑排序，最小生成树等等。
邻接链表
图有两种表示存储方法：
- 邻接链表
- 邻接矩阵
前言中的示意图为无向图，它的邻接链表示意图为：
对于图 G = (V， E) 来说，V代表顶点，E代表边，图是顶点和边的关系的集合。邻接链表是由包含 |V| 条链表的数组所构成。
链表中的第一个元素即是顶点，后续元素则为边。顶点代码定义如下：
public class Vertex {
public static enum COLOR{WHITE, BLACK, GRAY};
public Object info;
public int d;
public int f;
public COLOR color;
public Arc firstArc;//指向顶点的第一条边
public Vertex(Object info){
this.info = info;
}
}
边对象的代码为：
public class Arc {
public Vertex vertex;
public Arc next;
public int weight;
}
图的定义：
public static enum GRAPH_TYPE{digraph, undigraph};
public List<Vertex> mList;
public GRAPH_TYPE mType = GRAPH_TYPE.undigraph;
通过如上定义，邻接链表的存储方式就非常简单了，图中最重要的两个操作是增加点和增加边，且看看这两个方法的代码：
public void addVertex(Vertex vertex){
mList.add(vertex);
}
增加顶点的代码非常简单，直接添加到顶点列表当中即可。增加边稍微复杂一点，如果图的类型为无向图，那么还需要考虑反方向的边。
public void addArc(Vertex v, Vertex u, int weight){
Arc arc = new Arc();
arc.vertex = u;
arc.weight = weight;
arc.next = null;
if (v.firstArc == null) {
v.firstArc = arc;
}else {
Arc temp = v.firstArc;
while (temp.next != null) {
temp = temp.next;
}
temp.next = arc;
}
if (mType == GRAPH_TYPE.undigraph) {
Arc arc2 = new Arc();
arc2.vertex = v;
arc2.weight = weight;
arc2.next = null;
if (u.firstArc == null) {
u.firstArc = arc2;
}else {
Arc temp = u.firstArc;
while (temp.next != null) {
temp = temp.next;
}
temp.next = arc2;
}
}
}
邻接矩阵
邻接矩阵也是一种图的存储方式，图 G = (V， E) ，如果边的条数远远小于|V|2，则称图为稀疏图，反之则称为稠密图，一般来说，稠密图使用领接矩阵存储更好。
如果边太少，则不图中的矩阵有很多地方为0，则会浪费很多空间，因为稠密图用邻接矩阵表示。
邻接矩阵中，第A行第B列，则表示第A个元素与第B个元素是否有边相连通，如果有边相连通，则矩阵中的值为1，否则为0。无向图，如果AB两个顶点相连，那么不论从A到B，还是从B到A，都是相连的，所以无向图中的矩阵是对称的。因此可以使用半个矩阵来保存无向图。
边是可能有权重的，如果是权重图，那么矩阵中保存的值即是权重值。
邻接矩阵方式下，节点的定义类型可不变，需要重新定义边：
public class MatrixEdge {
public Vertex v1;
public Vertex v2;
public int weight;
}
边中增加了两个顶点，代表着边的指向，从v1到v2。
图的定义：
public List<Vertex> mList;
public GRAPH_TYPE mType = GRAPH_TYPE.undigraph;
public int maxLength;
public MatrixEdge[][] mEdges;
使用 mEdges 二维数组当矩阵，存储边的信息。
增加顶点：
public void addVertex(Vertex vertex){
mList.add(vertex);
}
增加边：
public void addEdge(Vertex v1, Vertex v2, int weight){
int index1 = mList.indexOf(v1);
int index2 = mList.indexOf(v2);
if (index1 >=0 && index2 >= 0) {
MatrixEdge edge = new MatrixEdge();
edge.v1 = v1;
edge.v2 = v2;
edge.weight = weight;
mEdges[index1][index2] = edge;
if (mType == GRAPH_TYPE.undigraph) {
MatrixEdge edge2 = new MatrixEdge();
edge2.v1 = v2;
edge2.v2 = v1;
edge2.weight = weight;
mEdges[index2][index1] = edge2;
}
}
}
结语
两种图的存储方式各有优劣，矩阵方式下，非常容易知道两个顶点是否边相连，直接查询二维数组内的值即可，但邻接链表方式下，需要遍历链表才行。邻接链表的优势在于较省空间，而且非常形象。
