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

一、前言

對(duì)于圖來(lái)說(shuō)，我一直以來(lái)都似懂非懂

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

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

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

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

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

二、什么是圖

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

簡(jiǎn)單抽象如下圖所示：

對(duì)于圖來(lái)說(shuō)，分為有向圖和無(wú)向圖，如下圖所示：

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

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

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

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

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

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

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

如何將這個(gè)二維的矩陣表示出來(lái)，成為了我們?cè)谧鰣D題目中比較困難的一件事

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

1、鄰接矩陣

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

對(duì)于無(wú)向圖的鄰接矩陣：對(duì)稱矩陣：int[][]

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

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

2、鄰接表

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

無(wú)向圖的鄰接表：HashMap<Integer, ArrayList<Integer>>

3、圖對(duì)象化表示

我們思考，上述兩個(gè)方法對(duì)于圖的表示形象嘛？

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

對(duì)于圖來(lái)說(shuō)，我們想一想主要包括什么？

圖是由點(diǎn)和邊組成的一個(gè)結(jié)構(gòu)，也就是我們想要勾畫一個(gè)圖，必須有：點(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<>();
    }
}

邊的描述：

來(lái)自哪里：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;
    }
}

圖的描述：

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

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

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

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

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

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

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

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

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

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

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

            //  點(diǎn)里面加入下一個(gè)點(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)行測(cè)試：

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

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

簡(jiǎn)單形象的描繪了我們的圖

四、圖的作用

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

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

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

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

最新評(píng)論