从 Kosaraju 的算法构造内核 DAG

Question

我目前正在学习 Kleinberg 和 Tardos 合着的《算法设计》一书中演示的不同算法。我已经完成了 Kosaraju-Sharir 算法的实现，现在我正尝试构建一个基于强连通组件的内核 DAG。我不确定如何实现执行此操作的代码。目前，我有一个名为 display 的方法，它将打印强连接组件，我希望它也能够打印 Kernel DAG。在此代码中，adjacent 是我的邻接列表，其中 DFS 已在反向邻接列表上执行。变量“kern”只是初始邻接表的一个副本，它以如下所示的格式输入。我希望输出的 Kernel DAG 看起来相似，强连接组件 1 打印在它具有边缘的强连接组件旁边（例如 SCC2 SCC4）。

使用给定输入的以下方法的输出如下所示：

The given graph has 3 Strongly Connected Components.
Connected Component #0: [4]
Connected Component #1: [3]
Connected Component #2: [0, 2, 1]

public static void display (ArrayList<ArrayList<Integer>> adjacent, ArrayList<ArrayList<Integer>>kern)
    {
        Iterator<ArrayList<Integer>> temp = adjacent.iterator();
        int size = adjacent.size();

        System.out.println("\nThe given graph has " + size + " Strongly Connected Components.");
        for(int i = 0; temp.hasNext(); i++)
        {

            ArrayList<Integer> x = temp.next();
            System.out.println("Connected Component #"+i + ":\t" + x);
        }
        System.out.println(kern);
    }

我试图为这个问题编写伪代码。我知道，因为我有我的强连接组件，我可以创建一个 for 循环，它将遍历各个强连接组件中的每个顶点，并在原始邻接列表中查找将它连接到另一个 SCC 的边。此外，我认为最好的做法是实现一个哈希图来存储内核 DAG，然后在打印之前检查该哈希图是否有重复项。那会是创建内核 DAG 的最好和最干净的方法吗？还是我缺少更好的解决方案？

Answer 1

是的，这是多余的，但这是检查边缘的唯一方法。使用拓扑排序会降低时间复杂度，使用拓扑排序就不用担心重复了

您可以参考下面的方程式以及有关图核的提示。 https://cs.uwaterloo.ca/~y328yu/mycourses/480-2018/assignments/a3/hw3.pdf

从 Kosaraju 的算法构造内核 DAG

Constructing Kernel DAG from Kosaraju's Algorithm

java

algorithm

graph

data-structures

kosaraju-algorithm