圖的題目基礎類與方法

寫在最前

本文章的思路都是看左神的演算法課學到的，并不一定每個題目都會用到全部的屬性，比如邊沒有權重的時候邊類的weight就是用不上的，隨機應變才是王道，其中比較簡單的圖型別的題基本上圖構建出來了題目也就解得差不多了，希望能幫到大家，

點類

屬性解釋：
value：點的值
in：點的入度
out：點的出度
nexts：從此點出發能直接到達的點
edges：一般指與此點相連的邊，也可指代從此點出去或者進入的邊，具體情況具體分析

class Node {

    public int value;

    public int in;

    public int out;
    
    public ArrayList<Node> nexts;

    public ArrayList<Edge> edges;

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

}

邊類

屬性分析：
weight：邊的權重（權值）
from：邊的起始點
to：邊的終點
如果是無向圖的話即每一條邊對應本類的兩個物件，比如a-b之間可以表示為一條a到b的邊+一條b到a的邊

class Edge {
    public int weight;

    public Node from;

    public Node to;

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

圖類

nodes：圖的所有點，key為點的value
edges：圖的所有邊

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

    public HashSet<Edge> edges;

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

圖的創建方法（每道題有每道題的創建方法，這里只是給個例子）

	//根據鄰接矩陣創建圖
   private static Graph createGraph(int[][] arr) {
        Graph graph = new Graph();
        //先把點都添加到圖的點集中
        for (int i = 1; i <= arr.length; i++) {
            ArrayList<Node> nexts = new ArrayList<>();
            ArrayList<Edge> edges = new ArrayList<>();
            Node node = new Node(i,0,0,nexts,edges);
            graph.nodes.put(i,node);
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (i == j){
                    continue;
                }
                if (arr[i][j]!=0){
                    int tmp = arr[i][j];
                    Node node = graph.nodes.get(i);
                    Node node1 = graph.nodes.get(j);
                    node.out++;
                    node1.in++;
                    node.nexts.add(node1);
                    Edge edge = new Edge(tmp,node,node1);
                    node.edges.add(edge);
                    node1.edges.add(edge);
                    graph.edges.add(edge);
                }
            }
        }
        return graph;
    }

廣度優先遍歷

public static void bfs(Node node) throws InterruptedException {
        if (node == null) {
            return;
        }
        //佇列進行遍歷
        Queue<Node> queue = new Queue<>();
        //set輔助判斷是否遍歷過
        HashSet<Node> set = new HashSet<>();
        //入隊，入set
        queue.enqueue(node);
        set.add(node);
        while (!queue.isEmpty()){
            //出隊并輸出
            Node dequeue = queue.dequeue();
            System.out.println(dequeue.value);
            //遍歷該節點的后續節點
            for (Node next : dequeue.nexts) {
                if(!set.contains(next)){
                    queue.enqueue(next);
                    set.add(next);
                }
            }
        }

    }

深度優先遍歷

public static void dfs(Node node){
        if (node == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        stack.push(node);
        set.add(node);

        handle(node);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            for (Node next : pop.nexts) {
                if(!set.contains(next)){
                    stack.push(pop);
                    stack.push(next);
                    set.add(next);
                    handle(next);
                    break;
                }
            }
        }
    }