你好，我是小黃，一名獨(dú)角獸企業(yè)的Java開發(fā)工程師。
校招收獲數(shù)十個offer，年薪均20W~40W。
感謝茫茫人海中我們能夠相遇，
俗話說：當(dāng)你的才華和能力，不足以支撐你的夢想的時(shí)候，請靜下心來學(xué)習(xí)，
希望優(yōu)秀的你可以和我一起學(xué)習(xí)，一起努力，實(shí)現(xiàn)屬于自己的夢想。

一、前言

對于圖來說，我一直以來都似懂非懂

懂的是圖的含義，不懂的是圖具體的實(shí)現(xiàn)

對于當(dāng)前各大廠面試的圖題，不外乎以下幾點(diǎn)：

深度優(yōu)先搜索、廣度優(yōu)先搜索：DFS、BFS最小生成樹：Kruskal、Prim最短路徑：Dijkstra、Dijkstra加強(qiáng)堆版拓?fù)渑判颍篢opologicalSort

這幾個算法其實(shí)聽起來不太難懂，但真正寫代碼的時(shí)候會發(fā)現(xiàn)一個事情，傻逼圖的邊和點(diǎn)太難描述，導(dǎo)致我們寫著寫著人就沒了，繞進(jìn)去出不來了

本篇系列文章，將從對象的角度來描述一個圖的產(chǎn)生，并用最簡單的思路去介紹上述所有算法，讓我們走進(jìn)本篇文章吧。

二、什么是圖

圖是我們現(xiàn)實(shí)生活中連接關(guān)系的抽象，例如朋友圈、微博的關(guān)注關(guān)系。

簡單抽象如下圖所示：

對于圖來說，分為有向圖和無向圖，如下圖所示：

我們可以看出來，有向圖代表只能從一個頂點(diǎn)到達(dá)另一個頂點(diǎn)，而無向圖代表兩個頂點(diǎn)之間可以相互到達(dá)。

圖1中，V4到達(dá)V1，而V1無法到達(dá)V4

圖2中，V4到達(dá)V1，V1也可以到達(dá)V4

當(dāng)然，還有一種圖的形式，叫做：帶權(quán)圖（主要用來做一些路程、路費(fèi)的計(jì)算），如下圖所示：

三、怎么存儲一個圖的結(jié)構(gòu)

我們在刷題的時(shí)候，題目給我們的樣例經(jīng)常是這種的：743. 網(wǎng)絡(luò)延遲時(shí)間

題目會給我們一個二維的矩陣，一行矩陣有三個數(shù)字，分別是：起始點(diǎn)、終止點(diǎn)、權(quán)重

如何將這個二維的矩陣表示出來，成為了我們在做圖題目中比較困難的一件事

本文將直接使用一種特殊的表示形式來解決這個難題，我們先從最基本的 鄰接矩陣 和 鄰接表 表示開始

1、鄰接矩陣

鄰接矩陣是表示圖中頂點(diǎn)之間相鄰關(guān)系的矩陣。

對于無向圖的鄰接矩陣：對稱矩陣：int[][]

有向圖的鄰接矩陣：各行之和是出度，各列之和是入度

帶權(quán)圖的鄰接矩陣

2、鄰接表

鄰接表是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，類似于鏈表數(shù)組。

無向圖的鄰接表：HashMap<Integer, ArrayList<Integer>>

3、圖對象化表示

我們思考，上述兩個方法對于圖的表示形象嘛？

雖然有的題目在用矩陣表示的時(shí)候，做起來很舒服，但我們想一想，當(dāng)我們求最小生成樹時(shí)，利用邊的連接解鎖點(diǎn)時(shí)，用矩陣會
不會感覺很抽象難懂，所示，我們要自定義一個圖的表示方法，來增強(qiáng)我們對圖的理解

對于圖來說，我們想一想主要包括什么？

圖是由點(diǎn)和邊組成的一個結(jié)構(gòu)，也就是我們想要勾畫一個圖，必須有：點(diǎn)、邊

點(diǎn)的描述：

點(diǎn)的值：int value

鄰接的點(diǎn)：ArrayList<Node> nexts

鄰接的邊：ArrayList<Edge> edges

入度：int in

出度：int out

public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

邊的描述：

來自哪里：Node from去往哪里：Node to邊的權(quán)重：int weight

public class Edge {
    Node from;
    Node to;
    int weight;

    public Edge(Node from, Node to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

圖的描述：

多個點(diǎn)的集合：HashMap<Integer, Node> nodes多個邊的集合：Set<Edge> edges

public class Graph {
    public HashMap<Integer, Node> nodes;
    public Set<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

這里可能有疑問了，你這樣寫雖然形象，但是怎么進(jìn)行轉(zhuǎn)化呢？

別急，下面我們就進(jìn)行轉(zhuǎn)化。

public static Graph createGraph(int[][] matrix) {
        // 初始化一個圖
        Graph graph = new Graph();

        for (int[] arr : matrix) {
            // 來的點(diǎn)
            int from = arr[0];
            // 去的點(diǎn)
            int to = arr[1];
            // 權(quán)重
            int value = arr[2];

            // 生成相對應(yīng)的點(diǎn)
            Node fromNode = new Node(from);
            Node toNode = new Node(to);

            // 查看當(dāng)前有沒有這個點(diǎn)的信息
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, fromNode);
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, toNode);
            }

            // 生成一個邊(這里的邊是有向邊)
            Edge edge = new Edge(fromNode, toNode, value);

            // 點(diǎn)里面加入邊
            graph.nodes.get(from).edges.add(edge);

            //  點(diǎn)里面加入下一個點(diǎn)
            graph.nodes.get(from).nexts.add(toNode);

            // 點(diǎn)里面加入入度和出度
            graph.nodes.get(from).out++;
            graph.nodes.get(to).in++;

            // 圖里面加入邊
            graph.edges.add(edge);

        }
        return graph;
    }

當(dāng)我們轉(zhuǎn)化完的時(shí)候，進(jìn)行測試：

public static void main(String[] args) {
        int[][] arr = new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        Graph graph = createGraph(arr);
        // 從2開始的邊有哪些
        List<Edge> edgeList = graph.nodes.get(2).edges;
        for (Edge edge : edgeList) {
            System.out.println("從" + edge.from.value + "---->" + edge.to.value + "權(quán)值為" + edge.weight);
        }
    }

最終結(jié)果：

從2---->1權(quán)值為1
從2---->3權(quán)值為1

以后我們在做題的時(shí)候，都可以保存此轉(zhuǎn)化代碼，直接進(jìn)行調(diào)用即可

簡單形象的描繪了我們的圖

四、圖的作用

圖經(jīng)常用在以下地方：

• 深度優(yōu)先搜索、廣度優(yōu)先搜索：DFS、BFS
• 最小生成樹：Kruskal、Prim
• 最短路徑：Dijkstra、Dijkstra加強(qiáng)堆版
• 拓?fù)渑判颍篢opologicalSort

之后的章節(jié)會慢慢的講解以上所有的應(yīng)用

以上就是java算法圖的對象化描述示例詳解的詳細(xì)內(nèi)容，更多關(guān)于java圖的對象化描述算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論