java - 输入和输出有助于拓扑排序

Question

public class Problem3 {

    public static void main (String [] args){

        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();
        System.out.println("Enter no. of island you want to be intially on");
        int r= 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 || u>n || v>n){ throw new Bounds("");}
            else{ g.addEgde(u-1, v-1);}

        }
                g.topoSort();}
        catch(IndexOutOfBoundsException e){
            System.out.println("Please enter a valid input!");
        }
       catch(Bounds e){
       System.out.println("Please enter a valid input!");
       }


    }
    public static class Bounds extends Exception{

    public Bounds (String message){
        super(message);
    }}



    static class Graph {
        int V;
        LinkedList<Integer>[] adjList;

        Graph(int V) {
            this.V = V;
            adjList = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adjList[i] = new LinkedList<>();
            }
        }

        public void addEgde(int u, int v) {
            adjList[u].addFirst(v);
        }

        public void topoSort() {
            boolean[] visited = new boolean[V];
            stack stack = new stack();
            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    topoSortRE(i, visited, stack);
                }
            }
            System.out.println("Topological Sort: ");
            int size = stack.size();
            for (int i = 0; i <size ; i++) {
                System.out.print(stack.pop()+ 1 + " ");
            }
        }

        public void topoSortRE(int s, boolean[] visited, stack stack) {
            visited[s] = true;
            for (int i = 0; i < adjList[s].size(); i++) {
                int vertex = adjList[s].get(i);
                if (!visited[vertex])
                    topoSortRE(vertex, visited, stack);
            }
            stack.push(s);
        }}}

以下代码尝试解决以下问题:有很多岛屿是通过单向桥连接的，也就是说，如果有一座桥连接岛屿a和b，那么你只能通过桥梁从a到b，但不能旅行后退通过使用相同的。如果你在 a 岛，那么你选择(均匀且随机)以下之一通过单向桥可直接到达的岛屿并移动到该岛屿岛。如果您无法进一步移动，您就会被困在一座岛上。可以保证如果从一个岛到第二个岛有一条有向的路径 没有从另一个岛引出的路径第二个回到第一个。换句话说，形成的图是有向无环图。找到你最有可能被困的岛屿；那就是你可以的岛屿可能以来自所有其他岛屿的最大路径数到达。

输入格式:第一行:三个整数n(岛屿数量)、m(单向桥梁数量)和r(您最初所在岛屿的索引)接下来的 m 行:两个整数 ui 和 vi 表示从岛 ui 到 vi 的单向桥。输出格式:打印出您最有可能被困的岛屿的索引。如果有多个岛，然后按索引的递增顺序打印它们(单个值中用空格分隔的值)线)。输入示例

5, 7, 1
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 4)
(2, 5)
(3, 4)

示例输出

4

我编写了代码来对图进行拓扑排序，但我遇到了如何使输入成为初始岛以及如何使输出成为最有可能被卡住的岛的问题。我知道我最有可能被困的岛屿是入度最多且没有出度的岛屿，但不知道如何实现。

Answer 1

为每个节点设置一个值(实数)，表示您从起始岛屿到达该节点的概率。首先，将初始节点的该值设置为1，其他节点的该值设置为0。

在拓扑排序过程中，当你在节点 v 时，将它的概率值除以邻居数量加上每个邻居的值(换句话说，因为你知道到达 v 的概率是 v.value，那么到达其邻居的概率应增加选择该邻居的 v.value * ppb，即 1/#_of_neighbors)。这样，在拓扑排序过程中，每当你处于某个节点时，它的值就等于到达该节点的总概率。

您的答案是具有最大值的结束岛(出度为 0 的节点)。

你的拓扑排序似乎是错误的，你正在做一些看起来像DFS的事情。在拓扑排序中，您希望在访问完具有以该边结尾的所有顶点之后访问每个顶点。

关于实现，我将你的DFS更改为拓扑排序，并添加了我谈到的那些概率。我把选择最佳结局顶点的部分留给了你，我不认为为某人做所有的工作是有教育意义的。另外，我不保证我下面的更改不包含任何拼写错误等。我已尽力，但我还没有运行此代码。

static class Graph {
    int V;
    LinkedList<Integer>[] adjList;

    Graph(int V) {
        this.V = V;
        adjList = new LinkedList[V];
        probability = new double[V];
        for (int i = 0; i < V; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEgde(int u, int v) {
        adjList[u].addFirst(v);
    }

    public void topoSort(int start) {
        double[] probability;
        probability[start] = 1;
        int[] indegree = new int[V];
        stack stack = new stack();

        for (int i = 0; i < V; i++) {
            probability[i] = 0;
            for (int j = 0; j < adjList[i].size(); ++j) {
                 indegree[adjList[i][j]] += 1;
            }
        }

        probability[start] = 1;

        for(int i = 0; i < V; ++i)
        {
            if(indegree[i] == 0)
              stack.push(i);
        }

        while(stack.size())
        {
           int v = stack.pop();
           for (int i = 0; i < adjList[v].size(); ++i)
           {
                indegree[adjList[v][i]] -= 1;
                probability[adjList[v][i]] += probability[v] / (double)(adjList[v].size());
                if(indegree[adjList[v][i]] == 0)
                  stack.push(adjList[v][i]);
           }
        }

         //probability array now contains all probabilities to visit each node

        }
    }
}