Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: connected_components
Note: This documentation is automatically generated.
Finds the connected components in an undirected graph:
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
If you have a fixed graph where the node are dense integers, use GetConnectedComponents(): it's very fast and uses little memory.
If you have a more dynamic scenario where you want to incrementally add nodes or edges and query the connectivity between them, use the [Dense]ConnectedComponentsFinder class, which uses the union-find algorithm aka disjoint sets:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["The core content details two methods for finding connected components in an undirected graph. `GetConnectedComponents()` is recommended for static graphs with dense integer nodes, offering speed and efficiency. For dynamic scenarios involving incremental changes, `DenseConnectedComponentsFinder` is suggested. It employs the union-find algorithm. Two classes, `ConnectedComponentsFinder` and `DenseConnectedComponentsFinder`, are provided for these respective approaches. Both are designed to determine the connected components within a given graph structure.\n"],null,[]]
