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

Solves:

  • 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

Complexity

O(vertices+edges)

Graphs

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]

Queues

can’t access random elements

FIFO, can only:

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

Example

Java

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 {
                    searchQueue.addAll(graph.get(person));
                    // Marks this person as searched
                    searched.add(person);
                }
            }
        }

        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());

        search("you");
    }
}

Python

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
            else:
                search_queue += graph[person]
                # Marks this person as searched
                searched.append(person)
    return False

search("you")

Grid

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
    is_x[row][col];
    is_first_sgfg[row][col];