C - 使用递归在邻接矩阵中进行深度优先搜索

Question

我有一个递归问题，我想用递归解决。

例如，给定此邻接矩阵AdjMat：

  0 1 2 3 
0 0 1 0 0
1 1 0 1 0
2 0 1 0 1
3 0 0 1 0

假设我想查看第0列及其所有邻居及其邻居的邻居（距离为2），并将所有行索引> 0存储到一个链接的整数列表中。

这是我更新的代码：

intNode *Neighbors(intNode *head, int colOfInterest, int distance) {
    int x = colOfInterest; 

    if (distance == 0) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
               if (AdjMat[x][j] > 0) { 
                   head = insertInt(head, j);
               }
            }
            break;
        }
    }
    intNode *subpath = NULL;
    for (int i = 0; i < distance; i++) {
        subpath = Neighbors(head, colOfInterest, distance);
    }
    // Once the final neighbor column has been reached, add elements to the linked list.
    return head;
} 

它目前不返回预期的输出（在链表中为0,1和2），但我不确定原因。任何帮助或方向表示赞赏。

Answer 1

您的代码中有两个主要的误解。第一个是关于递归，第二个是关于邻接矩阵如何工作。

递归基本上是这样的：

• 拿一个节点和一个最大值距离：func(node, d);
• 如果距离为负，则返回
• 将节点添加到列表中;
• 对于所有相邻节点，调用该节点上的函数并使用新的，现在更短的距离：func(next, d - dist(node, next)。

要查找节点＃0附近的所有节点，您将从一个空列表开始，然后调用func(0, 2)，这将导致以下调用：

func(0, 2)                  // list {0}
    func(1, 1)              // list {0, 1}
        func(0, 0)          // list {0, 1, 0}          error, see below
            func(1, -1)     // negative d, do nothing
        func(2, 0)          // list {0, 1, 0, 2}
             func(1, -1)    // negative d, do nothing
             func(3, -1)    // negative d, do nothing

--> recursion depth

这种递归最终会停止，因为你减少了每一步的距离。这很重要：每次递归都必须有终止条件，否则它会无休止地递归。 （无论是在前面测试距离还是在递归时测试距离都是一种风格问题。向上字体会提前捕获无效输入，但可能会导致无用的“死”递归。）

给定的递归有一个微妙的问题：当你调用func(0, 2)时，函数将两次添加节点＃0，因为从节点0到1然后再返回到0会产生距离2，这是触手可及的。有几种方法可以解决这个问题。例如，您可以查看给定节点是否已在列表中。或者您可以将节点标记为已访问。

邻接矩阵确定是否连接了两个节点。如果a，两个节点b和adj[a][b] != 0连接。这意味着如果你想找到给定节点next的所有邻居node，你应该这样做：

for (int next = 0; next < N; next++) {
    if (adj[node][next]) {
        // do something with next
    }
}

您不需要两个嵌套循环。矩阵有两个维度，但第一个维度始终是固定的：它是源节点。 （如果你查看你的代码，你会发现你没有对i做任何事情。）

在您的情况下，邻接矩阵似乎只有0和1的值，但它可以有其他非零值来指示加权图的距离。