Class BreadthFirstTraversal<TEdge, TNode>

Base class for all BFT strategies, i.e. all traversing strategies which visit all the nodes at the current depth, along any path of the tree, before going deeper or shallower, exploring nodes with higher or lower depth.

Inheritance
System.Object
TreeTraversal<TEdge, TNode>
BreadthFirstTraversal<TEdge, TNode>
FullyIterativeBreadthFirstTraversal<TEdge, TNode>
FullyRecursiveBreadthFirstTraversal<TEdge, TNode>
Implements
IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.RecImmTrees.Visitor
Assembly: MoreStructures.dll
Syntax
public abstract class BreadthFirstTraversal<TEdge, TNode> : TreeTraversal<TEdge, TNode>, IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge
TNode
Remarks

TRAVERSAL VS VISIT
The word "traversal" in TreeTraversal<TEdge, TNode> and its derivations, is here used with narrower scope than the word "visit" in IVisitStrategy<TNode, TVisitContext>.
- "Traversal" is used here as common class between DFS and BFS, as a visit strategy that starts from the root of the tree and proceeds downwards, following edges and terminating when leafs are reached.
- "Visit" is used in a more general sense, as any algorithm which "touches" 0 or more nodes of the tree, walking the tree in any possible way (up, down, sideways, ...).

Examples

Given the following tree structure:

0
|- 0 -> 1
|       |- 1 -> 2
|       |- 2 -> 3
|       |       |- 3 -> 4
|       |- 4 -> 5
|- 5 -> 6
|- 6 -> 7
        |- 7 -> 8
                |- 8 -> 9
                |- 9 -> 10

A BFT visit strategy "parent first" would visit nodes and edges in either of the following ways, depending on how children are sorted (lower-id edge first, lower-id edge last, median-id edge first, ...):
- { (null, 0), (0, 1), (5, 6), (6, 7), (1, 2), (2, 3), (4, 5), (7, 8), (3, 4), (8, 9), (9, 10) }
- { (null, 0), (6, 7), (5, 6), (0, 1), (7, 8), (4, 5), (2, 3), (1, 2), (9, 10), (8, 9), (3, 4) }
- { (null, 0), (5, 6), (6, 7), (0, 1), (7, 8), (2, 3), (4, 5), (1, 2), (9, 10), (8, 9), (3, 4) }
- ...

A BFT visit strategy "children first" would visit nodes and edges in either of the following ways, depending on how children are sorted:
- { (3, 4), (8, 9), (9, 10), (1, 2), (2, 3), (4, 5), (7, 8), (0, 1), (5, 6), (6, 7), (null, 0) }
- { (9, 10), (8, 9), (3, 4), (7, 8), (4, 5), (2, 3), (1, 2), (6, 7), (5, 6), (0, 1), (null, 0) }
- ...

Implements

Extension Methods