我怎样才能使这个算法不那么冗余？

Question

我对 C 还很陌生，不知道如何减少函数 number_within_k_degrees() 的冗余度。它一次又一次地访问图中的相同节点，即使它们可能已经被访问过。我想将所有值的初始设置删除为 false 以稍微减少它，但我认为这没有太大作用。关于如何减少或消除冗余工作的任何提示都将非常有帮助。谢谢

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    // mark current root person as reachable
    reachable[person_get_index(current)] = true;
    // now deal with this person's acquaintances
    if (steps_remaining > 0){
        int num_known = person_get_num_known(current);
        for (int i = 0; i < num_known; i++){
            struct person *acquaintance = person_get_acquaintance(current, i);
            find_reachable_recursive(acquaintance, steps_remaining - 1, reachable);
        }
    }
}

// computes the number of people within k degrees of the start person
int number_within_k_degrees(struct person *start, int total_people, int k){
    bool *reachable;
    int count;

    // maintain a boolean flag for each person indicating if they are visited
    reachable = malloc(sizeof(bool) * total_people);
    for (int i = 0; i < total_people; i++){
        reachable[i] = false;
    }

    // now search for all people who are reachable with k steps
    find_reachable_recursive(start, k, reachable);

    // all visited people are marked reachable, so count them
    count = 0;
    for (int i = 0; i < total_people; i++){
        if (reachable[i] == true){
            count++;
        }
    }
    return count;
}

Answer 1

I thought to remove the initial setting of all values to false to reduce it somewhat

这显然是一个非常糟糕的主意：它需要初始化（到 false）以确保正确性。

真正的问题是你永远不会测试一个节点是否已经被访问过。由于已经访问过的笔记不需要再次处理，您可以立即中止：

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    const int pindex = person_get_index(current);
    if (reachable[pindex]) return;
    // mark current root person as reachable
    reachable[pindex] = true;
    … rest of the code

一些进一步的改进建议：

不要在函数的开头声明变量，在初始化它们的地方声明它们。这通过将变量的声明和用法放在一起提高了可读性。
与其在循环中调用 malloc 然后将值设置为 false，不如使用 calloc.
不要在测试中使用布尔文字。 if (reachable[i] == true)这样的代码是多余的，应该写成if (reachable[i])。

我怎样才能使这个算法不那么冗余？

How would I make this algorithm less redundant?

c

redundancy