这个 if 语句是如何工作的？它似乎没有布尔表达式

Question

这是一段代码。我不确定倒数第二行的 if 语句是如何工作的？它没有像 'if A[n − 1, j] == x' 之类的布尔表达式。有人可以解释一下它对我的实际作用吗？谢谢

Connected(A[0..n − 1, 0..n − 1])

  //Input: Adjacency matrix A[0..n − 1, 0..n − 1]) of an undirected graph G

  //Output: 1 (true) if G is connected and 0 (false) if it is not

if n = 1 return 1 //one-vertex graph is connected by definition

else

 if not Connected(A[0..n − 2, 0..n − 2]) return 0

 else for j ←0 to n − 2 do
          if A[n − 1, j] return 1
      return 0

Answer 1

if A[n−1, j] == 1 等同于 if A[n-1,j]

邻接矩阵通常有 ones 和 zeros，yes 和 no 或 true 和 false - 只有 2 个可能的值 - 基本上每个元素都有（某种）布尔值，指示 2 个顶点是否连接。此外，这是伪代码，它没有 'work' 的那么多功能，但更多的是用人类可读（和简单）的术语来传达算法。

Answer 2

它调用了一个 return 布尔值（0 或 1）的函数，这就是它的工作原理。

然后，当您的代码执行 A[n − 1, j] 时，它会调用 A 函数，这是您在那里定义的函数，它会（最终）return 您的布尔值

这是一个递归函数。你会看到很多，并最终理解它。其实很简单，它是一个多次调用自身的函数，每次调用都有不同的参数，直到其中一个调用真正return的结果通过所有函数链一路传回

Answer 3

视情况而定，因为伪代码没有严格定义，所以有多种可能的含义。

if A[n-1,j] 可以等同于（假设为数字类型）if A[n-1,j] == 1 或 if A[n-1,j] != 0 或（假设为布尔类型）if A[n-1,j] == true。对于邻接矩阵（由二进制 true/false 或 0/1 数据组成）这些可能性可能是等价的。

Answer 4

您的算法将邻接矩阵缩减为单个节点 (n = 1) 的子图。在这个基本情况之后，它通过使用循环检查 "holes" 来确定您是否有连通图。

在此循环中，您将检查是否有 "orphan node"（邻接矩阵中整行均为零）。从单个节点向上构建，您可以前向链接以查看图形是否已连接。 请注意，在无向图中，当您检查基本情况时，如果该图未完全连接，您将发现一个断开连接的节点。即使它可能附加到另一个节点--它将附加到您尚未包含在搜索中的节点。

 else
   for j← 0 to n− 2 do //we hit the base case, now forward-chain from single node
     if A[n− 1, j]//traverse the whole row (i.e. "is this node connected to anything else?")
     return 1 //there's a connection, we can return
     return 0 // if ALL zeros in adjacency matrix, you have an orphaned node

希望对您有所帮助！ :)

澄清一下——if 语句有点模棱两可。对我来说，只有当您检查整个行（j 索引）中的所有零时，该算法才算完整。这是你return false 的情况。如果与前一个节点只有一个连接，则可以归纳 ("forward-chain") 并继续搜索。

干杯，
-加布

P.S。这在检查完全空行的嵌套 for 循环中更容易阅读。

这个 if 语句是如何工作的？它似乎没有布尔表达式

How does this if statement work? It appears to have no boolean expression

arrays

if-statement

pseudocode