Breadth-first Search

use a queue, can use a linked list also doesnt need to be recursive, just iterate

Uses FIFO Queue, DFS uses LIFO stack

Probably uses more memory than DFS because it stores more pointers, especially really wide trees


  • Fewest segments problems
  • if there is a path from one node to another, and what is the shortest path (shortest path problem.)
  • “find the shortest” problems

Checks first degree connections before moving on to check second degree

You need to make sure to mark nodes you already checked




nodes with one edge between them are neighbors

friends are first degree connections, their friends are second degree connections

you can implement a graph with a hashtable. key: your name, value: [friends]


can’t access random elements

FIFO, can only:

  • push/enqueue: add an item to the end
  • pop/dequeue: take an item off the



import java.util.*;

public class BreadthFirstSearch {
    private static Map<String, List<String>> graph = new HashMap<>();

    private static boolean search(String name) {
        Queue<String> searchQueue = new ArrayDeque<>(graph.get(name));
        // This list is how you keep track of which people you've searched before.
        List<String> searched = new ArrayList<>();

        while (!searchQueue.isEmpty()) {
            String person = searchQueue.poll();
            // Only search this person if you haven't already searched them
            if (!searched.contains(person)) {
                if (person_is_seller(person)) {
                    System.out.println(person + " is a mango seller!");
                } else {
                    // Marks this person as searched

        return false;

    private static boolean person_is_seller(String name) {
        return name.endsWith("m");

    public static void main(String[] args) {
        graph.put("you", Arrays.asList("alice", "bob", "claire"));
        graph.put("bob", Arrays.asList("anuj", "peggy"));
        graph.put("alice", Arrays.asList("peggy"));
        graph.put("claire", Arrays.asList("thom", "jonny"));
        graph.put("anuj", Collections.emptyList());
        graph.put("peggy", Collections.emptyList());
        graph.put("thom", Collections.emptyList());
        graph.put("jonny", Collections.emptyList());



from collections import deque

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    # This array is how you keep track of which people you've searched before.
    searched = []
    while search_queue:
        person = search_queue.popleft()
        # Only search this person if you haven't already searched them.
        if not person in searched:
            if person[-1] == 'm':
                print(person + " is a mango seller!")
                return True
                search_queue += graph[person]
                # Marks this person as searched
    return False



grids you can do 2 dimensional array, graph you can do a array of lists or hash table of lists with connected node list as value.

This method shows a strategy to check around a location in a 2D array for locations with true in them.

boolean[][] mineSweeperMap = new boolean[5][5];

boolean checkNeighbors(int x, int y) {
    int[] dx = {0,1,0,-1};
    int[] dy = {-1,0,1,0};
    //int[] dx = {0,1,0,-1,-1,-1,1,1}; // for corners
    //int[] dy = {-1,0,1,0,-1,1,-1,1}; // for corners

    for (int i; i<4; i++;) { //8 for corners
        neighbor_x = x + dx[i];
        neighbor_y = y + dy[i];
        if(mineSweeperMap[neighbor_x][neighbor_y]) {
            return true;
    return false;

// make 2 2d arrays to keep track of where you are and where the x's are