图基础算法

本文参考了 黑马程序员的算法，地址: https://www.bilibili.com/video/BV1rv4y1H7o6?p=76&spm_id_from=pageDriver&vd_source=0af94caf33fbb7a6f7ddfcf5e8c205f4

1.图的基本表示

import lombok.Getter;
import lombok.Setter;
@Getter
@Setter
public class Edge {

    private Vertex linked;
    private int weight;

    public Edge(Vertex linked) {
        this(linked, 1);
    }

    public Edge(Vertex linked, int weight) {
        this.linked = linked;
        this.weight = weight;
    }
}

import lombok.Getter;
import lombok.Setter;

import java.util.List;

/**
 * @author laihaonan
 * @version 1.0
 * @description TODO
 * @date 2024/1/24 7:36 上午
 */
@Getter
@Setter
public class Vertex {

    private String name;
    private List<Edge> edges;
    private boolean isVisited;

    public Vertex(String name) {
        this.name = name;
    }
}

2.图的dfs遍历

    /**
     *              b   e
     *          a   c       g
     *              d   f
     * @return
     */
     public static void dfsStack(Vertex vertex, List<String> res) {
        LinkedList<Vertex> stack = new LinkedList();
        stack.push(vertex);
        while (!stack.isEmpty()) {
            Vertex pop = stack.pop();
            pop.setVisited(true);
            res.add(pop.getName());
            if (CollectionUtil.isNotEmpty(pop.getEdges())) {
                for (Edge edge : CollectionUtil.reverse(pop.getEdges())) {
                    if (!edge.getLinked().isVisited()) {
                        stack.push(edge.getLinked());
                    }
                }
            }
        }
    }

    private static void dfs(Vertex vertex, List<String> res) {
        vertex.setVisited(true);
        res.add(vertex.getName());
        if (CollectionUtil.isNotEmpty(vertex.getEdges())) {
            for (Edge edge : vertex.getEdges()) {
                if (!edge.getLinked().isVisited()) {
                    dfs(edge.getLinked(), res);
                }
            }
        }
    }

    private static Vertex initData() {
        Vertex a = new Vertex("a");
        Vertex b = new Vertex("b");
        Vertex c = new Vertex("c");
        Vertex d = new Vertex("d");
        Vertex e = new Vertex("e");
        Vertex f = new Vertex("f");
        Vertex g = new Vertex("g");

        Edge edgeb = new Edge(b);
        Edge edgec = new Edge(c);
        Edge edged = new Edge(d);
        Edge edgee = new Edge(e);
        Edge edgef = new Edge(f);
        Edge edgeg = new Edge(g);

        List<Edge> list = new ArrayList<>();
        list.add(edgeb);
        list.add(edgec);
        list.add(edged);
        a.setEdges(list);

        List<Edge> list2 = new ArrayList<>();
        list2.add(edgee);
        b.setEdges(list2);

        List<Edge> list3 = new ArrayList<>();
        list3.add(edgeg);
        c.setEdges(list3);

        List<Edge> list4 = new ArrayList<>();
        list4.add(edgef);
        d.setEdges(list4);

        List<Edge> list5 = new ArrayList<>();
        list5.add(edgeg);
        f.setEdges(list5);

        List<Edge> list6 = new ArrayList<>();
        list6.add(edgeg);
        e.setEdges(list6);
        return a;
    }

3.图的广度遍历

public static void bfsQueue(Vertex vertex, List<String> res) {
        LinkedList<Vertex> queue = new LinkedList<>();
        queue.offer(vertex);
        vertex.setVisited(true);
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            res.add(poll.getName());
            if (CollectionUtil.isNotEmpty(poll.getEdges())) {
                for (Edge edge : poll.getEdges()) {
                    if (!edge.getLinked().isVisited()) {
                        queue.offer(edge.getLinked());
                        edge.getLinked().setVisited(true);
                    }
                }
            }
        }
    }

4.Test

public static void main(String[] args) {
        Vertex vertex = initData();
        List<String> res = new ArrayList<>();
        dfs(vertex, res);
        System.out.println(JSON.toJSONString(res));

        List<String> res1 = new ArrayList<>();
        vertex = initData();
        dfsStack(vertex, res1);
        System.out.println(JSON.toJSONString(res1));
        
        List<String> res2 = new ArrayList<>();
        vertex = initData();
        bfsQueue(vertex, res2);
        System.out.println(JSON.toJSONString(res2));

        /**
         * 基础: LinkedList用于stack
         */
        List<String> stackRes = new ArrayList<>();
        LinkedList<String> list = new LinkedList();
        list.push("1");
        list.push("2");
        list.push("3");
        list.push("4");
        list.push("5");
        for (int i = 0; i < 5; i++) {
            stackRes.add(list.pop());
        }
        System.out.println(JSON.toJSONString(stackRes));

        /**
         * 基础: LinkedList用于queue
         */
        List<String> queueRes = new ArrayList<>();
        LinkedList<String> queue = new LinkedList();
        queue.push("1");
        queue.push("2");
        queue.push("3");
        queue.push("4");
        queue.push("5");
        for (int i = 0; i < 5; i++) {
            queueRes.add(queue.pollLast());
        }
        System.out.println(JSON.toJSONString(queueRes));
    }