Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// <summary>
- /// Kosaraju's strongly connected components algorithm
- /// </summary>
- public void Kosaraju()
- {
- var L = new HashSet<Nodo>();
- Action<Nodo> Visit = null;
- Visit = (u) =>
- {
- // If u is unvisited then:
- if (u.color == Nodo.Color.White)
- {
- // Mark u as visited.
- u.color = Nodo.Color.Gray;
- // For each out-neighbour v of u, do Visit(v).
- foreach (var v in Adj[u])
- Visit(v);
- // Prepend u to L
- L.Add(u);
- }
- };
- Action<Nodo, Nodo> Assign = null;
- Assign = (u, root) =>
- {
- // If u has not been assigned to a component then
- if (u.color != Nodo.Color.Black)
- {
- // Assign u as belonging to the component whose root is root.
- if (u == root)
- Console.Write("SCC: ");
- Console.Write(u.N + " ");
- u.color = Nodo.Color.Black;
- // For each in-neighbour v of u, do Assign(v,root).
- foreach (var v in Adj[u])
- Assign(v, root);
- if (u == root)
- Console.WriteLine();
- }
- };
- // For each vertex u of the graph do Visit(u)
- foreach (var u in V)
- Visit(u);
- // For each element u of L in order, do Assign(u,u)
- foreach (var u in L)
- Assign(u, u);
- }
- /// <summary>
- /// Tarjan's strongly connected components algorithm, Time: O(|V|+|E|)
- /// </summary>
- public void Tarjan()
- {
- Console.WriteLine($"Tarjan su {Nome}");
- var indice = 0; // number of nodes
- var S = new Stack<Nodo>();
- Action<Nodo> StrongConnect = null;
- StrongConnect = (v) =>
- {
- // Set the depth index for v to the smallest unused index
- v.indice = indice;
- v.minima_distanza = indice;
- indice++;
- S.Push(v);
- // Consider successors of v
- foreach (var w in Adj[v])
- if (w.indice < 0)
- {
- // Successor w has not yet been visited; recurse on it
- StrongConnect(w);
- v.minima_distanza = Math.Min(v.minima_distanza, w.minima_distanza);
- }
- else if (S.Contains(w))
- // Successor w is in stack S and hence in the current SCC
- v.minima_distanza = Math.Min(v.minima_distanza, w.indice);
- // If v is a root node, pop the stack and generate an SCC
- if (v.minima_distanza == v.indice)
- {
- Console.Write("SCC: ");
- Nodo w = null;
- while (v != w && S.Count > 0)
- {
- w = S.Pop();
- Console.Write(w.N + " ");
- }
- Console.WriteLine();
- }
- };
- foreach (var v in V)
- if (v.indice < 0)
- StrongConnect(v);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement