Java实现图的存储与基本操作

概述

今天花了点时间，将数据结构中比较经典的图的基本应用用Java实现了一下，记录一下。因为觉得图的数据结构是比较经典的。其实，主要是好像面试似乎会弄得很多。准备一点也好。
数据结构里面，图的存储方式其实是有很多的。在以前考408的时候，复习了的就有四种，分别是邻接矩阵法，邻接表法，十字链表法和邻接多重法。不过今天只准备实现两种最常用的邻接矩阵和邻接表法。因为这两种是用的最频繁的，难度其实也比另外两种小。

邻接矩阵

所谓的邻接矩阵存储，就是用一个一维数组来存储图中顶点的信息，而用一个二维数据存储图中边的信息(也就是各个顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称之为邻接矩阵。
以下用一个无向图的邻接矩阵作为示例:

很明显的能看出来该无向图的邻接矩阵是一个对称矩阵。其实这也是很好理解的。从V0到V1有距离必然意味着V1到V0是有距离的。

而有向图的邻接矩阵可看如下图所示:

可以看出来有向图其实并不是对称的。另外如果这个有向图是有权值的话，矩阵中的数字1也是可以替换成其他的数字的。

我写了一个AMGraph的实现类，主要是邻接矩阵的生成初始化以及简单的插入删除边和节点的操作。

import java.util.*;
/**
 * @author WorthyYao
 * @date 2016/9/26
 */
public class AMGraph {
    private ArrayList vertexList;
    private int[][] edges;
    private int numsEdge;
    //初始化邻接矩阵
    public AMGraph(int n){
        edges=new int[n][n];
        vertexList=new ArrayList(n);
        numsEdge=0;
    }
    //返回图中点的数目
    public int getNumOfVertix(){
        return vertexList.size();
    }
    //返回图中边的条数
    public int getNumOfEdge(){
        return numsEdge;
    }
    //增加图中的点
    public void insertVertex(Object vertex) {
        vertexList.add(vertexList.size(),vertex);
    }
    //在图中插入一条边
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        numsEdge++;
    }
    //在图中删除一条边
    public void removeVertix(int v1,int v2){
        edges[v1][v2]=0;
        numsEdge--;
    }
}

邻接表

在一个图是稀疏图的时候，使用邻接矩阵来表示一个图其实是很浪费存储空间的。咋办，邻接表法主要就是用来解决这个问题的。
所谓的邻接表，其实是将图中所有顶点组合起来做成一个单链表。而第i个单链表中的结点则表示依附于顶点Vi的边，这样的链表就可以称之为顶点Vi的边表。比如上面那个无向图的邻接表就可以如下所示:

实现

给出一个有向图如下所示，可以写出他的邻接矩阵和邻接表的实现方法以及邻接矩阵的插入删除操作。

/**
 * @author WorthyYao
 * @date 2016/9/26
 */
public class Main {
    public static void main(String[] args) {
        //初始化图
        AMGraph amg=new AMGraph(4);
        //初始化四个节点
        String[] vertexs={"v1","v2","v3","v4"};
        for (int i=0;i<vertexs.length;i++){
            amg.insertVertex(vertexs[i]);
        }
        //插入四条边
        amg.insertEdge(0,1,2);
        amg.insertEdge(0,2,5);
        amg.insertEdge(2,3,8);
        amg.insertEdge(3,0,7);
        System.out.println("图中顶点数为: "+amg.getNumOfVertix());
        System.out.println("图中边的数目为: "+amg.getNumOfEdge());
        amg.removeVertix(2,3);
        System.out.println("在删除一条边后的总边数为: "+amg.getNumOfEdge());

    }
}

运行结果如下:

而邻接表的矩阵初始化则如下代码所示:

/**
 * @author WorthyYao
 * @date 2016/9/26
 */
//邻接表中表对应的链表的结构
class Enode{
    //初始化邻接表中顶点的名称以及值
    String vertex;
    int value;
    Enode next;
}
class Vnode{
    String vertex;
    Enode firstEdge;
}

//邻接表中图的存储
public class ALGraph {
    public static void main(String[] args) {
        String[] vertexs={"v1","v2","v3","v4"};
        Vnode[] vers=new Vnode[vertexs.length];
        //初始化链表
        for(int i=0;i<vertexs.length;i++){
            vers[i].vertex=vertexs[i];
            vers[i].firstEdge=null;
        }
        //插入几条边，初始化邻接表图
        Enode node1=new Enode();
        Enode node2=new Enode();
        Enode node3=new Enode();
        Enode node4=new Enode();
        node1.vertex="v2";node1.value=2;
        node2.vertex="v2";node2.value=5;
        node3.vertex="v4";node1.value=8;
        node4.vertex="v1";node1.value=7;
        vers[0].firstEdge=node1;
        node1.next=node2;
        vers[2].firstEdge=node3;
        vers[3].firstEdge=node4;
    }
}