数据结构之图结构解最短路径

不念不忘少年蓝@ 2024-02-19 21:20 46阅读 0赞

### 图结构 ###

1.  邻接矩阵：可以理解为一个二维数组，即一个正方形的图。例如：动态规划解LCS最长公共子序列，实现代码见：[https://blog.csdn.net/u010597819/article/details/86646297][https_blog.csdn.net_u010597819_article_details_86646297]
2.  邻接表：将二维数组中的其中一维换成链表结构，即不定长度。主要用于非稠密（稀疏的）的图结构，减少资源浪费，案例取自《数据结构与算法分析 java语言描述》例如：假设一个城镇街道是曼哈顿式（见下图），并且街道均是双向的，则顶点与边的关系为|E|≈|4V|，一个3000个顶点的图，该图有12000条边是实际有效的数据。如果使用邻接矩阵表示则需要一个3000\*3000的二维数组，也就是大小为9000000的数组。也就是存在大量的无效数据。此时使用邻接表更为合适![aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAxOS9qcGVnLzIyODAyMy8xNTY0MTk0MzUwOTIzLTg3NDdlOGQxLWM3ZjItNDA1Ny1iOGMxLWJkNDIzZDJhNjg1YS5qcGVn_align_left_display_inline_height_405_originHeight_405_originWidth_405_size_0_status_done_width_405][]

### 图遍历 ###

1.  广度优先遍历：先遍历邻接顶点数据，再继续遍历邻接顶点的邻接顶点。也就是先遍历邻接顶点距离最近的顶点再遍历距离远的顶点
2.  深度优先遍历：先遍历邻接顶点集合中第一个邻接顶点以及所有子邻接顶点。继续遍历第二个临街顶点以及之后的。也就是先遍历邻接顶点距离最远的顶点再遍历距离近的顶点

遍历均需要考虑环路问题

### 最短路径算法 ###

下图引用自《数据结构与算法分析 java语言描述》，对应案例中无权初始化的图结构。案例中有权初始化对应的v4节点的权重为-3。  
![image.png][]

#### 顶点与邻接链表（边） ####

package com.gallant.dispatch.graph;
    
    import java.util.List;
    import lombok.Builder;
    import lombok.Getter;
    import lombok.Setter;
    
    /**
     * @author 会灰翔的灰机
     * @date 2019/7/25
     */
    @Getter
    @Setter
    @Builder
    public class Vertex {
        
    
        /**
         * 邻接表
         */
        private List<Vertex> vertexList;
    
        private Integer key;
        /**
         * 指定某个源点，源点至到当前节点的最短路径长度
         */
        private Integer shortestPathLen;
        /**
         * 当前节点权重值
         */
        private Integer weight;
        /**
         * 当前正在被扫描
         */
        private boolean walking;
    
        @Override
        public String toString() {
        
            return String.format("%s(%s)", key, shortestPathLen);
        }
    }

#### 图与最短路径算法 ####

package com.gallant.dispatch.graph;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.Queue;
    import java.util.Set;
    import java.util.concurrent.ArrayBlockingQueue;
    import lombok.Getter;
    import lombok.Setter;
    import org.apache.commons.collections4.CollectionUtils;
    
    /**
     * @author 会灰翔的灰机
     * @date 2019/7/25
     */
    @Getter
    @Setter
    public class Graph {
        
    
        /**
         * 图结构，使用map为了方便初始化测试，可以直接根据key获取对应的节点链
         * key: 顶点的value值
         * value: 邻接表
         */
        private Map<Integer, Vertex> graph;
    
        public void add(Vertex vertex) {
        
            if (graph == null) {
        
                graph = new HashMap<>();
            }
            graph.put(vertex.getKey(), vertex);
        }
    
        /**
         * 无权图初始化(即权重相等的情况)
         * 有环路，无负值圈
         */
        public void initNoWeight(){
        
            for (int i=0; i<7; i++) {
        
                this.add(Vertex.builder().key(i+1).weight(1).build());
            }
            add(1, 2, 4);
            add(2, 4, 5);
            add(3, 1, 6);
            add(4, 3, 5, 6, 7);
            add(5, 7);
            add(7, 6);
        }
    
        /**
         * 有权图初始化(即权重不相等的情况)
         * 有环路，有负值圈
         */
        public void initWeight(){
        
            for (int i=0; i<7; i++) {
        
                this.add(Vertex.builder().key(i+1).weight(1).build());
            }
            graph.get(4).setWeight(-3);
            add(1, 2);
            add(2, 4, 5);
            add(3, 1, 6);
            add(4, 1, 3, 5, 6, 7);
            add(5, 7);
            add(7, 6);
        }
    
        public void add(Integer target, Integer... keys) {
        
            Vertex vertex = graph.get(target);
            List<Vertex> list = new ArrayList<>();
            for (Integer key : keys) {
        
                list.add(graph.get(key));
            }
            vertex.setVertexList(list);
        }
    
        public void printlnGraph() {
        
            if (graph != null) {
        
                Set<Entry<Integer, Vertex>> entrySet = graph.entrySet();
                for (Entry<Integer, Vertex> entry : entrySet) {
        
                    Vertex vertex = entry.getValue();
                    System.out.println(String.format("%s(%s):%s", vertex.getKey(), vertex.getShortestPathLen(), vertex.getVertexList()));
                }
            }
        }
    
        /**
         * 不使用walking状态
         * 深度优先遍历：源点的邻接表，邻接表由左向右一次计算各个路径的长度。先计算完第一个节点完成后再计算
         * 无权（其实就是权均为相等的有权场景）无负值圈
         * @param fromVertex :
         */
        public void updateLeastPathFromVertexByRecursive(Vertex fromVertex) {
        
            // 起始最短路径为0
            if (fromVertex.getShortestPathLen() == null) {
        
                fromVertex.setShortestPathLen(0);
            }
            // 遍历邻接顶点
            List<Vertex> vertices = fromVertex.getVertexList();
            if (CollectionUtils.isNotEmpty(vertices)) {
        
                for (Vertex toVertex : vertices) {
        
                    // 预增权重代价后面判断是否存在环路
                    int curShortestPathLen = fromVertex.getShortestPathLen() + toVertex.getWeight();
                    // 如果为空说明是第一次走到当前节点，直接更新最短路径，后面可能会再次经过当前节点，如果存在更小的则更新
                    // 发现更小的权重代价的路径长度则更新
                    if (toVertex.getShortestPathLen() == null || toVertex.getShortestPathLen() > curShortestPathLen) {
        
                        toVertex.setShortestPathLen(curShortestPathLen);
                        if (CollectionUtils.isNotEmpty(toVertex.getVertexList())) {
        
                            updateLeastPathFromVertexByRecursive(toVertex);
                        }
                    } else {
        
                        // 发现环路，不再递归，转了一圈回来发现子节点已经存在了路径长度，多转一圈的环路的路径一定是比没有环路的路径大
                        // 但是，如果存在权是负数，转了一圈后，路径值更小了，那么就会出现死循环。就需要其他方法解决。例如：记录每一次路径走过的所有节点，发现有重复则说明是环路
                        System.out.println("发现环路，不再递归");
                    }
                }
            }
        }
    
        /**
         * 使用walking状态
         * 深度优先遍历：源点的邻接表，邻接表由左向右一次计算各个路径的长度。先计算完第一个节点完成后再计算
         * 有权（其实就是权均为相等的有权场景）有负值圈
         * @param fromVertex :
         */
        public void updateLeastPathFromVertexByRecursiveWithWalking(Vertex fromVertex) {
        
            // 起始最短路径为0
            if (fromVertex.getShortestPathLen() == null) {
        
                fromVertex.setShortestPathLen(0);
            }
            // 遍历邻接顶点
            List<Vertex> vertices = fromVertex.getVertexList();
            if (CollectionUtils.isNotEmpty(vertices)) {
        
                for (Vertex toVertex : vertices) {
        
                    // 预增权重代价后面判断是否存在环路
                    int curShortestPathLen = fromVertex.getShortestPathLen() + toVertex.getWeight();
                    // 如果为空说明是第一次走到当前节点，直接更新最短路径，后面可能会再次经过当前节点，如果存在更小的则更新
                    // 发现更小的权重代价的路径长度则更新
                    if (toVertex.getShortestPathLen() == null || toVertex.getShortestPathLen() > curShortestPathLen) {
        
                        toVertex.setShortestPathLen(curShortestPathLen);
                        // 未发现环路，递归邻接顶点
                        if (CollectionUtils.isNotEmpty(toVertex.getVertexList()) && !toVertex.isWalking()) {
        
                            // 标识当前节点正处于递归中，不允许递归中的子节点再次通过当前节点（即环路）
                            toVertex.setWalking(true);
                            updateLeastPathFromVertexByRecursiveWithWalking(toVertex);
                            // 递归完成，恢复节点状态，允许其他递归路径通过当前节点
                            toVertex.setWalking(false);
                        } else {
        
                            // 递归路径中发现环路，不再递归
                            System.out.println("子顶点不存在邻接表或发现环路不再递归");
                        }
                    }
                }
            }
        }
    
        /**
         * 不使用walking状态
         * 广度优先遍历：先遍历邻接顶点数据，再继续遍历邻接顶点的邻接顶点。也就是先遍历邻接顶点距离最近的顶点再遍历距离远的顶点
         * 无权（其实就是权均为相等的有权场景）无负值圈
         * @param fromVertex :
         */
        public void updateLeastPathFromVertexByLoop(Vertex fromVertex) {
        
            // 起始最短路径为0
            if (fromVertex.getShortestPathLen() == null) {
        
                fromVertex.setShortestPathLen(0);
            }
            Queue<Vertex> queue = new ArrayBlockingQueue<>(16);
            queue.offer(fromVertex);
            while (!queue.isEmpty()) {
        
                Vertex vertex = queue.poll();
                if (vertex == null) continue;
                List<Vertex> vertices = vertex.getVertexList();
                if (vertices == null) continue;
                for (Vertex toVertex : vertices) {
        
                    int curShortestPathLen = vertex.getShortestPathLen() + toVertex.getWeight();
                    // 不需要判断最小值，广度优先，邻接顶点一定是距离当前顶点最近点，其他路径只会更远（无负值圈情况）
                    // 深度优先遍历，需要判断其他路径是否有更近情况，因为深度优先，先计算远节点再计算近节点
                    // || toVertex.getShortestPathLen() > curShortestPathLen
                    if (toVertex.getShortestPathLen() == null) {
        
                        // 子节点邻接顶点入栈，入栈的数据一定存在最短路径，保证子节点的最短路径的递增计算不会NPE
                        toVertex.setShortestPathLen(curShortestPathLen);
                        // 避免重复计算
                        if (queue.contains(toVertex)) continue;
                        queue.offer(toVertex);
                    }
                }
            }
        }
    
        /**
         * 使用walking状态
         * 广度优先遍历：先遍历邻接顶点数据，再继续遍历邻接顶点的邻接顶点。也就是先遍历邻接顶点距离最近的顶点再遍历距离远的顶点
         * 无权（其实就是权均为相等的有权场景）有负值圈
         * @param fromVertex :
         */
        public void updateLeastPathFromVertexByLoopWithWalking(Vertex fromVertex) {
        
            // 起始最短路径为0
            if (fromVertex.getShortestPathLen() == null) {
        
                fromVertex.setShortestPathLen(0);
                fromVertex.setWalking(true);
            }
            Queue<Vertex> queue = new ArrayBlockingQueue<>(16);
            queue.offer(fromVertex);
            while (!queue.isEmpty()) {
        
                Vertex vertex = queue.poll();
                if (vertex == null) continue;
    //            正处于计算中，负值圈仅走一圈就结束不再继续走，不然会死循环
                vertex.setWalking(true);
                List<Vertex> vertices = vertex.getVertexList();
                if (vertices == null) continue;
                for (Vertex toVertex : vertices) {
        
                    int curShortestPathLen = vertex.getShortestPathLen() + toVertex.getWeight();
                    // 需要判断最小值，广度优先，邻接顶点一定是距离当前顶点最近点，其他路径可能会更近（有负值圈情况）
                    // 需要判断其他路径是否有更近情况，这样会行程环路，队列永远不会为空一直有数据
                    if (toVertex.getShortestPathLen() == null || toVertex.getShortestPathLen() > curShortestPathLen) {
        
                        // 子节点邻接顶点入栈，入栈的数据一定存在最短路径，保证子节点的最短路径的递增计算不会NPE
                        toVertex.setShortestPathLen(curShortestPathLen);
                        // 避免重复计算
                        if (queue.contains(toVertex)) continue;
                        // 当前节点没有扫描过，
                        if (!toVertex.isWalking()) {
        
                            queue.offer(toVertex);
                        }
                    }
                }
            }
        }
    }

#### 测试案例 ####

1.  无权图，无负值圈场景，深度优先遍历
2.  有权图，有负值圈场景，深度优先遍历
3.  无权图，无负值圈场景，广度优先遍历
4.  有权图，有负值圈场景，广度优先遍历

package com.gallant.dispatch.graph;
    
    /**
     * @author 会灰翔的灰机
     * @date 2019/7/25
     */
    public class BreadthFirstSearch {
        
    
        public static void main(String[] args) {
        
            Graph graph = new Graph();
            // 初始化没有权重的图，有环路，无负值圈，权重均为1
    //        graph.initNoWeight();
            // 初始化没有权重的图，有环路，有负值圈，有一个权重均为-3的顶点
            graph.initWeight();
            // 打印图，没有最短路径，默认值为0或者null
            graph.printlnGraph();
            System.out.println("---------");
            // 遍历起始点
            Vertex start = graph.getGraph().get(3);
            boolean useWalking = args.length==0;
    //        深度优先遍历
    //        if (useWalking) {
        
    //            // 使用walking状态遍历，可以解决负值圈
    //            graph.updateLeastPathFromVertexByRecursiveWithWalking(start);
    //        } else {
        
    //            // 不使用walking状态遍历，未解决负值圈
    //            graph.updateLeastPathFromVertexByRecursive(start);
    //        }
    //        广度优先遍历
            if (useWalking) {
        
                graph.updateLeastPathFromVertexByLoopWithWalking(start);
            } else {
        
                graph.updateLeastPathFromVertexByLoop(start);
            }
            // 打印图，已经计算完成，起始点至每个顶点的最短路径代价
            graph.printlnGraph();
        }
    }

[https_blog.csdn.net_u010597819_article_details_86646297]: https://blog.csdn.net/u010597819/article/details/86646297
[aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAxOS9qcGVnLzIyODAyMy8xNTY0MTk0MzUwOTIzLTg3NDdlOGQxLWM3ZjItNDA1Ny1iOGMxLWJkNDIzZDJhNjg1YS5qcGVn_align_left_display_inline_height_405_originHeight_405_originWidth_405_size_0_status_done_width_405]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/67e452dc7203493d8ea9e4681311e61e.png
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/4c8a38afca8146ff9a0d6e68a655870d.png