BFS (Breadth first search) on Graph
Algorithm
Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and then visit i.e. mark the vertex as visited and process all of v’s neighbors. Now that we’ve visited and processed all of v’s neighbors, we need to visit and process all of v’s neighbors neighbors Pseudocode
BFS(graph G, vertex s) \[all nodes initially unexplored\] \-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w).
[Read More]