Блог пользователя iamscrew

Автор iamscrew, 10 лет назад, По-английски

Topological Sorting Help !!!

I read in tutorial to use the topological sorting in this question Fox and Names . I know that we have to find if there exists a order of alphabets such that name1<name2, name2<name3, name3<name4,and so on... but i could not help out how it is implemented and what is the basic idea behind this topological sorting algorithm? Can someone please help . ? Thanks in advance.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to implement topological sort ? I think that the easiest way is to

  1. add to Queue vertives, which have zero in-degree.

Loop

  1. Get vertex from queue ( let's say it is vertex v) and add to result list

  2. Decrement all in-degree of neighbours of v. If a neighbour will have in-degree equal 0, add to queue

If not possible to continue, check if list contains all vertices ( if yes == no cycle found ) , result list contains topological order

Sorry for my english

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ok thanks, i get your idea, what if graph is given like this 1-2-3-4-5 and no vertex is having zero-in-degree. ? or this algorithm works for directed graph (1->2->3->4->5) . ?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, here's the main idea:-

Initial Observation :

name1 < name2, if and only if, the letter that comes up right after their longest common prefix in name1, is lexicographically lesser than that occurring in name2. Thus you get conditions of the type : (char1 should come before char2) , for each consecutive pair of names.

Final Idea : Imagine the letters as nodes, and the condition (char1 should come before char2) as a directed edge from char1 to char2. Thus the answer to the main question reduces to finding the topological sort of the directed graph described above.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For implementation, refer the wikipedia article or my solution :-http://codeforces.net/contest/512/submission/9724237

    There are two corner cases as well, which I encourage you to find on your own.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If a graph has edges 1->2 2->3 2->4 What would the topological sort result into ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1,2,3,4 and 1,2,4,3 are both correct. The definition of topological sort is a sequence of all nodes in a graph where each node appears before all of his children.