SHARE
TWEET

Breadth-first Traversal with a Queue

a guest May 7th, 2017 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. /* The graphs used in the post's diagrams
  7.    have node indexing which starts at 1.
  8.    Since arrays and vectors in C++ use
  9.    0-based indexing, we subtract 1 from the
  10.    indices used in the input, and add 1
  11.    to the indices printed in the output. */
  12.  
  13. /* This graph can support 10000 nodes
  14.    numbered from 1 to 10000 inclusive. */
  15. bool visited[10000] = {false};
  16.  
  17. /* Each vector of integers represents
  18.    an individual node and the nodes it
  19.    is connected with. */
  20. vector< vector<int> > adjList;
  21.  
  22. int main () {
  23.     /* Take the number of nodes in the graph
  24.        and the number of edges in the graph as input. */
  25.     int nodeCount, edgeCount;
  26.     cin >> nodeCount >> edgeCount;
  27.  
  28.     /* Fill the adjacency list with unconnected nodes. */
  29.     for (int i = 0; i < nodeCount; i++) {
  30.         vector<int> node;
  31.         adjList.push_back (node);
  32.     }
  33.  
  34.     /* Add undirected edges to the adjacency list
  35.        using the input as a guide. */
  36.     for (int i = 0; i < edgeCount; i++) {
  37.         int n1, n2;
  38.         cin >> n1 >> n2;
  39.         n1--;
  40.         n2--;
  41.         adjList[n1].push_back (n2);
  42.         adjList[n2].push_back (n1);
  43.     }
  44.  
  45.     /* Take the index of the starting node. */
  46.     int startIndex;
  47.     cin >> startIndex;
  48.     startIndex--;
  49.  
  50.     /* First, push the index of the starting node
  51.        onto the traversal queue - this structure
  52.        holds the indices of the nodes which we
  53.        will go on to visit. */
  54.     queue<int> bfsQueue;
  55.     bfsQueue.push(startIndex);
  56.     while (!bfsQueue.empty()) {
  57.         /* Take the index of the node that is first
  58.            in the queue - this is the value which
  59.            has been in the queue the longest (that is,
  60.            the value at the 'front' of the queue). */
  61.         int index = bfsQueue.front();
  62.         bfsQueue.pop();
  63.         visited[index] = true;
  64.         cout << index+1 << "\n";
  65.  
  66.         for (int i = 0; i < adjList[index].size(); i++) {
  67.             if (!visited[adjList[index][i]]) {
  68.                 bfsQueue.push(adjList[index][i]);
  69.             }
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
RAW Paste Data
Top