Article Content
-
- Introduction – see above
- Breath-First Search
- Brief Note on Time Complexity
- Searching for a Vertex by Breath-First Search
- Conclusion
Breath-First Search
The Tree
A tree diagram to illustrate the Breath-First Search is as follows:
To look for a node, the algorithm starts with the root node 1 then to node 2, node 3, etc. Level by level, top to bottom, left to right, until it meets the node it is looking for.
Storing the Tree
A tree is like a simple graph. In this article, the tree is stored using an adjacency list. An adjacency list indicates a node (vertex) and all its adjacent nodes (vertices), as follows, in the previous diagram:
2 adjacent to 1, 5, 6
3 adjacent to 1
4 adjacent to 1, 7, 8
5 adjacent to 2, 9, 10
6 adjacent to 2
7 adjacent to 4, 11, 12
8 adjacent to 4
9 adjacent to 5
10 adjacent to 5
11 adjacent to 7
12 adjacent to 7
An Edge
An edge is the line joining a vertex and an adjacent vertex. It can also be considered as a pair, made up of a vertex (node) and an adjacent vertex (adjacent node). So, the previous tree has the following edges for the corresponding vertices:
3 edges: 2 adjacent to 1, 5, 6
1 edge: 3 adjacent to 1
3 edges: 4 adjacent to 1, 7, 8
3 edges: 5 adjacent to 2, 9, 10
1 edge: 6 adjacent to 2
3 edges: 7 adjacent to 4, 11, 12
1 edge: 8 adjacent to 4
1 edge: 9 adjacent to 5
1 edge: 10 adjacent to 5
1 edge: 11 adjacent to 7
C++ Structure
The previous information can be stored in a C++ vector of vectors. Each row begins with a node, followed by its adjacent nodes. The C++ vector-of-vectors, for the previous tree is as follows:
{2, 1, 5, 6},
{3, 1},
{4, 1, 7, 8},
{5, 2, 9, 10},
{6, 2},
{7, 4, 11, 12},
{8, 4},
{9, 5},
{10, 5},
{11, 7},
{12, 7} };
Brief Note on Time Complexity
Consider the following code:
for (int i=0; i<n; i++) {
cout << i << ", ";
}
The output is:
Assuming that the cout statement is a simple operation, the time complexity (speed) for this for-loop is said to be O(n), where n in this case is 10. The big O followed by brackets with n is the notation for time complexity (speed). Consider the following code:
for (int i=0; i<7; i++) {
cout << i << ", ";
}
The output is:
Though n is 10, not up to 10 elements are printed (7 elements have been printed). The time complexity is still said to be O(n). It is the maximum possible number of operations that is taken into consideration.
Consider the following code:
int m = 10;
for (int i=0; i<n; i++) {
cout << i << ", ";
}
cout << endl;
for (int i=0; i<m; i++) {
cout << i << ", ";
}
cout << endl;
The output is:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
There are two for-loops for 10 variables each, for n and m. The time complexity (speed) here is said to be: O(n + m). Even if the output is:
0, 1, 2, 3, 4, 5, 6
The time complexity is still given as O(n + m). It is the maximum possible number of operations that is taken into consideration. Also, if the output is:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
By convention, the time complexity is still given as O(n + m).
Searching for a Vertex by Breath-First Search
Wikipedia.org gives the algorithm as follows:
- Use a queue (First In First Out).
- Check whether a vertex has been explored before enqueueing the vertex.
It goes on to say that the time complexity is:
Where |V| is the number of vertices (nodes) and |E| is the number of edges.
If the structure for the tree is given as a vector-of-vectors, as in the previous case, there will be no need to use a queue. Just scan the vector-of-vectors, from top to bottom, until the vertex that is looked for is seen. This procedure still gives the same time complexity of O(|V| + |E|).
Assume that for the previous tree, the vertex 9 is to be searched for. From the edges/node table re-displayed in the following, for easy access, the number of edges is 19 and the number of nodes is 9:
3 edges: 2 adjacent to 1, 5, 6
1 edge: 3 adjacent to 1
3 edges: 4 adjacent to 1, 7, 8
3 edges: 5 adjacent to 2, 9, 10
1 edge: 6 adjacent to 2
3 edges: 7 adjacent to 4, 11, 12
1 edge: 8 adjacent to 4
1 edge: 9 adjacent to 5
1 edge: 10 adjacent to 5
1 edge: 11 adjacent to 7
The operations is 9 + 19 = 28. In this table, the edges are quoted on the left and the vertices are quoted on the right. Again, it is the maximum possible sum that is considered, that is: 11 + 21 = 32. It means that there are eleven vertices plus 21 edges, which is O(11 + 21), written in general terms as O(|V| + |E|).
The C++ code to search for the vertex 9 is:
for (unsigned i=0; i<vtr.size(); i++) {
for (unsigned j=0; j<vtr[i].size(); j++) {
counter = counter + 1;
}
if (vtr[i][0] == 9)
break;
}
cout << counter << endl;
The output is 28, with a maximum of 32.
Conclusion
The BFS Time complexity is:
O(|V| + |E|)
Where |V| is the number of vertices (nodes) and |E| is the number of edges.
