图基础知识

前言

图是非常重要的一种数据结构，它是一种多对多的关系，相比线性表、树等，它是最复杂的一种数据结构。

图由顶点和边组成，顶点之间由边连接，如果边有方向，则称为有向图，反之则为无向图。

图的作用非常大，常用于计算最短路径，或者拓扑排序，最小生成树等等。

邻接链表

图有两种表示存储方法：

邻接链表
邻接矩阵

前言中的示意图为无向图，它的邻接链表示意图为：

对于图 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|²，则称图为稀疏图，反之则称为稠密图，一般来说，稠密图使用领接矩阵存储更好。

如果边太少，则不图中的矩阵有很多地方为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;
        }
    }
}

结语

两种图的存储方式各有优劣，矩阵方式下，非常容易知道两个顶点是否边相连，直接查询二维数组内的值即可，但邻接链表方式下，需要遍历链表才行。邻接链表的优势在于较省空间，而且非常形象。

图基础知识

推荐阅读更多精彩内容