If a node is enqueued multiple times during a BFS traversal without checking whether it has already been visited, the algorithm can produce incorrect results and suffer from performance issues. The most immediate problem is redundant processing—the same node may be added to the queue several times, leading to duplicate visits and wasted computations. This can cause incorrect traversal orders and interfere with BFS’s guarantee of finding the shortest path, as the algorithm might reach a node through a longer route if it was already visited through a shorter one but re-enqueued. In cyclic graphs, this lack of a visited check can even result in infinite loops, where the algorithm continuously revisits nodes in a cycle. The memory usage will also increase unnecessarily, as the queue fills with repeated entries. A proper implementation marks nodes as visited before enqueuing them, not after, to avoid all these issues and ensure optimal performance and correctness.

Yes, BFS can be used on graphs that are not connected, but it will only traverse the connected component of the graph that includes the starting node. In a disconnected graph, there are one or more groups of nodes with no paths between them. If BFS is started from a node in one group, it will visit all nodes reachable from that node but will not reach any nodes in the other disconnected groups. To ensure that all nodes in a disconnected graph are visited, BFS must be run multiple times, once from each unvisited node. This technique is particularly useful when trying to identify or process connected components of a graph. For example, in undirected graphs, this approach can be used to count how many separate sections or clusters the graph contains. In directed graphs, it can help detect isolated subgraphs or strongly connected components, especially when combined with additional logic or traversal methods.

In theory, it is possible to implement BFS without explicitly using a queue, but doing so would require replicating the behaviour of a queue using some other structure or technique. The defining feature of BFS is its level-order traversal, which is only guaranteed if nodes are processed in the order they are discovered. This is naturally achieved with a First-In, First-Out (FIFO) queue. Without a queue, one would need to simulate FIFO behaviour manually—perhaps using a list or two stacks in a coordinated way. However, these alternatives often lead to more complex and less efficient code. If a stack is used without modification (as in depth-first search), the algorithm will no longer be BFS. Recursion, which is often used in depth-first search, is also unsuitable for BFS, as it does not preserve the correct processing order. Therefore, while technically possible to avoid a queue, doing so undermines the core logic of BFS and is not practical.

Breadth-first search is not designed to handle weighted edges correctly. It assumes that all edges have the same cost or weight, effectively treating the graph as unweighted. When BFS is used on a weighted graph, it does not consider the weights of the edges during traversal. It still visits nodes based on their distance from the starting point in terms of the number of edges, not the actual cost or total weight of the path. As a result, it may fail to find the truly shortest or least costly path if edge weights vary. For example, if one route has three low-weight edges and another has two high-weight edges, BFS will choose the two-edge path even though it's more expensive. To find the shortest path in a weighted graph, algorithms such as Dijkstra’s algorithm or A search* are required, as they take edge weights into account and prioritise lower-cost paths.

For very large graphs, BFS can become resource-intensive in terms of both memory and time. To optimise BFS in these situations, several strategies can be applied. First, use a more efficient graph representation, such as an adjacency list rather than an adjacency matrix, to save space. Second, ensure that the visited set is implemented using a hash set or Boolean array to allow constant-time lookups. Third, implement an early termination condition if you are searching for a particular node or condition—once the target is found, you can stop the search immediately, reducing traversal time. For graphs that are extremely large or distributed, parallel BFS can be used, where different processors handle different parts of the graph concurrently. Finally, bidirectional BFS can be used for pathfinding problems by performing BFS from both the source and the target simultaneously, meeting in the middle, which significantly reduces the search space from O(n) to O(sqrt(n)) in many cases.