java圖搜索算法之圖的對象化描述示例詳解

更新時間：2021年11月09日 09:47:11 作者：愛敲代碼的小黃

這篇文章主要為大家介紹了java圖搜索算法之圖的對象化描述示例詳解，可以帶你秒殺所有的圖搜索算法，有需要的朋友可以借鑒參考下，希望能夠有所幫助

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

一、前言

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

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

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

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

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

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

二、什么是圖

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

簡單抽象如下圖所示：

在這里插入圖片描述

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

在這里插入圖片描述

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

圖1中，V4到達V1，而V1無法到達V4

圖2中，V4到達V1，V1也可以到達V4

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

在這里插入圖片描述

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

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

在這里插入圖片描述

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

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

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

1、鄰接矩陣

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

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

在這里插入圖片描述

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

在這里插入圖片描述

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

在這里插入圖片描述

2、鄰接表

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

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

在這里插入圖片描述

3、圖對象化表示

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

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

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

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

點的描述：

點的值：int value

鄰接的點：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;
    }
}

圖的描述：

多個點的集合：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<>();
    }
}

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

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

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

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

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

            // 查看當(dāng)前有沒有這個點的信息
            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);

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

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

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

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

        }
        return graph;
    }

當(dāng)我們轉(zhuǎ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é)果：