Assembly: QuickGraph.Algorithms (in QuickGraph.Algorithms.dll) Version: 2.4.2.1407 (2.4.2.1407)
Syntax
| C# |
|---|
public class BreadthFirstSearchAlgorithm : IPredecessorRecorderAlgorithm, IDistanceRecorderAlgorithm, IVertexColorizerAlgorithm, ITreeEdgeBuilderAlgorithm, IAlgorithm |
| Visual Basic (Declaration) |
|---|
Public Class BreadthFirstSearchAlgorithm _ Implements IPredecessorRecorderAlgorithm, IDistanceRecorderAlgorithm, IVertexColorizerAlgorithm, ITreeEdgeBuilderAlgorithm, _ IAlgorithm |
Remarks
A breadth-first-search (BFS) traversal visits vertices that are closer to the source before visiting vertices that are further away. In this context ``distance'' is defined as the number of edges in the shortest path from the source vertex.
The BFS can be used to compute the shortest path from the source to all reachable vertices and the resulting shortest-path distances.
BFS uses two data structures to to implement the traversal: a color marker for each vertex and a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray vertices.
The algorithm proceeds by removing a vertex u from the queue and examining each out-edge (u,v). If an adjacent vertex v is not already discovered, it is colored gray and placed in the queue. After all of the out-edges are examined, vertex u is colored black and the process is repeated. Pseudo-code for the BFS algorithm is a listed below.
CopyC#IVertexListGraph g;
BFS(IVertex s)
{
// initialize vertices
foreach(IVertex u in g.Vertices)
{
Colors[u] = White;
OnInitializeVertex(u); // event
}
Visit(s);
}
Visit(IVertex s)
{
Colors[s]=GraphColor.Gray;
OnDiscoverVertex(s); //event
m_Q.Push(s);
while (m_Q.Count != 0)
{
IVertex u = m_Q.Peek();
m_Q.Pop();
OnExamineVertex(u); // event
foreach(Edge e in g.OutEdges(u))
{
OnExamineEdge(e); // event
GraphColor vColor = Colors[e.Target];
if (vColor == GraphColor.White)
{
OnTreeEdge(e); // event
OnDiscoverVertex(v); // event
Colors[v]=GraphColor.Gray;
m_Q.Push(v);
}
else
{
OnNonTreeEdge(e);
if (vColor == GraphColor.Gray)
{
OnGrayTarget(e); // event
}
else
{
OnBlackTarget(e); //event
}
}
}
Colors[u]=GraphColor.Black;
OnFinishVertex(this, uArgs);
}
}This algorithm is directly inspired from the BoostGraphLibrary implementation.
