日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

一、鄰接表

用鄰接矩陣來表示一個圖，雖然簡單、直觀，但是比較浪費存儲空間 。

對于無向圖來說，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。實際上，我們只需要存儲一個就可以了。 也就是說，無向圖的二維數組中，如果我們將其用對角線劃分為上下兩部分，那我們只需要利用上面或 者下面這樣一半的空間就足夠了，另外一半白白浪費掉了。

還有，如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊并不多， 那鄰接矩陣的存儲方法就更加浪費空間了。比如微信有好幾億的用戶，對應到圖上就是好幾億的頂點。 但是每個用戶的好友并不會很多，一般也就三五百個而已。如果我們用鄰接矩陣來存儲，那絕大部分的 存儲空間都被浪費了 針對上面鄰接矩陣比較浪費內存空間的問題，我們來看另外一種圖的存儲方法，鄰接表（Adjacency List）。

每個頂點對應一條鏈表，鏈表中存儲的是與這個頂點相連接的其他頂點。

圖中畫的是一個有向圖的鄰接表存儲方式，每個頂點對應的鏈表里面，存儲的是指向的頂點。 前面的數組存儲的是所有的頂點，每一個頂點后面連接的塊代表前面頂點所指向的頂點和路線的權值。

如果該點還指向其他頂點，則繼續在塊后面添加。例如A指向了B權值是4，那么A后面就加上一塊，之 后發現A還指向D權值是5，那么就在塊尾繼續添加一塊。其實也就是數組+鏈表的結構。

根據鄰接表的結構和圖，我們不難發現，圖其實是由頂點和邊組成的。所以我們就抽象出兩種類，一個 是Vertex頂點類，一個是Edge邊類。

/**
 * 頂點
 */
public class Vertex {
    String name; //頂點名稱
    Edge next; //從該定點出發的邊
    public Vertex(String name, Edge next){
        this.name = name;
        this.next = next;
    }
}

/**
 * 邊
 */
public class Edge {
    String name; //被指向的頂點
    int weight; //弧的權值
    Edge next; //被指向的下一個邊
    public Edge(String name, int weight, Edge next){
        this.name = name;
        this.weight = weight;
        this.next = next;
    }
}

package graph;

import JAVA.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * 鄰接表實現
 */
public class Graph2 {
    Map<String, Vertex> vertexsMap; //存儲所有的頂點
    Graph2(){
        this.vertexsMap = new HashMap<>();
    }
    public void insertVertex(String vertexName){ //添加頂點
        Vertex vertex = new Vertex(vertexName, null);
        vertexsMap.put(vertexName, vertex);
    }

    public void insertEdge(String begin, String end, int weight){
        //添加弧
        Vertex beginVertex = vertexsMap.get(begin);
        if(beginVertex == null){
            beginVertex = new Vertex(begin, null);
            vertexsMap.put(begin, beginVertex);
        }
        Edge edge = new Edge(end, weight, null);
        if(beginVertex.next == null){
            beginVertex.next = edge;
        }else{
            Edge lastEdge = beginVertex.next;
            while(lastEdge.next != null){
                lastEdge = lastEdge.next;
            }
            lastEdge.next = edge;
        }
    }

    public void print(){ //打印圖
        Set<Map.Entry<String, Vertex>> set = vertexsMap.entrySet();
        Iterator<Map.Entry<String, Vertex>> iterator = set.iterator();
        while(iterator.hasNext()){
            Map.Entry<String, Vertex> entry = iterator.next();
            Vertex vertex = entry.getValue();
            Edge edge = vertex.next;
            while(edge != null){
                System.out.println(vertex.name + " 指向 " + edge.name + " 權值為：" + edge.weight);
                edge = edge.next;
            }
        }
    }

    public static void main(String[] args) {
        Graph2 graph = new Graph2();
        graph.insertVertex("A");
        graph.insertVertex("B");
        graph.insertVertex("C");
        graph.insertVertex("D");
        graph.insertVertex("E");
        graph.insertVertex("F");
        graph.insertEdge("C", "A", 1);
        graph.insertEdge("F", "C", 2);
        graph.insertEdge("A", "B", 4);
        graph.insertEdge("E", "B", 2);
        graph.insertEdge("A", "D", 5);
        graph.insertEdge("D", "F", 4);
        graph.insertEdge("D", "E", 3);
        graph.print();
    }
}