CODEWITHSUNDEEP
algorithmsortinggraphtime-complexity
verticese
verticese

Reputation: 273

Sort lists in an adjacency list each in increasing order

In a directed graph I want an O(n+m) algorithm to sort lists in an adjacency list, so that names of vertices are sorted in increasing order in each list. The only one I can think of is to perform an insertion sort, on each of the list, but this definitely does not run in O(n+m). Can someone help me with this? Thanks

Upvotes: 0

Views: 4052

Answers (3)

Khoa Nguyen
Khoa Nguyen

Reputation: 46

This solution does not utilize radix sort, but rather relies on order of the vertices in the adjacency list itself and the concept of incoming/outcoming edges.

This is assuming we have the graph G in the form of an adjacency list with the vertices already ordered. In particular, the data structure used for the adjacency list has to be an array (or any data structure that allows random access) of linked-lists. Each index of the array corresponds to a vertex in the graph, and the linked-list contains its adjacent vertices. Let n and m be the number of vertices and edges respectively. To illustrate, let's say we have the following directed graph G:

G:

[1] -> 4,5,2

[2] -> 3,1

[3] -> x (no neighbors)

[4] -> 1,2

[5] -> 4

  1. Create a separate copy of the vertices as another adjacency list where all the linked-lists are empty. We call this G'. This step will take O(n) time.

G':
[1] ->

[2] ->

[3] ->

[4] ->

[5] ->

  1. We walk through each vertex of G, and for each neighbor examined, we add to the corresponding neighbor vertex in G' the parent vertex. So for example, if in G we have [1]->4,5,2, we would add in G' [4]->1, [5]->1, and [2]->1, as demonstrated below:

G':
[1] ->

[2] -> 1

[3] ->

[4] -> 1

[5] -> 1

Repeat this for all vertices in G. This process will take O(n+m) time.

  1. After step 2, we will have completed G', a directed graph representing incoming-edges of vertices in G. In G', it can be observed that the adjacent vertices are sorted in increasing order. This is because in step 2, we iterate through an ordered array of parent vertices ([1],[2],[3],[4],[5]), and thus 1 is the first to be added to G' (in this case 1 is first added to [2],[4],and [5] since 2,4, and 5 are adjacent to [1] in G). Then 2 follows, and 3, and so on. G' is as follows:

G':

[1] -> 2,4

[2] -> 1,4

[3] -> 2

[4] -> 1,5

[5] -> 1

  1. To turn G' into an outcoming-edge directed graph like G again, we performed step 2 again, but now switch the position of G and G'. We will iterate through G', and write the result in G. The result is a sorted G, as shown below:

G-sorted:

[1] -> 2,4,5

[2] -> 1,3

[3] -> x

[4] -> 1,2

[5] -> 4

Similarly to step 2, this process will take O(n+m) time.

  1. Congratulations, you have obtained a sorted directed graph in O(n+m) time

The undirected version is easier than this one, as you only have to perform step 2 once and not have to do it again in step 4 (no distinction between incoming-edges and out-coming edges)

Upvotes: 2

ghui
ghui

Reputation: 166

I don't have enough points ask this via comment yet, so I'm going to assume n is the number of vertices and m is the number of edges. By sorting by names of vertices, I'm going to assume you mean you want to sort alphabetically. If that's the case, then you might be able to use linear time sorting algorithms to achieve O(n+m), namely Radix sort. As long as the length of the vertex names is not huge, using Radix sort for each of the lists will take O(n+m) time total. Check out the wiki for radix sort:

https://en.wikipedia.org/wiki/Radix_sort

Upvotes: 0

aghast
aghast

Reputation: 15310

I don't believe this is possible. Your request for O(n+m) time suggests that you are looking for a topological sort of the graph. But while that will order the graph, it doesn't allow for the comparisons necessary to order the nodes/edges by another metric (the string node name).

Perhaps you have not stated the problem precisely?

Upvotes: 0

Related Questions