Cuthill–McKee algorithm: Difference between revisions

Revision as of 16:24, 16 January 2017

Revision as of 16:25, 16 January 2017

Line 23:

Then for <math>i = 1,2,\dots</math> we iterate the following steps while <math>|R| < n</math>

*Construct the adjacency set <math>A_i</math> of <math>R_i</math> (with <math>R_i</math> the ''i''-th component of ''<math>R''</math>) and exclude the vertices we already have in ''<math>R''</math>

:<math>A_i := \operatorname{Adj}(R_i) \setminus R</math>

*Sort <math>A_i</math> with ascending vertex order ([[Degree (graph theory)|vertex degree]]).

*Append <math>A_i</math> to the Result set ''<math>R''</math>.

In other words, number the vertices according to a particular [[breadth-first search|breadth-first traversal]] where neighboring vertices are visited in order from lowest to highest vertex order.