对图(地图，二维数组)的深度优先和广度优先算法

古城微笑少年丶 2023-05-31 02:25 3阅读 0赞

地图是否存在一个路径使的可以从起始点（图的左上角）走出去（到达另一个点，一般为图的右下角）

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    
    //图
    public class Graph { 
        private ArrayList<String> vertextList;//存储顶点集合
        private int[][] edges; //存储图对应的邻结矩阵
        private int numOfEdges;//表示边的数目
        private boolean[] isVisited;
    
    
        public static void main(String[] args) { 
    
            int n = 5;//结点个数
            String vertexs[] = { "A", "B", "C", "D", "E"};
            Graph graph = new Graph(n);
            //添加结点
            for (int i = 0; i < vertexs.length; i++) { 
                graph.insertVertex(vertexs[i]);
            }
            //添加边
            //A-B A-C B-C B-D B-E
            graph.insertEdge(0, 1, 1);
            graph.insertEdge(0, 2, 1);
            graph.insertEdge(1, 2, 1);
            graph.insertEdge(1, 3, 1);
            graph.insertEdge(1, 4, 1);
    
            graph.showGraph();
            System.out.println("\n深度遍历");
            graph.dfs();
    
    
            System.out.println("\n广度遍历");
            graph.bfs();
    
    
        }
    
        public Graph(int n) { 
            this.edges = new int[n][n];
            this.vertextList = new ArrayList<String>(n);
            this.numOfEdges = 0;
    
        }
    
        //遍历所有结点，进行广度优先遍历
        private void bfs() { 
            isVisited = new boolean[5];
            for (int i = 0; i < getNumOfVertex(); i++) { 
                if (!isVisited[i]) { 
                    bfs(isVisited, i);
                }
            }
    
        }
    
        //对一个结点进行广度优先遍历
        private void bfs(boolean[] isVisited, int i) { 
            int u;//表示队列的头结点
            int w;//邻接结点
            //队列
            LinkedList<Integer> queue = new LinkedList<>();
            System.out.print(getValueByIndex(i) + "->");
            isVisited[i] = true;
            //将结点加入队列
            queue.add(i);
            while (!queue.isEmpty()) { 
                //拿到队列头结点
                u = queue.removeFirst();
                //得到邻接结点
                w = getFirstNeighbor(u);
                while (w != -1) { 
                    if (!isVisited[w]) { 
                        System.out.print(getValueByIndex(w) + "->");
                        isVisited[w] = true;
                        //入队
                        queue.addLast(w);
                    }
                    //w已经访问过了,找下一个邻接结点
                    w = getNextNeighbor(u, w);
                }
            }
    
        }
    
    
        //重载dfs,遍历所有结点
        public void dfs() { 
            isVisited = new boolean[5];
            for (int i = 0; i < getNumOfVertex(); i++) { 
                if (!isVisited[i]) { 
                    dfs(isVisited, i);
                }
            }
        }
    
    
        //深度优先遍历算法
        private void dfs(boolean[] isVisited, int i) { 
            //访问
            System.out.print(getValueByIndex(i) + "->");
            //将结点设置为已经访问
            isVisited[i] = true;
            //找到i的领接结点
            int w = getFirstNeighbor(i);
            while (w != -1) { 
                if (!isVisited[w]) { 
                    dfs(isVisited, w);
                }
                //如果w已经被访问过
                w = getNextNeighbor(i, w);
            }
    
        }
    
    
        /** * 得到第一个邻接结点的下标 * * @param index 给定节点 * @return 返回相邻结点下标 */
        public int getFirstNeighbor(int index) { 
            for (int i = 0; i < vertextList.size(); i++) { 
                if (edges[index][i] > 0) { 
                    return i;
                }
            }
            return -1;
        }
    
        //根据前一个邻接结点的下标来获取下一个邻接结点
        public int getNextNeighbor(int v1, int v2) { 
            for (int i = v2 + 1; i < vertextList.size(); i++) { 
                if (edges[v1][i] > 0) { 
                    return i;
                }
            }
            return -1;
        }
    
    
        //插入结点
        public void insertVertex(String vertex) { 
            vertextList.add(vertex);
        }
    
    
        /** * 插入边 * * @param v1 表示第一个点的下标 * @param v2 表示第二个点的下标 * @param weight 权值 */
        public void insertEdge(int v1, int v2, int weight) { 
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        public int getNumOfVertex() { 
            return vertextList.size();
        }
    
        public int getNumOfEdges() { 
            return numOfEdges;
        }
    
        //返回结点的值
        public String getValueByIndex(int i) { 
            return vertextList.get(i);
        }
    
        //返回权值
        public int getWeight(int v1, int v2) { 
            return edges[v1][v2];
        }
    
        //显示图矩阵
        public void showGraph() { 
            for (int[] edge : edges) { 
                System.out.println(Arrays.toString(edge));
            }
        }
    
    
    }