Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.35 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement