На примере поиска цикла в графе
|
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 |
private void Dfs(Digraph G, int v) // v is start vertex here { onStack[v] = true; marked[v] = true; foreach (int w in G.GetAdj(v)) { // short circuit if directed cycle found if (cycle != null) return; // found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; Dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<int>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.Push(x); } cycle.Push(w); cycle.Push(v); Debug.Assert(Check()); } } onStack[v] = false; } |
|
1 2 3 4 |
public IEnumerable<int> GetCycle() { return cycle; } |
В другом классе используем так…
|
1 2 3 4 5 |
public Stack<int> GetCycle(Digraph G) { DirectedCycle o = new DirectedCycle(G); return new Stack<int>(o.GetCycle()); } |