This repository has been archived by the owner on Oct 6, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 78
/
Copy pathtoposort in C#
92 lines (73 loc) · 2.25 KB
/
toposort in C#
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using System;
using System.Collections.Generic;
class Graph {
// No. of vertices
private int V;
// Adjacency List as ArrayList
// of ArrayList's
private List<List<int> > adj;
// Constructor
Graph(int v)
{
V = v;
adj = new List<List<int> >(v);
for (int i = 0; i < v; i++)
adj.Add(new List<int>());
}
// Function to add an edge into the graph
public void AddEdge(int v, int w) { adj[v].Add(w); }
// A recursive function used by topologicalSort
void TopologicalSortUtil(int v, bool[] visited,
Stack<int> stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
foreach(var vertex in adj[v])
{
if (!visited[vertex])
TopologicalSortUtil(vertex, visited, stack);
}
// Push current vertex to
// stack which stores result
stack.Push(v);
}
// The function to do Topological Sort.
// It uses recursive topologicalSortUtil()
void TopologicalSort()
{
Stack<int> stack = new Stack<int>();
// Mark all the vertices as not visited
var visited = new bool[V];
// Call the recursive helper function
// to store Topological Sort starting
// from all vertices one by one
for (int i = 0; i < V; i++) {
if (visited[i] == false)
TopologicalSortUtil(i, visited, stack);
}
// Print contents of stack
foreach(var vertex in stack)
{
Console.Write(vertex + " ");
}
}
// Driver code
public static void Main(string[] args)
{
// Create a graph given
// in the above diagram
Graph g = new Graph(6);
g.AddEdge(5, 2);
g.AddEdge(5, 0);
g.AddEdge(4, 0);
g.AddEdge(4, 1);
g.AddEdge(2, 3);
g.AddEdge(3, 1);
Console.WriteLine("Following is a Topological "
+ "sort of the given graph");
// Function Call
g.TopologicalSort();
}
}