user3810795 user3810795 - 5 days ago 6
C# Question

How to check simple connectivity in graph?

I have this adjacency matrix :

enter image description here

And I don't know of can I check if any of the nodes are not connected with the others, I mean if it's alone , a rows and column of zeros for example the first one A, A should return false because is not exist simple connectivity

public bool HayConectividadsimple()
{
bool respuesta = true;
for (int i = 0; i < Aristas.GetLength(0); i++)
{
for (int j = 0; j < Aristas.GetLength(1); j++)
{
if (i, j == 0)
return false;
}
}
return respuesta;
}


Hope you can help me.

Best regards,

Answer

From my understanding you're looking for a whole row of 0 and a whole column of 0. If you spot either then return false. Roughly something like this:

For each node..

  1. check if it has an all 0 column
  2. Check if it has an all 0 row
  3. If both are true, return false

Return true otherwise.

So, that looks like this:

public bool HayConectividadsimple()
{

    // For each node..
    for (int i = 0; i < Aristas.GetLength(0); i++)
    {
        // Assume it's not connected unless shown otherwise.
        bool nodeIsConnected=false;

        // Check the column and row at the same time:
        for (int j = 0; j < Aristas.GetLength(1); j++)
        {
            if (Aristas[i, j] != 0 || Aristas[j, i] != 0)
            {
                // It was non-zero; must have at least one connection.
                nodeIsConnected=true;
                break;
            }
        }

        // Is the current node connected?
        if(!nodeIsConnected)
        {
            return false;
        }

    }

    // All ok otherwise:
    return true;
}
Comments