数据结构之图

概念

图是一种非线性的数据结构。由顶点和边组成。

顶点（Vertex）：图的每一个节点就是顶点，也可以成为节点。

边（Edge）: 两个节点之间的连接叫边。

路径：节点到节点之间途径的节点叫路径。

环：起点和终点重合的路径叫做环。

度：对于无向图，顶点连接的边的数量叫做这个顶点的度。

入度：对于有向图，以顶点为终点的边数的数量叫做这个顶点的入度。

出度：对于有向图，以顶点为起点的边数的数量叫做这个顶点的出度。

有权值：对边赋予的各种属性，在不同问题中，权值可以代表距离、时间以及价格等不同的属性。如图所示
在这里插入图片描述

类型

图分两种类型：

无向图

边没有指向的图叫做无向图。如图所示：
在这里插入图片描述

有向图

顶点直接连接有方向的图叫做有向图。如图所示：
在这里插入图片描述

图的存储方式

图结构在代码中的存储方式有两种：二维数组表示邻接矩阵；链表表示（邻接表）

邻接矩阵

使用二位数组表示，创建最大节点数量的二位数组，0表示两个节点间不相连，1表示相连

有向图和无向图的邻接矩阵表示方法的区别：

无向图：对于无向图, 顶点i 和顶点 j连接，那么邻接矩阵G[i] [j] 和 G[j] [i]都为1.

有向图：对于有向图，顶点i 有一条边指向顶点 j, 那么邻接矩阵 G[i] [j] 为1，否则为0。

总结：无向图满足 G[i] [j] = G[j] [i], 有向图不满足 G[i] [j] = G[j] [i]。

邻接表

邻接表主要采用了数组+链表来存储属性结构，数组表示树的顶点，数组中每个元素的链表，这个顶点的关系

在这里插入图片描述

图的遍历

所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历

深度优先遍历（DFS）

概述

从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历是首先访问第一个邻接节点，然后再以这个被访问的邻接节点为初始节点，访问它的第一个邻接节点。可以理解为：每次都在访问当前节点后首先访问当前节点的第一个邻接节点. 类似于二叉树的前序遍历。

流程

如下图：访问步骤为

访问初始节点 0
访问 0 的第一个邻接节点 1
访问 1 的第一个邻接节点 4
访问 4 的第一个邻接节点，不存在
访问1的第二个邻接节点 3，
访问 3 的第一个邻接节点 1，已存在，则访问下一个，下一个没有了
访问 0 的第二个邻接节点 3，已访问过，则访问下一个 2.

访问顺序：0 -》 1- 》 4 -》 3 -》 2
在这里插入图片描述

广度优先遍历 (BFS)

概述

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点。类似于二叉树的分层遍历

流程

如下图：访问步骤为

访问初始节点 0
访问 0 的第一个邻接节点 1
访问 0 的第二个邻接节点 3
访问 0 的第三个邻接节点 2
访问 0 的第四个邻接节点，不存在
访问 1的第一个邻接节点4，

访问顺序：0 -》 1- 》 3 -》 2 -》 4

在这里插入图片描述

PriorityQueue 优先队列

主要有两种类型的优先级队列,分别为:PriorityQueue和PriorityBlockingQueue

PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的.
注意:

在使用PriorityQueue时必须要导入PriorityQueue所在的包:
import java.util.PriorityQueue;
虽然我们现在使用的IDE会自动导包,但是一些基础的还是要记一下,毕竟面试的时候是没有自动导包的.
PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException(类型转换异常).
不能插入null对象，否则会抛出NullPointerException(空指针异常)
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
PriorityQueue底层使用了堆数据结构(堆我会在第二部分进行讲解的)
PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素大堆—即每次获取到的元素都是最大的元素
总结：PriorityQueue 优先队列，并不遵循先进先出的队列标准，而是根据权重值来决定先出的元素。

Dijkstra(迪杰斯特拉)算法

概述

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存原点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T={}，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。

若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把其他所有s**不能直接到达的顶点的路径长度设为无穷大。**初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是原点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点。

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

代码


/**
 * 图-邻接表表示方法
 */
public class Graph01 {
    // 默认为无向图
    private static final boolean DETAULT_DIRECTION = false;
    // 顶点集合
    private List<Integer> vList;

    // 顶点数量
    private int V;

    // 边数
    private int E;

    // 图结构
    private Map<Integer, List<GraphNode>> adjMap;

     {
        V = 0;
        E = 0;
        adjMap = new HashMap<>();
         vList = Lists.newArrayList();
    }

    /**
     * 该顶点是否已经存在
     * @param v
     * @return
     */
    private boolean hasExistNode(int v){
         if (vList.contains(v)){
             return true;
         }
         return false;
    }

    /**
     * 判断该边是否已经存在
     * @return
     */
    private boolean hasExistNode(int source, int target){
        List<GraphNode> graphNodes = adjMap.get(source);
        if (CollectionUtils.isEmpty(graphNodes)){
            return false;
        }
        long count = graphNodes.stream().filter(v -> v.equals(target)).count();
        return count > 0;
    }

    /**
     * 判断边是否存在
     * @param source
     * @param target
     * @return
     */
    private boolean hasExistEdg(int source, int target){
        List<GraphNode> graphNodes = adjMap.get(source);
        if (CollectionUtils.isEmpty(graphNodes)){
            return false;
        }
        long count = graphNodes.stream().filter(v -> v.getVal() == target).count();
        return count > 0;
    }

    /**
     * 添加顶点
     * @param v
     */
    private void addV(int v){
        if (vList.contains(v)){
            return;
        }else {
            vList.add(v);
            V ++;
        }
    }

    /**
     * 添加有向边
     * @param source
     * @param target
     * @param weight
     */
    private void doAddDirectionEdg(int source, int target, int weight){
        addV(source);
        addV(target);
        GraphNode edg = new GraphNode(target, weight);
        List<GraphNode> graphNodes = Optional.ofNullable(adjMap.get(source)).orElse(Lists.newArrayList());
        graphNodes.add(edg);
        adjMap.put(source, graphNodes);
        E++;
    }

    /**
     * 添加无向边
     * @param source
     * @param target
     * @param weight
     */
    private void doAddNoDirectionEdg(int source, int target, int weight){
        addV(source);
        addV(target);
        GraphNode targetNode = new GraphNode(target, weight);
        GraphNode sourceNode = new GraphNode(source, weight);
        List<GraphNode> targetNodeList = Optional.ofNullable(adjMap.get(source)).orElse(Lists.newArrayList());
        targetNodeList.add(targetNode);
        adjMap.put(source, targetNodeList);
        List<GraphNode> sourceNodeList = Optional.ofNullable(adjMap.get(target)).orElse(Lists.newArrayList());
        sourceNodeList.add(sourceNode);
        adjMap.put(target, sourceNodeList);
        E+=2;
    }

    /**
     * 添加边-有权类型
     * @param source        起始顶点
     * @param target        目标顶点
     * @param weight        权重
     * @param hasDirection   是否是有向图：true-是，false-否
     */
    public void addEdg(int source, int target, int weight, boolean hasDirection){
        if (hasExistEdg(source, target)){
            return;
        }
        if (hasDirection){
            doAddDirectionEdg(source, target, weight);
        }else {
            doAddNoDirectionEdg(source, target, weight);
        }
        System.out.println();
    }


    public void printGraph(){
        System.out.println("当前图: 数量： "+ V +", 边数量： "+ E +",节点：{}"+ JSON.toJSONString(vList));
        adjMap.forEach((k,v) -> {
            System.out.println("当前图: 顶点："+ k + ",边：{}"+ JSON.toJSONString(v));
        });
    }


    /**
     * 深度遍历-dfs
     * @param v  初始节点v
     */
    public void dfs(int v, Set<Integer> hasVisited){
        if (!hasVisited.add(v)){
            // 已经访问过了
            return;
        }
        System.out.println("访问节点：" + v);
        List<GraphNode> graphNodes = adjMap.get(v);
        if (CollectionUtils.isEmpty(graphNodes)){
            // 已经访问到底了
            return;
        }
        for (GraphNode graphNode : graphNodes) {
            // 继续访问该节点的邻接节点
            dfs(graphNode.getVal(), hasVisited);
        }
    }

    /**
     * 广度遍历-bfs
     * 类似于二叉树的分层遍历
     * @param v  初始节点v
     */
    public void bfs(int v){
        Set<Integer> hasVisited = new HashSet<Integer>();
        if (!hasVisited.add(v)){
            // 已经访问过了
            return;
        }
        System.out.println("访问节点：" + v);
        List<GraphNode> graphNodes = adjMap.get(v);
        LinkedList<GraphNode> linkedList = mergeGraph(graphNodes);
        GraphNode node = linkedList.pollFirst();
        while (node != null){
            if (hasVisited.add(node.getVal())){
                System.out.println("访问节点：" + node.getVal());
                List<GraphNode> graphNodeList = adjMap.get(node.getVal());
                graphNodeList.forEach(val -> {
                    linkedList.addLast(val);
                });
            }
            node = linkedList.pollFirst();
            System.out.println("--");
        }


    }

    private LinkedList<GraphNode> mergeGraph(List<GraphNode> graphNodes){
        LinkedList<GraphNode> graphList = new LinkedList<>();
        if (!CollectionUtils.isEmpty(graphNodes)){
            for (GraphNode graphNode : graphNodes) {
                graphList.addLast(graphNode);
            }
        }
        return graphList;
    }


    // Dijkstra 算法实现，计算从 V1 到 V2 的最短路径和距离
    void dijkstra01(int src, int dest) {
        int[] dist = new int[V]; // 保存从源顶点到其他所有顶点的最小距离
        boolean[] visited = new boolean[V]; // 记录各顶点是否已被处理
        int[] prev = new int[V]; // 保存前驱节点，构建最短路径

        // 使用优先队列来高效选择最短路径顶点
        PriorityQueue<GraphNode> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

        // 初始化距离数组和前驱节点数组
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        dist[src] = 0;

        // 将源顶点加入优先队列
        pq.offer(new GraphNode(src, 0));

        while (!pq.isEmpty()) {
            GraphNode edge = pq.poll();
            int u = edge.getVal();

            // 顶点已被处理则跳过
            if (visited[u]) continue;

            // 标记顶点为已处理
            visited[u] = true;

            // 如果到达目标顶点，当前路径即为最短路径
            if (u == dest) {
                printPath(prev,  dest);
                return;
            }

            // 更新邻居顶点的距离信息
            for (GraphNode neighbor : adjMap.get(u)) {
                int v = neighbor.getVal();
                int weight = neighbor.weight;

                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    prev[v] = u; // 保存前驱节点
                    pq.offer(new GraphNode(v, dist[v]));
                }
            }
        }
    }

    // 打印路径的方法
    void printPath(int[] parent, int target) {
        if (parent[target] == -1) {
            System.out.print(target);
            return;
        }
        printPath(parent, parent[target]);
        System.out.print(" -> " + target);
    }

    /**
     * 图节点
     */
    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    private static class GraphNode{

        /**
         * 目标顶点
         */
        private int val;

        /**
         * 权重
         */
        private int weight;
    }

    public static void main(String[] args) {

        Graph01 graph01 = buildGraph01();
//        graph01.dfs(0, new HashSet<>());

        graph01.dijkstra01(0, 4);
    }



    public static Graph01 buildGraph02(){
        Graph01 graph = new Graph01();
        graph.addEdg(0, 1, 11, false);
        graph.addEdg(0, 3, 5, false);
        graph.addEdg(0, 2, 8, false);
        graph.addEdg(1, 4, 9, false);
        graph.addEdg(1, 3, 7, false);
        return graph;
    }


    public static Graph01 buildGraph01(){
        Graph01 graph = new Graph01();
        graph.addEdg(0, 1, 11, false);
        graph.printGraph();
        graph.addEdg(0, 2, 5, false);
        graph.printGraph();
        graph.addEdg(0, 3, 8, false);
        graph.printGraph();
        graph.addEdg(1, 3, 11, false);
        graph.printGraph();
        graph.addEdg(1, 4, 9, false);
        graph.printGraph();
        graph.addEdg(2, 3, 6, false);
        graph.printGraph();
        graph.addEdg(3, 4, 3, false);
        return graph;
    }

}