проверьте, есть ли цикл в ориентированном графе CS50 tideman

для проверки цикла программа переходит от первого узла в графе к каждому заблокированному узлу в графе-> проверяет, посещался ли он раньше, затем это цикл, иначе повторяется рекурсивно с проверенного следующего узла. когда я тестирую это сам, он работает, но когда я использую его на выборах tideman, он не работает.

объяснение проблемы: https://cs50.harvard.edu/x/2020/psets/3/tideman/

Цель этой задачи - выбрать победителя на выборах с помощью алгоритма голосования tideman. CS50 ide предоставляет тестовую функцию Check50, я пытаюсь исправить эти ошибки: 1.lock_pairs пропускает последнюю пару, если создает цикл. 2.lock_pairs пропускает среднюю пару, если создает цикл.

моя логика неверна?

int graph[nodes_count][nodes_count];
bool check_cycle()
{
    //if a node is visited during checking cycles visited[]=true
    bool visited[nodes_count];
    bool circle = false;
    return gointo(circle, visited, 0);
}
bool gointo(bool &circle, bool visited[], int to)
{
// start trip form one node in the graph check if it have been visited ( Cycle )
    visited[to] = true;
    for (int n = 0; n < nodes_count; n++)
    {
        if (graph[to][n])
        {
            if (visited[n])
            {
                circle = true;
            }
            else
            {
                gointo(visited, n);
            }
            break;
        }
    }

    return circle;
}

мое полное решение: https://pastebin.com/sbua3EGA
спасибо за ваше время и извините за плохое английский :)


c cs50 algorithm adjacency-matrix directed-graph
person Breair Sabir    schedule 14.06.2020    source источник
comment
У вас больше шансов получить ответы, если вы предоставите короткий фрагмент кода, демонстрирующий проблему, а не 250 строк.   -  person Han-Kwang Nienhuys    schedule 14.06.2020
comment
@ Han-Kwang Nienhuys ОК, готово. я поместил всю программу, потому что я пробовал работать с моим собственным графиком заблокированных пар и его работой   -  person Breair Sabir    schedule 14.06.2020
comment
Так лучше, но вам все равно нужно объяснить, что представляют собой различные переменные: pairs, locked, visited.   -  person Han-Kwang Nienhuys    schedule 14.06.2020
comment
@ Han-Kwang Nienhuys, я постараюсь изо всех сил, если вы хотите полностью понять проблему, пожалуйста, проверьте ссылку в вопросе.   -  person Breair Sabir    schedule 14.06.2020
comment
Посмотрите, как задать хороший вопрос.   -  person Han-Kwang Nienhuys    schedule 14.06.2020
comment
Если граф содержит два несвязанных подграфа, то ваш алгоритм может дать сбой. Предположим, что у первого подграфа нет цикла, а у второго есть циклы, но если вы запустили dfs на первом графике, то dfs завершится, и вы не заметите цикла.   -  person Deepak Patankar    schedule 14.06.2020
comment
@ Дипак-Патанкар, верно, спасибо .. но в данной ситуации этого не произойдет   -  person Breair Sabir    schedule 14.06.2020
comment
Хорошо, @BreairSabir Ваша реализация алгоритма определения цикла мне кажется правильной.   -  person Deepak Patankar    schedule 14.06.2020

Ответы (1)


arrow_upward
1
arrow_downward

Ваш алгоритм будет правильным в неориентированном графе. В ориентированных графах это не так очевидно.

Во-первых, начиная с узла 0 вы не можете посещать все узлы. Контрпример: 1 -> 0 -> 2

Когда вы начинаете проверку с узла 0, вы вообще не посетите 1. Если у 1 также есть край цикла, вы его не обнаружите. Это означает, что вы должны сделать цикл для каждой вершины и, если она еще не посещена, запустить функцию gointo.

С помощью описанного выше изменения вы можете обнаружить циклы, когда их нет.

Например:

1 -> 2 -> 3

4 -> 2

Если вы сначала выполните gointo (1), вы отметите 1, 2 и 3 как посещенные. Затем при вызове gointo (4) вы «обнаружите цикл», поскольку 4 имеет ребро к уже отмеченной вершине. Вот почему вам нужны два массива: один, который сообщает, что вы уже посетили узел, другой, который сообщает, что узел был посещен в этом конкретном вызове gointo.

Код должен выглядеть так:

int graph[nodes_count][nodes_count];
bool check_cycle()
{
    //if a node is visited during checking cycles visited[]=true
    bool visited[nodes_count];
    bool this_call[nodes_count];
    bool circle = false;
    for (int i = 0; i < nodes_count; ++i)
    {
         if(!visited[i] && gointo(circle, visited, i))
           return true;
    }
    return false;
}
bool gointo(bool &circle, bool visited[], int to)
{
// start trip form one node in the graph check if it have been visited ( Cycle )
    visited[to] = true;
    this_call[to] = true;
    for (int n = 0; n < nodes_count; n++)
    {
        if (graph[to][n])
        {
            if (visited[n] && this_call[n])
            {
                circle = true;
            }
            else if(!visited[n])
            {
                gointo(visited, n);
            }
        }
    }
    this_call[to] = false;
    return circle;
}
person Maras    schedule 15.06.2020