SHARE
TWEET

Untitled

a guest Apr 23rd, 2019 122 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public IList<Vertex<T>> TopologicalSort()
  2. {  
  3.     // Dönüt listesi
  4.     IList<Vertex<T>> list = new List<Vertex<T>>();
  5.     // Düğüme gelen kenarların sayısı: in-degree
  6.     // degreeMap her düğüm için bu değeri tutuyor
  7.     IDictionary<Vertex<T>, int> degreeMap = new Dictionary<Vertex<T>, int>();
  8.     foreach(var vertex in Vertices)
  9.     {
  10.         if(vertex.IncomingVertices.Count == 0)
  11.         {
  12.             // in-degree = 0 için hiçbir şeye bağımlı değildir.
  13.             list.Add(vertex);
  14.         }
  15.         // Bütün düğümleri in-degreelerini sözlüğe at
  16.         degreeMap.Add(vertex, vertex.IncomingVertices.Count);
  17.     }
  18.     for (int i = 0; i < list.Count; i++)
  19.     {
  20.         // Bütün değerler için dön
  21.         // Bu liste içerde güncellenebilir.
  22.         DFSUtil(list[i], ref list, ref degreeMap);
  23.     }
  24.     return list;
  25. }
  26.  
  27. private void DFSUtil(Vertex<T> v, ref IList<Vertex<T>> result,
  28.     ref IDictionary<Vertex<T>, int> degreeMap)
  29. {
  30.     foreach (var outgoing in v.OutgoingVertices)
  31.     {
  32.         // Gidilen her düğüm için eğer in-degree 0 değilse
  33.         // in-degree'yi bir azalt
  34.         if(degreeMap[outgoing] != 0)
  35.         {
  36.             degreeMap[outgoing] -= 1;
  37.         }
  38.         // Eğer sıfırsa veya sıfıra düşmüşse listeye ekle
  39.         if(degreeMap[outgoing] == 0)
  40.         {
  41.             result.Add(outgoing);
  42.         }
  43.     }
  44. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top