【数据结构与算法之图结构】案例

超、凢脫俗 2024-03-25 16:38 124阅读 0赞

#### 【数据结构与算法之图结构】案例 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之图结构】案例
         *   *   *  1 迷宫问题

###### 1 迷宫问题 ######

如图所示为一个环形迷宫，S 为迷宫入口，E为迷宫出口，给出该迷宫的走法。

![在这里插入图片描述][538a5b2e0181430e9c6fbeee6738fa11.png_pic_center]

我们可以将迷宫的起点、分岔路口、阻挡道路的墙壁都抽象为图中顶点、迷宫路径抽象为图中的边，那么一个迷宫就相当于一个无向图。

最后我们要做的就是找出顶点S 到顶点E的通路。

注意是通路而不是路径，通路允许包含重复的顶点。

Java代码算法实现：

import java.util.ArrayList;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: Maze
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 19:28
     */
    
    public class Maze {
        
    
        private VNode[] vNodes;
        int[] visited;
        ArrayList<Character> res;
    
        public void createMaze(char v[], int arc[]) {
        
            vNodes = new VNode[v.length];
            res = new ArrayList<Character>();
    
            for (int i = 0; i < v.length; i++) {
        
                vNodes[i] = new VNode();
                vNodes[i].data = v[i];
                vNodes[i].firstArc = null;
            }
    
            int index = 0;
            ArcNode p, q = null;
            for (int i = 0; i < v.length; i++) {
        
                for (; index < arc.length && arc[index] != -1; index++) {
        
                    p = new ArcNode(arc[index]);
                    if (vNodes[i].firstArc == null) {
        
                        vNodes[i].firstArc = p;
                    } else {
        
                        q.next = p;
                    }
                    q = p;
                }
    
                index++;
            }
        }
    
        // 寻找一条行走迷宫的路径
        public void findPath() {
        
            visited = new int[vNodes.length];
            for (int i = 0; i < vNodes.length; i++) {
        
                visited[i] = 0;
            }
            res = new ArrayList<Character>(); // 保存结果序列
            for (int i = 0; i < vNodes.length; i++) {
        
                if (vNodes[i].data == 'S') {
        
                    DFS(i);  // 从入口S进入迷宫深搜
                }
            }
    
            System.out.println(res);
        }
    
        private boolean DFS(int vIndex) {
        
            if (visit(vIndex)) {
        
                return true;
            }
            visited[vIndex] = 1;
            int w = getFirstAdj(vIndex);
            while (w != -1) {
        
                if (visited[w] == 0) {
        
                    if (DFS(w)) {
        
                        return true;
                    }
    
                    res.add(vNodes[vIndex].data);
                }
                w = getNextAdj(vIndex, w);
            }
    
            return false;
    
        }
    
        private boolean visit(int vIndex) {
        
            res.add(vNodes[vIndex].data);
            if (vNodes[vIndex].data == 'E') {
        
                return true;
            }
            return false;
        }
    
        private int getFirstAdj(int vIndex) {
        
            if (vNodes[vIndex].firstArc != null) {
        
                return vNodes[vIndex].firstArc.adjvex;
            }
            return -1;
        }
    
        private int getNextAdj(int vIndex, int w) {
        
            ArcNode p;
            p = vNodes[vIndex].firstArc;
            while (p != null) {
        
                if (p.adjvex == w && p.next != null) {
        
                    return p.next.adjvex;
                }
                p = p.next;
            }
            return -1;
        }
    
        public static void main(String[] args) {
        
    
            char[] v = {
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'S'};
            int[] arc = {
        1, 3, 7, -1, 0, -1, 4, -1, 0, 4, 5, -1, 2, 3, -1, 3, -1, 7, -1, 0, 6, -1};
            Maze maze = new Maze();
    
            maze.createMaze(v, arc);
            maze.findPath();
    
        }
    
    }
    
    // 顶点类型
    class VNode {
        
    
        char data; // 数据信息
        ArcNode firstArc; // 指向单链表, 即指向该顶点的第1条边
    
    }
    
    // 边节点类型
    class ArcNode {
        
        int adjvex; // 该边指向的顶点在数组中的位置(数组下标)
        ArcNode next; // 指向下一条边的指针
    
        ArcNode(int adjvex) {
        
            this.adjvex = adjvex;
        }
    }

运行结果

![在这里插入图片描述][a91a67bdb8e3435eb1bf296a77b206b7.png_pic_center]

[538a5b2e0181430e9c6fbeee6738fa11.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/87c5013561334b49bcb5af227df572e6.png
[a91a67bdb8e3435eb1bf296a77b206b7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7d050beca4054a02a649973abec3b883.png