0

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

1 0 
0 2 
2 1 
0 3 
3 4

具有给定输入的以下方法的输出如下所示：

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 的最佳和最干净的方法吗？还是我缺少更好的解决方案？

4

1 回答 1

1

是的，这是多余的，但这是检查边缘的唯一方法。使用拓扑排序将降低时间复杂度，如果您确实使用拓扑排序，则无需担心重复。

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

于 2020-09-30T03:35:54.423 回答