Breadth-First Search: Difference between revisions

From Wiki
Jump to navigation Jump to search
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
= Breadth-First Search (BFS) =
== Breadth-First Search ==


Breadth-First Search (BFS) is an algorithm for searching a tree or graph data structure for a node that meets a set of criteria. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. <ref name=“geeksforgeeks”>https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/</ref>
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward (layer-by-layer) motion. BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph.


== How it works ==
== Algorithm ==


BFS uses a queue data structure to keep track of the nodes to be visited. It also uses an array or a set to mark the nodes that have been visited, to avoid revisiting them.
    Start at the source node and mark it as visited.
    Enqueue the source node into a queue.
    While the queue is not empty:
    a. Dequeue the front node from the queue.
    b. Process the dequeued node (e.g., print its value).
    c. For each adjacent node of the dequeued node, if it is not visited, mark it as visited and enqueue it.


The algorithm works as follows:
Choose a starting node, mark it as visited, and add it to the queue.
While the queue is not empty:
Dequeue a node from the queue and process it (e.g., print its value).
Enqueue all its adjacent nodes that have not been visited and mark them as visited.
Repeat step 2 until the queue is empty.
== Complexity ==
== Complexity ==


Line 28: Line 26:
#include <vector>
#include <vector>
#include <queue>
#include <queue>
#include <set>
 
using namespace std;
using namespace std;


// A simple graph class
vector<vector<int>> adjList;
class Graph {
vector<bool> visited;
  int V; // number of vertices
  vector<int> *adj; // adjacency list
public:
  // constructor
  Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
  }


  // add an edge from u to v
void bfs(int startNode) {
  void addEdge(int u, int v) {
     queue<int> q;
     adj[u].push_back(v);
  }


  // BFS starting from s
     visited[startNode] = true;
  void BFS(int s) {
     q.push(startNode);
     queue<int> q; // queue for BFS
     set<int> visited; // set for marking visited nodes


     // mark s as visited and enqueue it
     while (!q.empty()) {
    visited.insert(s);
        int currentNode = q.front();
    q.push(s);
        q.pop();


    while (!q.empty()) {
        cout << "Visiting node: " << currentNode << endl;
      // dequeue a node and print it
      int v = q.front();
      q.pop();
      cout << v << " ";


      // enqueue all adjacent nodes that are not visited
        for (int adjacent : adjList[currentNode]) {
      for (int u : adj[v]) {
            if (!visited[adjacent]) {
        if (visited.find(u) == visited.end()) {
                visited[adjacent] = true;
          visited.insert(u);
                q.push(adjacent);
          q.push(u);
            }
         }
         }
      }
     }
     }
    cout << endl;
}
  }
};


// driver code
int main() {
int main() {
  // create a graph with 6 vertices
    // Initialize adjacency list and visited vector
  Graph g(6);
    adjList = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    visited.resize(4, false);


  // add some edges
    // Perform BFS from the first node
  g.addEdge(0, 1);
    bfs(0);
  g.addEdge(0, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(3, 5);
  g.addEdge(4, 5);


  // BFS starting from node 0
    return 0;
  g.BFS(0);
 
  return 0;
}
}


</pre>
</pre>


== USACO problems for BFS ==
=== Example USACO Silver Problems ===
 
Here are some example USACO Silver problems that utilize Breadth-First Search:
 
    [[USACO_2017_January_Silver_P3|2017 January Silver Problem 3: Cow Navigation]]
    [[USACO_2018_December_Silver_P2|2018 December Silver Problem 2: Mooyo Mooyo]]
    [[USACO_2020_February_Silver_P1|2020 February Silver Problem 1: Triangles]]
 
=== Example USACO Gold Problems ===
 
Here are some example USACO Gold problems that utilize Breadth-First Search:
 
    [[USACO_2015_December_Gold_P1|2015 December Gold Problem 1: Moocast]]
    [[USACO_2019_December_Gold_P2|2019 December Gold Problem 2: Cow Land]]
    [[USACO_2020_January_Gold_P2|2020 January Gold Problem 2: Milk Visits]]


Here are some USACO problems that can be solved using BFS:


- [[http://www.usaco.org/index.php?page=viewproblem2&cpid=713|Cow Navigation]]
[[Category:Breadth-First Search]]
- [[http://www.usaco.org/index.php?page=viewproblem2&cpid=615|Milk Pails]]
[[Category:Algorithms]]
- [[http://www.usaco.org/index.php?page=viewproblem2&cpid=788|MooTube]]
[[Category:Graph]]
- [[http://www.usaco.org/index.php?page=viewproblem2&cpid=668|Moocast]]
- [[http://www.usaco.org/index.php?page=viewproblem2&cpid=856|The Bucket List]]

Latest revision as of 05:05, 6 May 2023

Breadth-First Search[edit]

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward (layer-by-layer) motion. BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph.

Algorithm[edit]

   Start at the source node and mark it as visited.
   Enqueue the source node into a queue.
   While the queue is not empty:
   a. Dequeue the front node from the queue.
   b. Process the dequeued node (e.g., print its value).
   c. For each adjacent node of the dequeued node, if it is not visited, mark it as visited and enqueue it.

Complexity[edit]

The time complexity of BFS is O(|V| + |E|), where |V| is the number of nodes and |E| is the number of edges in the graph. This is because every node and every edge will be explored in the worst case.

The space complexity of BFS is O(|V|), where |V| is the number of nodes in the graph. This is because the queue can hold up to |V| nodes in the worst case.

Example C++ code[edit]

Here is an example of implementing BFS in C++ using STL containers: 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> adjList;
vector<bool> visited;

void bfs(int startNode) {
    queue<int> q;

    visited[startNode] = true;
    q.push(startNode);

    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();

        cout << "Visiting node: " << currentNode << endl;

        for (int adjacent : adjList[currentNode]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                q.push(adjacent);
            }
        }
    }
}

int main() {
    // Initialize adjacency list and visited vector
    adjList = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    visited.resize(4, false);

    // Perform BFS from the first node
    bfs(0);

    return 0;
}

Example USACO Silver Problems[edit]

Here are some example USACO Silver problems that utilize Breadth-First Search: 

   2017 January Silver Problem 3: Cow Navigation
   2018 December Silver Problem 2: Mooyo Mooyo
   2020 February Silver Problem 1: Triangles

Example USACO Gold Problems[edit]

Here are some example USACO Gold problems that utilize Breadth-First Search: 

   2015 December Gold Problem 1: Moocast
   2019 December Gold Problem 2: Cow Land
   2020 January Gold Problem 2: Milk Visits
Retrieved from "https://wiki.usaco.fun/index.php?title=Breadth-First_Search&oldid=480"