英文:
Constructing Kernel DAG from Kosaraju's Algorithm
问题
我目前正在学习《Algorithm Design》这本由Kleinberg和Tardos撰写的书中展示的不同算法。我已经完成了Kosaraju-Sharir算法的实现，现在我正试图基于强连通分量构建一个Kernel DAG。我不确定如何实现能够执行此操作的代码。目前，我有一个名为"display"的方法，它将打印出强连通分量，并且我希能够使其也能够打印Kernel DAG。在这段代码中，"adjacent" 是我的邻接表，已经在反向邻接表上执行了DFS。变量"kern"只是初始邻接表的一个副本，其格式如下所示。我希望输出的Kernel DAG看起来类似，例如将强连通分量1打印在与其有边相连的强连通分量旁边（例如SCC2 SCC4）。
1 0
0 2
2 1
0 3
3 4
以下是使用给定输入的方法的输出：
给定的图有3个强连通分量。
连通分量＃0： [4]
连通分量＃1： [3]
连通分量＃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);
}
我已经尝试为这个问题编写了伪代码。我知道由于我已经有了强连通分量，我可以创建一个循环，遍历每个个体强连通分量中的顶点，并在原始邻接表中查找连接到另一个SCC的边。此外，我认为最好实践是实现一个哈希映射来存储Kernel DAG，然后在打印之前检查该哈希映射是否存在重复。这是否是创建Kernel DAG的最佳清晰方法？还是我忽略了更好的解决方案？
英文:
I am currently learning about different algorithms demonstrated in the book Algorithm Design by Kleinberg and Tardos. I have completed an implementation of the Kosaraju-Sharir algorithm and I am now attempting to construct a Kernel DAG based on the strongly connected components. I am unsure how to implement code that will perform this. Currently, I have a method titled display that will print the strongly connected components and I want it to be able to print the Kernel DAG as well. Within this code, adjacent is my adjacency list with DFS already performed on the reverse adjacency list. The variable "kern" is just a copy of the initial adjacency list which was input in a format shown below. I would like the output Kernel DAG to look similar, with strongly connected component 1 printed next to the strongly connected component it has an edge with (SCC2 SCC4 for example).
1 0
0 2
2 1
0 3
3 4
The output of the following method with the given input shown below:
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);
}
I have attempted to write pseudocode for this issue. I know that since I have my strongly connected components, I can create a for loop that will iterate through each vertex in the individual strongly connected components and look in the original adjacency list for an edge connecting it to another SCC. Also, I believe it may be best practice to implement a hashmap to store the Kernel DAG then checking that hashmap for duplicates before printing. Would that be the best and cleanest method of creating a Kernel DAG? Or is there a better solution that I am missing?
答案1
得分: 1
是的，这是多余的，但那将是检查边缘的唯一方法。
使用拓扑排序将减少时间复杂度，如果确实使用拓扑排序，则无需担心重复。
关于方程式以及图内核提示，您可以参考以下链接。
https://cs.uwaterloo.ca/~y328yu/mycourses/480-2018/assignments/a3/hw3.pdf
英文:
Yes, it is redundant but that would be the only way to check for an edge.
Using a topological sort will reduce the time complexity,if you do use a topological sort you need not worry about duplicates.
You can refer to the below for equations as well as hints on Graph Kernels .
https://cs.uwaterloo.ca/~y328yu/mycourses/480-2018/assignments/a3/hw3.pdf
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论