0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Complexity of sorting serial numbers is O(N), not O(N log N): you can use radix sort or counting sort. $\endgroup$ – jkff Nov 7 '15 at 4:26
  • $\begingroup$ 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. $\endgroup$ – orezvani Jul 4 '16 at 0:25
  • 2
    $\begingroup$ @user118972 What non-homework use of this do you have that requires the exact complexity of O(V+E)? $\endgroup$ – jmite Aug 3 '16 at 2:03
1
$\begingroup$

Hint:

  1. Use BFS to calculate the distances.
  2. Calculate the scores (sums of distance to source and serial number).
  3. Use counting sort to sort the scores.
  4. Go over the list again and output the vertices in sorted order.
$\endgroup$
  • $\begingroup$ Hi! Could you please elaborate more on this approach? If i am not mistaken, this would fail for the following graph : (s,a),(s,b),(b,c) where sn(a)=4, sn(b)=sn(c)=1. score(a)=5 whereas score(c)=3 so final answer would be [b,c,a] instead of [b,a,c] $\endgroup$ – jjohn Oct 9 '15 at 21:02
  • $\begingroup$ @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. $\endgroup$ – orezvani Aug 3 '16 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.