图的题目基础类与方法

写在最前

本文章的思路都是看左神的算法课学到的，并不一定每个题目都会用到全部的属性，比如边没有权重的时候边类的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;
                }
            }
        }
    }