c# - 如何检查图中的简单连通性？

Question

我有这个邻接矩阵:

而且我不知道是否可以检查是否有任何节点未与其他节点连接。我的意思是，如果它是单独的，一行和一列零(例如，第一个 A)应该返回 false，因为不存在简单连接。

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

希望你能帮助我。

最好的问候，

Answer 1

根据我的理解，您正在寻找一整行 0 和一整列 0。如果您发现其中任何一个，则返回 false。大致是这样的:

对于每个节点..

1. 检查它是否有全0列
2. 检查是否有全0行
3. 如果两者都为真，则返回假

否则返回真。

所以，看起来像这样:

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