How to Trace the Path in a Breadth-First Search

How to trace the path in a Breadth-First Search?

You should have look at http://en.wikipedia.org/wiki/Breadth-first_search first.

---

Below is a quick implementation, in which I used a list of list to represent the queue of paths.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a 
        # new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

This prints: ['1', '4', '7', '11']

---

Another approach would be maintaining a mapping from each node to its parent, and when inspecting the adjacent node, record its parent. When the search is done, simply backtrace according the parent mapping.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path
        

def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

The above codes are based on the assumption that there's no cycles.

Finding path to node using Breadth First Search

You can do a standard BFS using a queue, but add the path to that node as part of the state in the queue.

from collections import deque

class Node: 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None

def path_from_to(root, target):
    queue = deque([(root, [root.data])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        if node.left:
            queue.append((node.left, path + [node.left.data]))
        if node.right:
            queue.append((node.right, path + [node.right.data]))

if __name__ == "__main__":
    root = Node('A')
    root.left = Node('B') 
    root.left.left = Node('D')
    root.left.right = Node('E')
    root.left.left.left = Node('G')
    root.left.left.right = Node('H') 
    root.left.right.right = Node('K')
    root.left.right.left = Node('I')
    target = Node('K')
    root.left.right.left.left = target
    print(path_from_to(root, target))

Output:

['A', 'B', 'E', 'I', 'K']

Since it's a tree, we don't need to keep a list of previously visited nodes.

Note that DFS is usually a bit better suited for searching in trees.

How to keep track of path in BFS Graph search JavaScript

You need to store the path for each visited node as well.

const graph = { 1: [2, 3, 4], 2: [5, 6], 3: [10], 4: [7, 8], 5: [9, 10], 7: [11, 12], 11: [13] };

function bfs(graph, start, end) {
    let queue = [[start, []]],
        seen = new Set;

    while (queue.length) {
        let [curVert, [...path]] = queue.shift();
        path.push(curVert);
        if (curVert === end) return path;

        if (!seen.has(curVert) && graph[curVert]) {
            queue.push(...graph[curVert].map(v => [v, path]));
        }
        seen.add(curVert);
    }
}

console.log(bfs(graph, 1, 13));

How does a Breadth-First Search work when looking for Shortest Path?

Technically, Breadth-first search (BFS) by itself does not let you find the shortest path, simply because BFS is not looking for a shortest path: BFS describes a strategy for searching a graph, but it does not say that you must search for anything in particular.

Dijkstra's algorithm adapts BFS to let you find single-source shortest paths.

In order to retrieve the shortest path from the origin to a node, you need to maintain two items for each node in the graph: its current shortest distance, and the preceding node in the shortest path. Initially all distances are set to infinity, and all predecessors are set to empty. In your example, you set A's distance to zero, and then proceed with the BFS. On each step you check if you can improve the distance of a descendant, i.e. the distance from the origin to the predecessor plus the length of the edge that you are exploring is less than the current best distance for the node in question. If you can improve the distance, set the new shortest path, and remember the predecessor through which that path has been acquired. When the BFS queue is empty, pick a node (in your example, it's E) and traverse its predecessors back to the origin. This would give you the shortest path.

If this sounds a bit confusing, wikipedia has a nice pseudocode section on the topic.

Returning shortest path using breadth-first search

You can make searched a dictionary instead of a set, and then let the value for each key be a backreference to the node where you came from.

When you find the target, you can recover the path by walking back over those backreferences and then return the reverse of that.

Adapted code:

def search(name):
  search_queue = deque()
  search_queue.append((name, None))
  searched = {}  # dict instead of set

  while search_queue:
    # print(search_queue)
    person, prev = search_queue.popleft()
    if person not in searched:
      searched[person] = prev
      # print(f'Searching {person}')
      if person_is_seller(person):
        result = []
        while person is not None:
            result.append(person)
            person = searched[person]
        return result[::-1]
      else:
        search_queue += [(neighbor, person) for neighbor in graph[person]]
  return []

Now the function returns a list. It will have the start and end node when a path is found, so in this case:

['you', 'claire', 'thom']

If no path is found, the result is an empty list.

How to get the path between 2 nodes using Breadth-First Search?

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

BFS algorithm, tracking the path

First off, I started with a little bit of code cleanup to make it a bit more concise and made a rust playground to experiment with. There are two main approaches to solving this problem. Either you keep track of the path taken in the queue or the visited nodes. The easiest approach for you would likely be to simply adapt your code to have the visited nodes array point to the previous node in the path from each visited node. playground link

fn bfs(arr: [[i32; 10]; 10], target: i32) -> Option<Vec<(i32, i32)>> {
    let mut visited = [[None; 10]; 10];
    let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
    queue.push_back((0, 0));

    // Put some filler into the first location
    visited[0][0] = Some((0, 0));
    
    while let Some((y, x)) = queue.pop_front() {
    
        // Prind debug info
        println!("\nExpanding ({}, {})", x, y);
        for y in 0..visited.len() {
            for x in 0..visited.len() {
                if arr[y][x] == target && visited[y][x].is_some() {
                    print!("X ");
                } else if visited[y][x].is_some() {
                    print!("0 ");
                } else if arr[y][x] == 3 {
                    print!("# ");
                } else {
                    print!(". ");
                }
            }
            println!();
        }

        // Check if this position is the target
        if arr[y as usize][x as usize] == target {
            let mut path_taken = Vec::new();
            path_taken.push((y, x));
            
            let mut prev_x = x;
            let mut prev_y = y;
            while prev_x != 0 || prev_y != 0 {
                let (py, px) = visited[prev_y as usize][prev_x as usize].unwrap();
                path_taken.push((py, px));
                prev_y = py;
                prev_x = px;
            }
            
        
            return Some(path_taken.into_iter().rev().collect())
        }

        // Iterate over adjacent offsets
        for (dx, dy) in &[(1, 0), (0, 1), (-1, 0), (0, -1)] {
            // Check if offset is within bounds
            if x + dx < 0
                || y + dy < 0
                || (y + dy) as usize >= arr.len()
                || (x + dx) as usize >= arr[(y + dy) as usize].len()
            {
                continue;
            }

            // Check if offset points to valid location
            if arr[(y + dy) as usize][(x + dx) as usize] == 3 {
                continue;
            }
            
            if visited[(y + dy) as usize][(x + dx) as usize].is_some() {
                continue;
            } 

            visited[(y + dy) as usize][(x + dx) as usize] = Some((y, x));
            queue.push_back((y + dy, x + dx));
        }
    }
    None
}

However, I personally prefer the approach of keeping track of the path taken in the queue to reduce the memory requirement for small paths. While it is not as true to your original question, my favorite version of this would be to write BFS in a way that better represents how it described mathematically using type parameters. playground link

fn bfs<N, F, R>(start: N, end: N, expand: F) -> Option<SearchPath<N>>
    where N: Copy + Eq + Hash,
          F: Fn(N) -> R,
          R: IntoIterator<Item=N> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    queue.push_back(SearchPath(start, None));
    visited.insert(start);
    
    while let Some(SearchPath(node, path)) = queue.pop_front() {
        if node == end {
            return Some(SearchPath(node, path))
        }
        
        let path = Rc::new(SearchPath(node, path.clone()));
        
        for edge in expand(node) {
            if !visited.contains(&edge) {
                visited.insert(edge);
                queue.push_back(SearchPath(edge, Some(path.clone())));
            }
        }
    }
    
    None
}

#[derive(Clone, PartialEq, Eq)]
pub struct SearchPath<N> (N, Option<Rc<SearchPath<N>>>);

impl<N: Debug> Debug for SearchPath<N> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match &self.1 {
            Some(v) => write!(f, "{:?} -> {:?}", v, &self.0),
            None => write!(f, "{:?}", &self.0)
        }
    }
}

Going further down the rabbit hole, we can do even more with this if we add some more type parameters. It may be a bit harder to read now, but what this lets us do is implement a bunch of different search approaches from graph theory using search as a base. Essentially, this new function search boils down the the core components of many search methods.

/// A general purpose graph search.
///  - start: Initial value to use in search queue
///  - expand: A function that takes a path, expands the edges of the top node,
///       then places the next elements in the queue according to the current search
///       approach. Additional ordering constraints may also be applied.
///  - next_node: A helper function which takes a path and evaluates if the search goal
///       has been reached. If the goal has been reached, None is returned and the current
///       path is returned. Otherwise, the top node in the given path is returned so
///       that it can be expanded.
fn search<N, P, F, R>(start: P, expand: F, next_node: R) -> Option<P>
where
    N: Eq + Hash,
    F: Fn(&P, &mut VecDeque<P>),
    R: Fn(&P) -> Option<N>,
{
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    queue.push_back(start);
    while let Some(path) = queue.pop_front() {
        let node = match next_node(&path) {
            Some(v) => v,
            None => return Some(path),
        };

        if visited.contains(&node) {
            continue;
        }
        visited.insert(node);

        expand(&path, &mut queue);
    }
    None
}

#[derive(Clone, PartialEq, Eq)]
pub struct WeightedSearchPath<N>(i32, N, Option<Rc<SearchPath<N>>>);

/// An example using search to find the most efficient path with weighted graph edges 
fn weighted_search<N, F, R>(start: N, end: N, expand: F) -> Option<WeightedSearchPath<N>>
where
    N: Copy + Eq + Hash,
    F: Fn(N) -> R,
    R: IntoIterator<Item=(i32, N)>,
{
    search(
        WeightedSearchPath(0, start, None),
        |WeightedSearchPath(cost, node, path), queue| {
            let path = Rc::new(SearchPath(*node, path.clone()));
            for (weight, edge) in expand(*node) {
                queue.push_back(WeightedSearchPath(cost + weight, edge, Some(path.clone())));
            }
            
            queue.make_contiguous().sort_by_key(|x| x.0);
        },
        |WeightedSearchPath(_, node, _)| {
            if *node == end {
                return None;
            }
            Some(*node)
        },
    )
}

---

Related Topics