# Concept derivation guides

299 concept teaching guides, separate from the 36,000 individual question derivations.

[Search all questions & derivations →](/en/explore/)

1 1 results · Page 1 of 1



Concept guide



## [Connected components: finding every component of a finite simple graph by complete BFS](/en/derivations/derivation-mko-connected-component-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-connected-component)

Let G=(V,E) with V={0,1,2,3,4,5,6} and E consisting of exactly the five edges {0,1}, {0,2}, {1,2}, {3,4}, {4,5}. First prove that 'joined by a path' is an equivalence relation on V; then compute each equivalence class by complete BFS, prove that the set BFS returns is exactly that class, and conclude Q(G)={{0,1,2},{3,4,5},{6}}, where the isolated vertex 6 forms a singleton component.

Connected component

derivation-mko-connected-component-01





1 1 results · Page 1 of 1