Class BFS

Implements Breadth First Search algorithm for graph traversal.

Inheritance

System.Object

BFS

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: AlgorithmsAndDataStructures.Algorithms.GraphTraversal

Assembly: AlgorithmsAndDataStructures.dll

Syntax

public class BFS

Methods

| Improve this Doc View Source

BFS_Iterative<TValue>(GraphNode<TValue>)

An iterative version of Breadth First Search algorithm for traversing a graph that might have cycles.

Declaration

public static List<GraphNode<TValue>> BFS_Iterative<TValue>(GraphNode<TValue> startNode)

Parameters

Type	Name	Description
GraphNode<TValue>	startNode	A node in the graph from which traversal starts.

Returns

Type	Description
System.Collections.Generic.List<GraphNode<TValue>>	A sequence of all graph nodes, put into a BFS ordering.

Type Parameters

Name	Description
TValue	Type of the values stored in graph nodes.

Remarks

A graph can have many BFS orderings. Each ordering depends on (i) the start node, and (ii) the order by which each node's adjacent nodes are visited.

| Improve this Doc View Source

BFS_Recursive<TValue>(Queue<GraphNode<TValue>>, List<GraphNode<TValue>>)

A recursive version of Breadth First Search algorithm for traversing a graph that might have cycles. A graph can have many BFS orderings. Each ordering depends on (i) the start node, and (ii) the order by which each node's adjacent nodes are visited.

Declaration

public static void BFS_Recursive<TValue>(Queue<GraphNode<TValue>> queue, List<GraphNode<TValue>> bfsOrdering)

Parameters

Type	Name	Description
System.Collections.Generic.Queue<GraphNode<TValue>>	queue	A queue structure for tracking nodes. The queue is expected to have the start node enqueued in it.
System.Collections.Generic.List<GraphNode<TValue>>	bfsOrdering	A sequence of all graph nodes, put into a BFS ordering.

Type Parameters

Name	Description
TValue	Type of the values stored in graph nodes.