{"schema_version":"4ort.packet/1","entity":{"entity_id":"prim-s-algorithm","kg_uuid":"a1d66cf0-360b-4c76-87c8-55ac7ffbe531","wikidata_id":"Q470813","name":"Prim's algorithm","description":"algorithm for finding the minimum spanning tree for weighted undirected graphs","type":"Intangible","url":"https://4ort.xyz/entity/prim-s-algorithm"},"status":"complete","as_of":{"copy_written_at":"2026-11-14T01:42:46Z","last_source_edit_seen":"2026-11-14T01:42:37Z","stale_possible":false,"claims_refreshed_at":"2026-11-14T01:42:46Z","source_revision":2568971530},"facts":[{"field":"P31","label":"instance of","value":"algorithm","value_id":"Q8366","value_raw":"Q8366","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P31","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"graph algorithm","value_id":"Q30503704","value_raw":"Q30503704","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P31","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P31","label":"instance of","value":"greedy algorithm","value_id":"Q504353","value_raw":"Q504353","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P31","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Vojtěch Jarník","value_id":"Q730209","value_raw":"Q730209","rank":"normal","current":null,"qualifiers":[{"field":"P577","label":"publication date","value":"1930"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P61","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Robert C. Prim","value_id":"Q92939","value_raw":"Q92939","rank":"normal","current":null,"qualifiers":[{"field":"P577","label":"publication date","value":"1957"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P61","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P61","label":"discoverer or inventor","value":"Edsger W. Dijkstra","value_id":"Q8556","value_raw":"Q8556","rank":"normal","current":null,"qualifiers":[{"field":"P577","label":"publication date","value":"1959"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P61","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P138","label":"named after","value":"Robert C. Prim","value_id":"Q92939","value_raw":"Q92939","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P138","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P138","label":"named after","value":"Vojtěch Jarník","value_id":"Q730209","value_raw":"Q730209","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P138","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P366","label":"has use","value":"minimum spanning tree","value_id":"Q240464","value_raw":"Q240464","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P366","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P366","label":"has use","value":"decision tree","value_id":"Q831366","value_raw":"Q831366","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P366","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(|E| + |V| \\log |V|)","value_id":null,"value_raw":"O(|E| + |V| \\log |V|)","rank":"normal","current":null,"qualifiers":[{"field":"P2283","label":"uses","value":"Fibonacci heap"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P3752","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O((|V| + |E|) \\log |V|) = O(|E| \\log |V|)","value_id":null,"value_raw":"O((|V| + |E|) \\log |V|) = O(|E| \\log |V|)","rank":"normal","current":null,"qualifiers":[{"field":"P2283","label":"uses","value":"binary heap"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P3752","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3752","label":"worst-case time complexity","value":"O(|V|^2)","value_id":null,"value_raw":"O(|V|^2)","rank":"normal","current":null,"qualifiers":[{"field":"P2283","label":"uses","value":"adjacency list"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P3752","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"PrimsAlgorithm","value_id":null,"value_raw":"PrimsAlgorithm","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P5106","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"PrimJarniacutek","value_id":null,"value_raw":"PrimJarniacutek","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P5106","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"primJarnik","value_id":null,"value_raw":"primJarnik","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P5106","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P6366","label":"Microsoft Academic ID (discontinued)","value":"1649724","value_id":null,"value_raw":"1649724","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q470813#P6366","source_edition":"2026-11-14T01:42:46Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P61","P138","P366","P3752","P5106","P6366"]}],"routes":{"entity_page":"https://4ort.xyz/entity/prim-s-algorithm","packet_api":"https://4ort.xyz/api/v1/entities/prim-s-algorithm/packet","facts_jsonld":"https://4ort.xyz/entity/prim-s-algorithm/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=prim-s-algorithm","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=prim-s-algorithm","wikidata":"https://www.wikidata.org/wiki/Q470813","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":[]}