-
Notifications
You must be signed in to change notification settings - Fork 287
/
DepthFirstTopSort.cs
46 lines (38 loc) · 1.33 KB
/
DepthFirstTopSort.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using System.Collections.Generic;
using Advanced.Algorithms.DataStructures.Graph;
namespace Advanced.Algorithms.Graph;
/// <summary>
/// Find Toplogical order of a graph using Depth First Search.
/// </summary>
public class DepthFirstTopSort<T>
{
/// <summary>
/// Returns the vertices in Topologically Sorted Order.
/// </summary>
public List<T> GetTopSort(IDiGraph<T> graph)
{
var pathStack = new Stack<T>();
var visited = new HashSet<T>();
//we need a loop so that we can reach all vertices
foreach (var vertex in graph.VerticesAsEnumberable)
if (!visited.Contains(vertex.Key))
Dfs(vertex, visited, pathStack);
//now just pop the stack to result
var result = new List<T>();
while (pathStack.Count > 0) result.Add(pathStack.Pop());
return result;
}
/// <summary>
/// Do a depth first search.
/// </summary>
private void Dfs(IDiGraphVertex<T> vertex,
HashSet<T> visited, Stack<T> pathStack)
{
visited.Add(vertex.Key);
foreach (var edge in vertex.OutEdges)
if (!visited.Contains(edge.TargetVertexKey))
Dfs(edge.TargetVertex, visited, pathStack);
//add vertex to stack after all edges are visited
pathStack.Push(vertex.Key);
}
}