# Academic Citation for components() algorithm

**URL:** <https://igraph.discourse.group/t/academic-citation-for-components-algorithm/776>\
**Category:** Usage\
**Tags:** R\
**Created:** [9 June 2021 14:08 UTC](https://igraph.discourse.group/t/academic-citation-for-components-algorithm/776 "2021-06-09T14:08:26Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![tZV8ZSdpSuPkEhg8nQ5Z](https://avatars.discourse-cdn.com/v4/letter/t/ecc23a/32.png) [@tZV8ZSdpSuPkEhg8nQ5Z](https://igraph.discourse.group/u/tZV8ZSdpSuPkEhg8nQ5Z)\
**Post date:** [9 June 2021 14:08 UTC](https://igraph.discourse.group/t/academic-citation-for-components-algorithm/776/1 "2021-06-09T14:08:26Z")

</div>

What algorithm is used to implement components(), which returns the set of connected components If one were providing a citation to the algorithm used for this calculation, where would one cite?

The paper below seems to be the first and/or most common algorithm, but I wasn’t sure. Let me know if anyone knows.

Hopcroft, J.; Tarjan, R. (1973), “[Algorithm 447: efficient algorithms for graph manipulation](https://dl.acm.org/doi/10.1145/362248.362272)”, Communications of the ACM, 16 (6): 372–378, doi:10.1145/362248.362272

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [9 June 2021 17:13 UTC](https://igraph.discourse.group/t/academic-citation-for-components-algorithm/776/2 "2021-06-09T17:13:47Z")

</div>

> [@tZV8ZSdpSuPkEhg8nQ5Z](#):
>
> What algorithm is used to implement components(), which returns the set of connected components

You can find the source code here:

> <https://github.com/igraph/igraph/blob/master/src/connectivity/components.c#L89>

It looks to be doing a BFS. Do note that there is no guarantee that the details of the algorithm that igraph uses will not be changed in future versions.

> [@tZV8ZSdpSuPkEhg8nQ5Z](#):
>
> If one were providing a citation to the algorithm used for this calculation, where would one cite?

If you used igraph for your work, please do cite igraph. See [igraph Reference Manual](https://igraph.org/c/doc/igraph-Introduction.html#citing-igraph)

That said, finding connected components in an undirected graph is a fairly trivial operation whose solution is well known. You will find a description in any introductory graph theory or computer science textbook. Trying to find the very first treatment of this problem is rather misguided, unless you are doing research in the history of mathematics.

If you are writing for an audience whose members are unlikely to have much mathematical knowledge, do them a favour and cite a modern and accessible introductory textbook with an easy to understand description.