Implementing the CutHill-McKee Algorithm
Regarding readability, it is generally a good practice to avoid using unnecessarily shortened forms like adjcncy, as it is only two characters short of adjacency. Also using R for result_queue is discouraged in general (subjective opinion).

If there is no constraint on it being pure python, you may try Cython to get speeds closer to that of C, without moving too far away from the python syntax.