做拓扑排序时数组越界异常

Question

此代码取号。图中的节点数并创建具有节点数的图，然后用户必须输入两个顶点之间的单向边。（形成的图是有向无环图或 DAG）。然后通过拓扑排序函数 topoSort 对图进行排序问题出在 topoSortRE 方法中，该方法是在 topoSort 中调用的递归方法，它检查是否访问了顶点，但在我的运行中具有以下输入：

5（节点数）7（边数）

边的连接： 1-2, 1-3, 1-4, 1-5, 2-4, 2-5, 3-4,

布尔数组visited越界

public class n {
    public static void main(String[] args) throws Bounds{
        Scanner sc= new Scanner (System.in);
        System.out.println("Enter no. of Islands");
        int n= sc.nextInt();
        Graph g = new Graph (n);
        System.out.println("Enter no. of one-way bridges");
        int m= sc.nextInt();
        try { 
            for (int i=0; i<m;i++){ 
                System.out.println("This one-way bridge connects between");
                int u = sc.nextInt();
                int v = sc.nextInt();
                if(u == v){ throw new Bounds("");}
                else{ g.addEdge(u, v);}
            }
        } catch(IndexOutOfBoundsException e){
            System.out.println("Please enter a valid input!");
        } catch(Bounds e){
            System.out.println("Please enter a valid input!");
        }
        g.topoSort();  
    }

    public static class Bounds extends Exception {
        public Bounds (String message){
            super(message);
        }
    }   

    public static class Graph  {  
        private int V;    
        private ArrayList<ArrayList<Integer>> adj;  

        Graph(int v) {  
            V = v;  
            adj = new ArrayList<ArrayList<Integer>>(v);  
            for (int i=0; i<v; ++i)  
                adj.add(new ArrayList<Integer>());  
        }  

        void addEdge(int v,int w) { adj.get(v).add(w); }  

        void topoSortRE( int v, boolean visited[], Stack<Integer> stack) {  
            visited[v] = true;  
            Integer i;  

            Iterator<Integer> it = adj.get(v).iterator();  
            while (it.hasNext()) {  
                i = it.next();  
                if (false == visited[i])  
                    topoSortRE(i, visited, stack);  
            }  
            stack.push(new Integer(v));  
        }

        void topoSort() {  
            Stack<Integer> stack = new Stack<>();  

            boolean visited[] = new boolean[V];  
            for (int i = 0; i < V; i++)  
                visited[i] = false;  

            for (int i = 0; i < V; i++)  
                if (visited[i] == false)  
                    topoSortRE(i, visited, stack);  

            while (stack.isEmpty()==false)  
                System.out.print(stack.pop() + " ");  
        } 
    }
}

Answer 1

您似乎在尝试使用岛屿编号作为数组索引。 Setting a bridge between islands 1-5 表示在索引为 0-4 的岛屿之间设置桥梁。

void topoSortRE( int v, boolean visited[], Stack<Integer> stack) {
    visited[v] = true;
    Integer i;

    Iterator<Integer> it = adj.get(v).iterator();
    while (it.hasNext()) {
        i = it.next() - 1; // -1 to make bridge number to be bridge index in array
        if (false == visited[i])
            topoSortRE(i, visited, stack);
    }
    stack.push(new Integer(v));
}

您肯定需要熟悉调试工具。它将帮助您并提高您的开发技能和代码质量，并减少您花在修复代码上的时间。

做拓扑排序时数组越界异常

Array out of bound exception while doing topological sort

java

sorting

algorithm

graph

topological-sort

5（节点数）7（边数）