Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public IList<Vertex<T>> TopologicalSort()
- {
- // Dönüt listesi
- IList<Vertex<T>> list = new List<Vertex<T>>();
- // Düğüme gelen kenarların sayısı: in-degree
- // degreeMap her düğüm için bu değeri tutuyor
- IDictionary<Vertex<T>, int> degreeMap = new Dictionary<Vertex<T>, int>();
- foreach(var vertex in Vertices)
- {
- if(vertex.IncomingVertices.Count == 0)
- {
- // in-degree = 0 için hiçbir şeye bağımlı değildir.
- list.Add(vertex);
- }
- // Bütün düğümleri in-degreelerini sözlüğe at
- degreeMap.Add(vertex, vertex.IncomingVertices.Count);
- }
- for (int i = 0; i < list.Count; i++)
- {
- // Bütün değerler için dön
- // Bu liste içerde güncellenebilir.
- DFSUtil(list[i], ref list, ref degreeMap);
- }
- return list;
- }
- private void DFSUtil(Vertex<T> v, ref IList<Vertex<T>> result,
- ref IDictionary<Vertex<T>, int> degreeMap)
- {
- foreach (var outgoing in v.OutgoingVertices)
- {
- // Gidilen her düğüm için eğer in-degree 0 değilse
- // in-degree'yi bir azalt
- if(degreeMap[outgoing] != 0)
- {
- degreeMap[outgoing] -= 1;
- }
- // Eğer sıfırsa veya sıfıra düşmüşse listeye ekle
- if(degreeMap[outgoing] == 0)
- {
- result.Add(outgoing);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement