存儲結構

要存儲一個圖，我們知道圖既有結點，又有邊，對于有權圖來說，每條邊上還帶有權值。常用的圖的存儲結構主要有以下二種：

• 鄰接矩陣
• 鄰接表

上一篇文章《圖的理解：存儲結構與鄰接矩陣的Java實現(xiàn)》用的是鄰接矩陣的形式實現(xiàn)的，這次用鄰接表來存儲

30adcbef76094b36d054d85ba0cc7cd98c109d46.jpg

就如上圖所示，表頭節(jié)點表示源節(jié)點，后面跟的就是他能到達的節(jié)點，比如A,他能到達1,2,3節(jié)點，而有向圖和無向圖最大的區(qū)別，就是方向，無向圖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;//頂點的個數(shù)
    public int e; //邊的個數(shù)

    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