This should ideally be more of a comment than an answer, but don't yet have enough rep to comment.
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.
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.
