{"record":{"id":"1cb5acfb9af6a64f","repo":"TheAlgorithms/C-Sharp","slug":"graph-must-be-connected","errorCode":null,"errorMessage":"Graph must be connected!","messagePattern":"Graph must be connected!","errorType":"exception","errorClass":"ArgumentException","httpStatus":null,"severity":"error","filePath":"Algorithms/Graph/MinimumSpanningTree/PrimMatrix.cs","lineNumber":105,"sourceCode":"        for (var i = 0; i < adjacencyMatrix.GetLength(0); i++)\n        {\n            var connection = false;\n            for (var j = 0; j < adjacencyMatrix.GetLength(0); j++)\n            {\n                if (Math.Abs(adjacencyMatrix[i, j] - adjacencyMatrix[j, i]) > 1e-6)\n                {\n                    throw new ArgumentException(\"Adjacency matrix must be symmetric!\");\n                }\n\n                if (!connection && float.IsFinite(adjacencyMatrix[i, j]))\n                {\n                    connection = true;\n                }\n            }\n\n            if (!connection)\n            {\n                throw new ArgumentException(\"Graph must be connected!\");\n            }\n        }\n    }\n\n    /// <summary>\n    ///     Determine which node should be added next to the MST.\n    /// </summary>\n    /// <param name=\"adjacencyMatrix\">Adjacency matrix of graph.</param>\n    /// <param name=\"key\">Currently known minimum edge weight connected to each node.</param>\n    /// <param name=\"added\">Whether or not a node has been added to the MST.</param>\n    /// <param name=\"parent\">The node that added the node to the MST. Used for building MST adjacency matrix.</param>\n    private static void GetNextNode(float[,] adjacencyMatrix, float[] key, bool[] added, int[] parent)\n    {\n        var numNodes = adjacencyMatrix.GetLength(0);\n        var minWeight = float.PositiveInfinity;\n\n        var node = -1;\n","sourceCodeStart":87,"sourceCodeEnd":123,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/Graph/MinimumSpanningTree/PrimMatrix.cs#L87-L123","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Ensure the input graph is connected: every node must have at least one finite-weight edge, or run the algorithm per connected component separately.","If the data legitimately has disconnected components, split the vertex set into components first and compute an MST for each one.","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.","Pre-check connectivity in caller code (BFS/DFS from node 0 over finite edges) and fail early with a clearer message."],"exampleFix":"// before\n// node 4 has no edges: adj[4,*] all NaN => disconnected\n\n// after\nadj[4, 1] = 2.5f;\nadj[1, 4] = 2.5f; // add an edge so every node is reachable","handlingStrategy":"validation","validationCode":"static bool HasNoIsolatedNodes(float[,] adj)\n{\n    for (int i = 0; i < adj.GetLength(0); i++)\n    {\n        bool any = false;\n        for (int j = 0; j < adj.GetLength(1) && !any; j++)\n            any = float.IsFinite(adj[i, j]);\n        if (!any) return false;\n    }\n    return true;\n}\nif (!HasNoIsolatedNodes(adj)) throw new ArgumentException(\"graph has isolated nodes / is disconnected\");","typeGuard":"static bool IsConnected(float[,] adj)\n{\n    int n = adj.GetLength(0);\n    if (n == 0) return true;\n    var seen = new bool[n];\n    var stack = new Stack<int>();\n    stack.Push(0); seen[0] = true;\n    while (stack.Count > 0)\n    {\n        int u = stack.Pop();\n        for (int v = 0; v < n; v++)\n            if (!seen[v] && float.IsFinite(adj[u, v])) { seen[v] = true; stack.Push(v); }\n    }\n    for (int i = 0; i < n; i++) if (!seen[i]) return false;\n    return true;\n}","tryCatchPattern":"try\n{\n    var mst = prim.Solve(adj);\n}\ncatch (ArgumentException ex) when (ex.Message == \"Graph must be connected!\")\n{\n    // split into connected components or add missing edges, then retry\n}","preventionTips":["Run a BFS/DFS connectivity check on the graph before calling Solve","Handle isolated/orphan nodes in your data pipeline explicitly","Verify your 'no edge' sentinel (NaN/Infinity) is not accidentally filling entire rows","Compute an MST per connected component when the input may be disconnected"],"tags":["csharp","graph","mst","connectivity","input-validation"],"backgroundTag":"invalid-argument-value","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}