Класс
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace WOrGraph { class Topological { private Boolean[] marked; // marked[v] = true if v is reachable from source(s) public Queue<int> Pre { get; } public Queue<int> Post { get; } public Stack<int> ReversePost { get; } public Topological(EdgeWeightedDigraph G) { Pre = new Queue<int>(); Post = new Queue<int>(); ReversePost = new Stack<int>(); marked = new bool[G.GetVertices()]; for (int v = 0; v < G.GetVertices(); v++) if (!marked[v]) Dfs(G, v); } public bool IsOrder() { return (ReversePost.Count > 0); } private void Dfs(EdgeWeightedDigraph G, int v) { marked[v] = true; Pre.Enqueue(v); foreach (DirectedEdge e in G.GetAdj(v)) { int w = e.To(); if (!marked[w]) Dfs(G, w); } Post.Enqueue(v); ReversePost.Push(v); } // --- validation private void ValidateVertex(int v) { int V = marked.Length; if (v < 0 || v >= V) { throw new ArgumentException("vertex " + v + " is not between 0 and " + "(V - 1)"); } } } } |
Пример использования
|
1 2 3 4 5 6 7 8 |
Topological topological = new Topological(G); if (!topological.IsOrder()) throw new ArgumentException("Digraph is not acyclic."); foreach (int v in topological.ReversePost) { foreach (DirectedEdge e in G.GetAdj(v)) // do smth } |