# pgRouting Manual (3.0-rc1)

## pgr_connectedComponents

`pgr_connectedComponents` — Connected components of an undirected graph using a DFS-based approach.

Boost Graph Inside

Availability

- Version 3.0.0
  - Return columns change:
    - `n_seq` is removed
    - `seq` changed type to `BIGINT`
  - Official function
- Version 2.5.0
  - New experimental function

Support

- Supported versions: current(3.0)
- Unsupported versions: 2.6 2.5

## Description

A connected component of an undirected graph is a set of vertices that are all reachable from each other.

The main characteristics are:

- The signature is for an undirected graph.
- Components are described by vertices
- The returned values are ordered:
  - component ascending
  - node ascending
- Running time: \(O(V + E)\)

## Signatures

    pgr_connectedComponents(edges_sql)

    RETURNS SET OF (seq, component, node)
    OR EMPTY SET

Example: | The connected components of the graph

    SELECT * FROM pgr_connectedComponents(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table'
    );
     seq | component | node
    -----+-----------+------
       1 |         1 |    1
       2 |         1 |    2
       3 |         1 |    3
       4 |         1 |    4
       5 |         1 |    5
       6 |         1 |    6
       7 |         1 |    7
       8 |         1 |    8
       9 |         1 |    9
      10 |         1 |   10
      11 |         1 |   11
      12 |         1 |   12
      13 |         1 |   13
      14 |        14 |   14
      15 |        14 |   15
      16 |        16 |   16
      17 |        16 |   17
    (17 rows)

## Parameters

Parameter | Type | Default | Description
--- | --- | --- | ---
Edges SQL | `TEXT` |  | Inner query as described below.

## Inner query

edges SQL: | an SQL query of an undirected graph, which should return a set of rows with the following columns:

Column | Type | Default | Description
--- | --- | --- | ---
id | `ANY-INTEGER` |  | Identifier of the edge.
source | `ANY-INTEGER` |  | Identifier of the first end point vertex of the edge.
target | `ANY-INTEGER` |  | Identifier of the second end point vertex of the edge.

cost

`ANY-NUMERICAL`

Weight of the edge (source, target)

- When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

`ANY-NUMERICAL`

-1

Weight of the edge (target, source),

- When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER: | SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT

## Result Columns

Returns set of `(seq, component, node)`

Column | Type | Description
--- | --- | ---
seq | `BIGINT` | Sequential value starting from 1.
component | `BIGINT` | Component identifier. It is equal to the minimum node identifier in the component.
node | `BIGINT` | Identifier of the vertex that belongs to component.

## See Also

- Components - Family of functions
- The queries use the Sample Data network.
- Boost: Connected components
- wikipedia: Connected component

Indices and tables

- Index
- Search Page