Advertisement
mikymaione

Topological_Sorting

Feb 9th, 2017
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.22 KB | None | 0 0
  1.  
  2.  
  3.         public void Topological_Sorting()
  4.         {
  5.             var L = new HashSet<Nodo>();
  6.  
  7.             Action<Nodo> Visit = null;
  8.             Visit = (n) =>
  9.             {
  10.                 // if n has a temporary mark then stop (not a DAG)
  11.                 if (n.color == Nodo.Color.Gray)
  12.                     throw new Exception("not a DAG!");
  13.  
  14.                 // if n is not marked(i.e.has not been visited yet) then
  15.                 if (n.color == Nodo.Color.White)
  16.                 {
  17.                     // mark n temporarily
  18.                     n.color = Nodo.Color.Gray;
  19.  
  20.                     // for each node m with an edge from n to m do visit(m)
  21.                     foreach (var m in Adj[n])
  22.                         Visit(m);
  23.  
  24.                     // mark n permanently
  25.                     n.color = Nodo.Color.Black;
  26.                     // add n to head of L
  27.                     L.Add(n);
  28.                 }
  29.             };
  30.  
  31.             foreach (var v in V)
  32.                 if (v.color == Nodo.Color.White)
  33.                     Visit(v);
  34.  
  35.             Console.Write("Topological sort: ");
  36.             foreach (var x in L)
  37.                 Console.Write(x.N + " ");
  38.             Console.WriteLine();
  39.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement