Breadth-First Search: Difference between revisions

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

@@ Line 26: / Line 26: @@
 #include <vector>
 #include <queue>
-#include <set>
 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() {
-  // 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;
 }
@@ Line 109: / Line 81: @@
      [[USACO_2019_December_Gold_P2|2019 December Gold Problem 2: Cow Land]]
      [[USACO_2020_January_Gold_P2|2020 January Gold Problem 2: Milk Visits]]
+[[Category:Breadth-First Search]]
+[[Category:Algorithms]]
+[[Category:Graph]]