Author: Gihyun Kim
Data: October 15th, 2023
Topic: BFS Algorithm and its use
What is BFS?
BFS, Breadth First Search, is a searching algorithm that (like DFS) is commonly used to traverse a tree or other data structures such as arrays, arraylists (in java), vectors, or even hashsets. A BFS algorithm starts from a single node and goes over other branches of the node in an ordered fashion and most importantly, uses a queue and/or an array/arraylist to not return to a node that has already been checked. For example, in an array where all the values have been set to 0, if one node has been visited, the algorithm would put a 1 or a value that indicates that the node has been visited and thus should not be visited later.
The main idea behind this searching algorithm is to explore all neighboring nodes before moving onto the next level.
Benefits:
Here are some benefits of the BFS algorithm:
Finding Shortest Paths: Because BFS explores all nodes of the level it is currently in before moving onto the next one, it ensures that it finds the shortest route from the starting point to the endpoint.
Efficiency: BFS tends to be more efficient, especially in scenarios such as finding shortest paths, and finding connectivity (whether a node is reachable from a certain point.
Finding Neighbors: As BFS goes through all the nodes at a certain level, before moving onto the next one, it is very efficient in scenarios where one must find the neighbors of a certain node or a certain distance away from the node.
Uses:
Below is a proglem that I have solved using the BFS algorithm. The question is as follows:
Question:
There is a grid-type road network consisting of m vertical lines and n horizontal lines on a two-dimensional plane.
The figure below is an example of a road network consisting of 7 vertical lines and 6 horizontal lines.
Among the intersection points where the vertical and horizontal lines meet, the position of the lower left point is (1,1), and the coordinates of the upper rightmost point are (m,n).
There are k buses operating on this road network, and each bus travels back and forth on a line segment between two intersections on a horizontal line or a line segment between two intersections on a vertical line.
Each bus stops at every intersection between the segments it travels on (including intersections at either end of the segments).
When an origin intersection and a destination intersection are given (the origin and destination are different), we try to go from the origin to the destination only by bus.
Write a program to find the minimum number of buses used.
For example, let’s say 8 buses are running as follows.
Bus 1: (2, 1) – (2, 2)
Bus 2: (1, 1) – (5, 1)
Bus 3: (3, 2) – (6, 2)
Bus 4: (5, 6) – (5, 1)
Bus 5: (1, 5) – (7, 5)
Bus 6: (7, 3) – (7, 6)
Bus 7: (2, 1) – (2, 6)
Bus 8: (3, 5) – (6, 5)
Let’s say the starting point is (2, 1) and the destination is (7, 4).
One way, first take bus 2 and get off at intersection (5, 1), then take bus 4 and get off at (5, 5), then take bus 5 and get off at (7, 5), and finally Take the number 6 bus and get off at the destination (7, 4).
Then the number of buses used is 4.
Alternatively, take bus number 7 and get off at (2, 5), then take bus number 5 and get off at (7, 5), and finally take bus number 6 and get off at your destination (7, 4).
Then the number of buses used is 3, which is the minimum.
Input
In the first line, the number m of vertical lines and the number n of horizontal lines are given with spaces between them (1 ≤ m,n ≤ 100,000).
The number of buses (1≤k≤5,000) is given in the second line.
From the third line to the k lines, five numbers b, x1, y1, x2, y2 representing the operating section of the bus are given with blanks in between.
Here, b(1≤b≤k) represents the number of the bus, and (x1,y1) and (x2,y2) represent the coordinates of the intersections at both ends of the bus.
In the last line, four numbers sx, sy, dx, and dy representing the coordinates of the starting point and destination are given with spaces between them.
Where (sx,sy) is the coordinates of the starting point and (dx,dy) is the coordinates of the destination. 1≤x1, x2, sx, dx≤m, and 1≤y1, y2, sy, dy≤n.
For every input, the origin and destination are given differently, and there is more than one way to get from the origin to the destination.
Print
Print the minimum number of buses used in the first line.
My Code:
This is the code that I used to approach and solve this problem (written in C++).
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Bus {
int idx;
bool isHorizon;
pair<int, int> startPos, endPos;
}bus[5001];
int row, column, numBus, startr, startc, destr, destc;
vector< vector<int> > adj;
int BFS() {
vector<int> visited(numBus+1, -1);
vector<bool> isDest(numBus, false);
queue<int> que;
for (int i = 1; i <= numBus; i++) {
if (bus[i].isHorizon) {
if (bus[i].startPos.first != startr || bus[i].startPos.second > startc || startc > bus[i].endPos.second) continue;
}
else {
if (bus[i].startPos.second != startc || bus[i].startPos.first > startr || startr > bus[i].endPos.first) continue;
}
que.push(bus[i].idx);
visited[bus[i].idx] = 1;
}
for (int i = 1; i <= numBus; i++) {
if (bus[i].isHorizon) {
if (bus[i].startPos.first == destr && bus[i].startPos.second <= destc && destc <= bus[i].endPos.second) isDest[bus[i].idx] = true;
}
else {
if (bus[i].startPos.second == destc && bus[i].startPos.first <= destr && destr <= bus[i].endPos.first) isDest[bus[i].idx] = true;
}
}
int busIdx, transferNum, minTransfer = 0;
while (!que.empty()) {
busIdx = que.front();
que.pop();
transferNum = visited[busIdx];
if (isDest[busIdx]) {
minTransfer = transferNum;
break;
}
int nextBus;
for (int i = 0; i < adj[busIdx].size(); i++) {
nextBus = adj[busIdx][i];
if (visited[nextBus] == -1) {
que.push(nextBus);
visited[nextBus] = transferNum+1;
}
}
}
return minTransfer;
}
int main() {
cin >> row >> column >> numBus;
adj = vector< vector<int> > (numBus+1);
int busIndex, r1, c1, r2, c2;
for (int i = 1; i <= numBus; i++) {
cin >> busIndex >> c1 >> r1 >> c2 >> r2;
bus[i].idx = busIndex;
if (r1 == r2) bus[i].isHorizon = true;
else bus[i].isHorizon = false;
if (r1 > r2 || c1 > c2) {
bus[i].startPos = make_pair(r2, c2);
bus[i].endPos = make_pair(r1, c1);
}
else {
bus[i].startPos = make_pair(r1, c1);
bus[i].endPos = make_pair(r2, c2);
}
Bus& nowBus = bus[i], compBus;
for (int j = 1; j < i; j++) {
compBus = bus[j];
if (compBus.isHorizon == nowBus.isHorizon) {
if (nowBus.isHorizon) {
if (nowBus.startPos.first != compBus.startPos.first || compBus.endPos.second < nowBus.startPos.second || nowBus.endPos.second < compBus.startPos.second) continue;
}
else {
if (nowBus.startPos.second != compBus.startPos.second || compBus.endPos.first < nowBus.startPos.first || nowBus.endPos.first < compBus.startPos.first) continue;
}
}
else {
if (nowBus.isHorizon) {
if ((nowBus.startPos.first < compBus.startPos.first || compBus.endPos.first < nowBus.startPos.first) || (compBus.startPos.second < nowBus.startPos.second || nowBus.endPos.second < compBus.startPos.second)) continue;
}
else {
if ((compBus.startPos.first < nowBus.startPos.first || nowBus.endPos.first < compBus.startPos.first) ||(nowBus.startPos.second < compBus.startPos.second || compBus.endPos.second < nowBus.startPos.second)) continue;
}
}
adj[nowBus.idx].push_back(compBus.idx);
adj[compBus.idx].push_back(nowBus.idx);
}
}
cin >> startc >> startr >> destc >> destr;
cout << BFS() << endl;
return 0;
}
Gihyun Kim 
Leave a comment