Breadth-First Search: Difference between revisions

Jump to navigation Jump to search

Breadth-First Search (edit)

Revision as of 04:03, 6 May 2023

469 bytes removed ,  6 May 2023
→‎Example C++ code
Line 26: 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
  g.addEdge(0, 1);
  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
    // Perform BFS from the first node
  g.BFS(0);
    bfs(0);


  return 0;
    return 0;
}
}


Retrieved from "https://wiki.usaco.fun/index.php/Special:MobileDiff/474"

Navigation menu