亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

一、鄰接表

用鄰接矩陣來(lái)表示一個(gè)圖，雖然簡(jiǎn)單、直觀，但是比較浪費(fèi)存儲(chǔ)空間 。

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

還有，如果我們存儲(chǔ)的是稀疏圖（Sparse Matrix），也就是說(shuō)，頂點(diǎn)很多，但每個(gè)頂點(diǎn)的邊并不多， 那鄰接矩陣的存儲(chǔ)方法就更加浪費(fèi)空間了。比如微信有好幾億的用戶，對(duì)應(yīng)到圖上就是好幾億的頂點(diǎn)。 但是每個(gè)用戶的好友并不會(huì)很多，一般也就三五百個(gè)而已。如果我們用鄰接矩陣來(lái)存儲(chǔ)，那絕大部分的 存儲(chǔ)空間都被浪費(fèi)了 針對(duì)上面鄰接矩陣比較浪費(fèi)內(nèi)存空間的問(wèn)題，我們來(lái)看另外一種圖的存儲(chǔ)方法，鄰接表（Adjacency List）。

每個(gè)頂點(diǎn)對(duì)應(yīng)一條鏈表，鏈表中存儲(chǔ)的是與這個(gè)頂點(diǎn)相連接的其他頂點(diǎn)。

圖中畫的是一個(gè)有向圖的鄰接表存儲(chǔ)方式，每個(gè)頂點(diǎn)對(duì)應(yīng)的鏈表里面，存儲(chǔ)的是指向的頂點(diǎn)。 前面的數(shù)組存儲(chǔ)的是所有的頂點(diǎn)，每一個(gè)頂點(diǎn)后面連接的塊代表前面頂點(diǎn)所指向的頂點(diǎn)和路線的權(quán)值。

如果該點(diǎn)還指向其他頂點(diǎn)，則繼續(xù)在塊后面添加。例如A指向了B權(quán)值是4，那么A后面就加上一塊，之 后發(fā)現(xiàn)A還指向D權(quán)值是5，那么就在塊尾繼續(xù)添加一塊。其實(shí)也就是數(shù)組+鏈表的結(jié)構(gòu)。

根據(jù)鄰接表的結(jié)構(gòu)和圖，我們不難發(fā)現(xiàn)，圖其實(shí)是由頂點(diǎn)和邊組成的。所以我們就抽象出兩種類，一個(gè) 是Vertex頂點(diǎn)類，一個(gè)是Edge邊類。

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

/**
 * 邊
 */
public class Edge {
    String name; //被指向的頂點(diǎn)
    int weight; //弧的權(quán)值
    Edge next; //被指向的下一個(gè)邊
    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;

/**
 * 鄰接表實(shí)現(xiàn)
 */
public class Graph2 {
    Map<String, Vertex> vertexsMap; //存儲(chǔ)所有的頂點(diǎn)
    Graph2(){
        this.vertexsMap = new HashMap<>();
    }
    public void insertVertex(String vertexName){ //添加頂點(diǎn)
        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 + " 權(quán)值為：" + 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();
    }
}