CS50 Tideman问题：递归循环检测函数失效的调试求助

我需要实现一个函数判断添加新边是否会形成循环，但递归函数始终无法检测到循环，导致所有边都被添加。以添加从B（索引1）到C（索引2）的紫色边为例，我的思路是递归遍历C指向的所有节点，若当前节点等于原边起点（1）则返回非零值，但实际没生效。

调用递归的lock_pairs代码 #

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Initialize variables
    int cycle_start;
    int current;
    int cycle;

    // Loop through pairs to determine acceptable locks
    for (int i = 0; i < pair_count; i++)
    {
        // Set new cycle start and current node
        cycle_start = pairs[i].winner;
        current = pairs[i].loser;

        // Reset Boolean
        cycle = 0;

        // If a cycle would be created, skip edge
        if (cycle_created(current, cycle_start, cycle) > 0)
        {
            continue;
        }

        else
        {
            // Add edge by locking pairs
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }

    return;
}

递归函数cycle_created代码 #

// Recursively check candidate node to see if cycle would be created
int cycle_created(int current, int cycle_start, int cycle)
{
    // Reached start of cycle, exit function and don't add edge
    if (current == cycle_start)
    {
        cycle++;
        return cycle;
    }

    else
    {
        // Loop through all pairs
        for (int j = 0; j < pair_count; j++)
        {
            // New candidate branch to investigate
            if (current == pairs[j].winner)
            {
                // Set new branch to check
                current = pairs[j].loser;

                // Call function to check new branch
                return cycle_created(current, cycle_start, cycle);
            }
        }

        // No edge found where current node is the winner, can lock edge
        return cycle;
    }
}

预期递归执行流程 #

• cycle_created(2,1,0)：j=0时current等于pairs[0].winner，current变为5，返回cycle_created(5,1,0)
• cycle_created(5,1,0)：j=5时current等于pairs[5].winner，current变为6，返回cycle_created(6,1,0)
• cycle_created(6,1,0)：j=6时current等于pairs[6].winner，current变为4，返回cycle_created(4,1,0)
• cycle_created(4,1,0)：j=4时current等于pairs[4].winner，current变为1，返回cycle_created(1,1,0)
• cycle_created(1,1,0)：current等于cycle_start，cycle设为1，返回1
• 后续递归栈依次返回1，最终cycle_created(2,1,0)返回1，应该跳过添加这条边，但实际没生效。

完整代码 #

#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
} pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
int cycle_created(int current, int cycle_start, int cycle);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i] = argv[i + 1];
    }

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // ranks[i] is voter's ith preference
        int ranks[candidate_count];

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    // Loop through each candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // Check if vote matches any existing candidates
        if (strcmp(candidates[i], name) == 0)
        {
            // Update ranks array to indicate rank of input candidate
            ranks[rank] = i;
            return true;
        }
    }

    // No candidate found
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // Loop through each candidate except final candidate (no preferences over others)
    for (int i = 0; i < candidate_count - 1; i++)
    {
        // Loop through candidates following the row candidate
        for (int j = i + 1; j < candidate_count; j++)
        {
            // Increment preferences array, since candidate i is preferred over candidate j
            preferences[ranks[i]][ranks[j]]++;
        }
    }

    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // Loop through row candidates (i)
    for (int i = 0; i < candidate_count; i++)
    {
        // Loop through column candidates (j)
        for (int j = 0; j < candidate_count; j++)
        {
            // Check if more voters prefer candidate i over candidate j
            if (preferences[i][j] > preferences[j][i])
            {
                // Update winner and loser in pairs array with index as current pair count
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;

                // Increment pair count total
                pair_count++;
            }
        }
    }

    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // Initialize temporary variable pair
    pair tmp;

    // Loop through each pair, except last pair
    for (int i = 0; i < pair_count - 1; i++)
    {
        // Loop through pair j following pair i
        for (int j = i + 1; j < pair_count; j++)
        {
            // Check if second pair vote count is greater than first pair vote count
            if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[i].winner][pairs[i].loser])
            {
                // Swap pairs
                tmp = pairs[i];
                pairs[i] = pairs[j];
                pairs[j] = tmp;
            }
        }
    }

    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Initialize variables
    int cycle_start;
    int current;
    int cycle;

    // Loop through pairs to determine acceptable locks
    for (int i = 0; i < pair_count; i++)
    {
        // Set new cycle start and current node
        cycle_start = pairs[i].winner;
        current = pairs[i].loser;

        // Reset Boolean
        cycle = 0;

        // If a cycle would be created, skip edge
        if (cycle_created(current, cycle_start, cycle) > 0)
        {
            continue;
        }

        else
        {
            // Add edge by locking pairs
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }

    return;
}

// Recursively check candidate node to see if cycle would be created
int cycle_created(int current, int cycle_start, int cycle)
{
    // Reached start of cycle, exit function and don't add edge
    if (current == cycle_start)
    {
        cycle = 1;
        return cycle;
    }

    else
    {
        // Loop through all pairs
        for (int j = 0; j < pair_count; j++)
        {
            // New candidate branch to investigate
            if (current == pairs[j].winner)
            {
                // Set new branch to check
                current = pairs[j].loser;

                // Call function to check new branch
                return cycle_created(current, cycle_start, cycle);
            }
        }

        // No edge found where current node is the winner, can lock edge
        return cycle;
    }
}

问题根源与修复方案 #

问题根源 #

1. 遍历逻辑错误：cycle_created的for循环中找到第一个匹配边就直接返回递归结果，忽略了其他可能形成循环的路径。
2. 未使用已锁定的边：遍历所有pairs数组中的边，但Tideman算法应只检查已锁定的边（locked数组为true的边），未锁定的边还未加入图，不会形成循环。
3. 参数冗余：cycle参数为值传递，逻辑上可简化为返回布尔类型。

修复后的cycle_created函数 #

// Recursively check if adding edge from cycle_start to current creates a cycle
bool cycle_created(int current, int cycle_start)
{
    // Found a cycle
    if (current == cycle_start)
    {
        return true;
    }

    // Check all locked edges starting from current
    for (int j = 0; j < candidate_count; j++)
    {
        if (locked[current][j])
        {
            // Recurse on the loser node, if any path returns true, cycle exists
            if (cycle_created(j, cycle_start))
            {
                return true;
            }
        }
    }

    // No cycle found
    return false;
}

修复后的lock_pairs调用 #

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Loop through pairs to determine acceptable locks
    for (int i = 0; i < pair_count; i++)
    {
        int winner = pairs[i].winner;
        int loser = pairs[i].loser;

        // Check if adding winner -> loser creates a cycle
        if (!cycle_created(loser, winner))
        {
            locked[winner][loser] = true;
        }
    }

    return;
}

修复说明 #

1. 只检查已锁定边：通过locked[current][j]判断已加入图的边，符合算法逻辑。
2. 遍历所有路径：对每个出边递归检查，只要有一条路径回到起点就返回循环存在。
3. 简化逻辑：去掉冗余参数，直接返回布尔值，代码更清晰。

内容的提问来源于stack exchange，提问作者Fulferr