# Find an algorithm that sorts the nodes of a given graph acc. to distance from source node + value of the node's key

an unweighted connected graph $G=(V,E)$ all nodes of the graph contain a "serial number" between 1 to V. (V is an integer).

I am trying to come up with an algorithm that sorts all nodes firstly by distance (number of eadges) from source node 's' , secondly- if two nodes have same distance value sort them by value of thier serial number.

complexity required is $O (V+E)$

I tried to solve this via using bfs and then recieve a "bucket" array of distances - for each distance $1,2...$ all nodes within it are in its "bucket". the problem is, that in order to sort two nodes with same distance according to their serial number takes at least $O( nlogn)$ of sorting. I tried to come up with a use $v-1$ empty arrays and tried to send each "bucket" nodes acc. to their index in the graph and print it - that takes )$V^2$.

This is NOT homework, I really did try my best. Your comments are appreciated.

• Complexity of sorting serial numbers is O(N), not O(N log N): you can use radix sort or counting sort.
– jkff
Nov 7 '15 at 4:26
• When you are sorting all nodes with distance $i$, assume that you are sorting a separate array using linear sort. Basically, you want to perform the linear sort two times. Jul 4 '16 at 0:25
• @user118972 What non-homework use of this do you have that requires the exact complexity of O(V+E)? Aug 3 '16 at 2:03

• @jjohn You need to create a vector d[serialNumber] = distance from source to node associated with serialNumber; then you can use counting sort on it. Aug 3 '16 at 3:19