CODEWITHSUNDEEP
calgorithmcs50adjacency-matrixdirected-graph
Breair Sabir
Breair Sabir

Reputation: 54

check if there is a cycle in directed graph CS50 tideman

to check cycle the program goes from first node in the graph to every locked node in the graph-> check if its visited before ,then its a cycle ,,else repeat recursively from the checked next node. when i test it myself it works but when i use it in tideman election it doesnt.

explanation of the problem : https://cs50.harvard.edu/x/2020/psets/3/tideman/

The goal in this problem to pick a winner from election using tideman voting algorithm. CS50 ide provides test function Check50 ,I am trying to fix these errors: 1.lock_pairs skips final pair if it creates cycle 2.lock_pairs skips middle pair if it creates a cycle.

is my logic wrong?

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;
}

my full solution:https://pastebin.com/sbua3EGA
thanks for yours time and sorry for bad english :)

Upvotes: 1

Views: 1873

Answers (1)

Maras
Maras

Reputation: 982

Your algorithm would be correct in undirected graph. In directed graphs it is not that obvious.

First of all, starting from node 0 you may not visit all the nodes. Counterexample: 1 -> 0 -> 2

When you start checking from node 0, you will not visit 1 at all. If 1 also has an edge to a cycle, you will not detect it. That means, you should make a loop for each vertex and if it's not visited yet, run 'gointo' function.

With the change described above you may end up finding cycles when there are not any.

For example:

1 -> 2 -> 3

4 -> 2

If you first do gointo(1), you will mark 1, 2 and 3 as visited. Then when calling gointo(4) you will 'detect a cycle', since 4 has edge to already marked vertex. That's why you need two arrays, one that tells that you've already visited the node, the other one that tells that the node was visited in this specific gointo call.

Code should look like this:

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;
}

Upvotes: 1

Related Questions