存储结构

要存储一个图，我们知道图既有结点，又有边，对于有权图来说，每条边上还带有权值。常用的图的存储结构主要有以下二种：

• 邻接矩阵
• 邻接表

上一篇文章《图的理解：存储结构与邻接矩阵的Java实现》用的是邻接矩阵的形式实现的，这次用邻接表来存储

30adcbef76094b36d054d85ba0cc7cd98c109d46.jpg

就如上图所示，表头节点表示源节点，后面跟的就是他能到达的节点，比如A,他能到达1,2,3节点，而有向图和无向图最大的区别，就是方向，无向图A->B，也一定有B->A,在有向图中就不一定，这次介绍带权重的有向图的邻接表表示。

首先要表示图，首先要定义图的边

//带权重的有向图
public class DirectedEdge {
    private int v; //边的起点
    private int w; //边的终点

    private double weight;//边的权重

    public DirectedEdge(int v,int w,double weight){
        this.v=v;
        this.w=w;
        this.weight=weight;
    }

    public int from(){
        return v;
    }

    public int to(){
        return w;
    }

    public double weight(){
        return weight;
    }

    @Override
    public String toString() {
        return String.format("%d->%d% .2f",v,w,weight);
    }
}

这里跟上图表示的有点不一样，我把两个顶点都保留下来啦，如果不需要权重，去掉weight就行

定义完图的边，就需要定义图

public class EdgeWeightDigraph {
    public int v;//顶点的个数
    public int e; //边的个数

    public ArrayList<DirectedEdge> [] adj; //邻接表

    public EdgeWeightDigraph(int v){
        this.v=v;
        this.e=e;
        adj=new ArrayList[v];
        for(int i=0;i<v;i++){
            adj[i]=new ArrayList<DirectedEdge>();
        }
    }

    /**
     * 添加边
     * @param e
     */
    public void addEdge(DirectedEdge e){
        adj[e.from()].add(e);
        this.e++;
    }

    public void printEdge(){
        for(int i=0;i<v;i++){
            for(DirectedEdge e:adj[i]){
                System.out.println(e+" ");
            }
        }

    }
   public static void main(String[] args){
         EdgeWeightDigraph graph=new EdgeWeightDigraph(5);

          DirectedEdge e=new DirectedEdge(0,1,1);
          DirectedEdge e1=new DirectedEdge(0,2,1);
          DirectedEdge e2=new DirectedEdge(1,2,1);
          DirectedEdge e3=new DirectedEdge(2,3,1);
          DirectedEdge e4=new DirectedEdge(3,4,1);

        graph.addEdge(e);
        graph.addEdge(e1);
        graph.addEdge(e2);
        graph.addEdge(e3);
        graph.addEdge(e4);

        graph.printEdge();

    }
}

这里我用list集合来表示邻接表，添加边时，e.from表示源边，在它的集合里保存边即可

控制台输出结果如下图所示：

result.png