algorithm - 我将如何着手编写伪代码以在邻接矩阵中查找汇？

Question

伪代码会是什么样子？我知道水槽是什么，我想我可以告诉你识别水槽的过程。但是我如何表示矩阵及其行和列呢？谢谢。

Answer 1

在 Java 中，您可以像这样声明一个 bool 值的二维矩阵:

final int ROWS = 8;
final int COLS = 8;
boolean matrix[][] = new boolean[ROWS][COLS];

然后用一些数据填充矩阵:

for (int i=0; i < ROWS; i++)
   for (int j=0; j < COLS; j++)
      matrix[i][j] = true; //(false if no edge from element i to element j)

然后您可以使用与填充矩阵相同的嵌套 for 循环结构遍历矩阵:

for (int i=0; i < ROWS; i++)
   for (int j=0; j < COLS; j++)
      //matrix[i][j] is row i, column j

遍历 n 行和 m 列的任何矩阵的运行时间为 O(nm)

对于你来说，因为你正在构建一个邻接矩阵，ROWS 和 COLS 将是相同的值，所以你可以只使用 ROWS 两次。外层循环遍历每一行，而内层循环遍历每一列，因此它将检查从节点 0 到节点 0、节点 1、节点 2、节点 3 等的边。

然后它将检查从节点 1 到节点 0、节点 1、节点 2 等的边(请注意我们如何以这种方式检查自身的边)

因为 ROWS 和 COLS 是相同的值，所以你的运行时间实际上是 O(n²)

您可以使用更保守的图形表示方法做得更好。

编辑:

寻找接收器的伪代码可能类似于以下内容:

• 创建一个列表，将索引与 bool 值和计数相关联。索引是矩阵的元素， bool 值是一个标志，用于指示节点是否是汇点，计数是传入边的数量。
• 遍历邻接表，假设 matrix[i][j] == true 表示存在从 i 到 j 的有向边
• 如果 matrix[i][j] == true，则元素 i 不是汇，因为它有出边，因此将其 bool 值设置为 false
• 如果 matrix[i][j] == true，则增加元素 j 的传入边数
• 在我们对矩阵进行一次迭代之后，我们列表中的某些元素可能仍然认为它可能是一个接收器(即它没有传出边)，因此我们再次迭代该列表以查看这些元素是否具有 bool 值仍然设置为 true 的边数等于元素的数量(即来自所有其他节点的传入边)

我已经向您展示了如何创建和迭代邻接列表，现在您认为您可以查找如何满足第一个项目符号项的要求吗？