TheAlgorithms/C-Sharp · error · ArgumentException

Graph must be connected!

Error message

Graph must be connected!

What it means

Prim's algorithm builds a spanning tree only when the graph is connected; on a disconnected graph no spanning tree exists. ValidateMatrix checks each row of the adjacency matrix for at least one finite entry (an edge from that node) and throws ArgumentException when a node has none, i.e. the node is isolated so the graph is not connected. Solve calls this check before running the algorithm.

Solutions

1. Ensure the input graph is connected: every node must have at least one finite-weight edge, or run the algorithm per connected component separately.
2. If the data legitimately has disconnected components, split the vertex set into components first and compute an MST for each one.
3. Verify your 'no edge' sentinel handling — rows entirely filled with the sentinel (NaN/Infinity) are treated as isolated nodes; connect them with real edges if that is unintended.
4. Pre-check connectivity in caller code (BFS/DFS from node 0 over finite edges) and fail early with a clearer message.

Example fix

// before
// node 4 has no edges: adj[4,*] all NaN => disconnected

// after
adj[4, 1] = 2.5f;
adj[1, 4] = 2.5f; // add an edge so every node is reachable

static bool HasNoIsolatedNodes(float[,] adj)
{
    for (int i = 0; i < adj.GetLength(0); i++)
    {
        bool any = false;
        for (int j = 0; j < adj.GetLength(1) && !any; j++)
            any = float.IsFinite(adj[i, j]);
        if (!any) return false;
    }
    return true;
}
if (!HasNoIsolatedNodes(adj)) throw new ArgumentException("graph has isolated nodes / is disconnected");

static bool IsConnected(float[,] adj)
{
    int n = adj.GetLength(0);
    if (n == 0) return true;
    var seen = new bool[n];
    var stack = new Stack<int>();
    stack.Push(0); seen[0] = true;
    while (stack.Count > 0)
    {
        int u = stack.Pop();
        for (int v = 0; v < n; v++)
            if (!seen[v] && float.IsFinite(adj[u, v])) { seen[v] = true; stack.Push(v); }
    }
    for (int i = 0; i < n; i++) if (!seen[i]) return false;
    return true;
}

try
{
    var mst = prim.Solve(adj);
}
catch (ArgumentException ex) when (ex.Message == "Graph must be connected!")
{
    // split into connected components or add missing edges, then retry
}

When it happens

Trigger: Calling PrimMatrix.Solve with an adjacency matrix where some row i has no finite (edge) entry — an isolated vertex, or all its entries being non-finite (NaN/infinity sentinels) — meaning the graph has more than one connected component.

Common situations: A dataset with orphan nodes that have no edges; using NaN or float.PositiveInfinity for 'no edge' in a row where all connections were meant to be absent; merging subgraphs (e.g. two separate clusters) and forgetting a bridge edge; filtering edges out and accidentally disconnecting a node.

Understand the failure class

Background: "Must be a positive integer", "Invalid value", "Unsupported": the invalid-argument-value error family, when a library rejects the value you pass — this error's family across 35 libraries.

Related errors

• Matrix must be symmetric!
• Graph must be undirected!
• Adjacency matrix must be square!
• Adjacency matrix must be symmetric!
• The length of key should be divisible by 16

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/1cb5acfb9af6a64f. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Graph/MinimumSpanningTree/PrimMatrix.cs:105

        for (var i = 0; i < adjacencyMatrix.GetLength(0); i++)
        {
            var connection = false;
            for (var j = 0; j < adjacencyMatrix.GetLength(0); j++)
            {
                if (Math.Abs(adjacencyMatrix[i, j] - adjacencyMatrix[j, i]) > 1e-6)
                {
                    throw new ArgumentException("Adjacency matrix must be symmetric!");
                }

                if (!connection && float.IsFinite(adjacencyMatrix[i, j]))
                {
                    connection = true;
                }
            }

            if (!connection)
            {
                throw new ArgumentException("Graph must be connected!");
            }
        }
    }

    /// <summary>
    ///     Determine which node should be added next to the MST.
    /// </summary>
    /// <param name="adjacencyMatrix">Adjacency matrix of graph.</param>
    /// <param name="key">Currently known minimum edge weight connected to each node.</param>
    /// <param name="added">Whether or not a node has been added to the MST.</param>
    /// <param name="parent">The node that added the node to the MST. Used for building MST adjacency matrix.</param>
    private static void GetNextNode(float[,] adjacencyMatrix, float[] key, bool[] added, int[] parent)
    {
        var numNodes = adjacencyMatrix.GetLength(0);
        var minWeight = float.PositiveInfinity;

        var node = -1;

View on GitHub (pinned to 96e2905cab)