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

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

1 迷宫问题

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

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

最后我们要做的就是找出顶点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;}
}

运行结果