BFS / DFS Engineering Primer: k-hop Queries, Subgraph Extraction, and Path Existence ACERS Breakdown

graph = [
  [1,2],    # 0
  [3],      # 1
  [3,4],    # 2
  [5],      # 3
  [],       # 4
  []        # 5
]
s = 0, K = 2

output nodes: {0,1,2,3,4}

same graph as above
s = 0, t = 5

output: true

from collections import deque
from typing import List, Set


class SimpleBloom:
    """Demo Bloom filter: prefilter only, not a standalone correctness guarantee."""

    def __init__(self, m: int = 1 << 15):
        self.m = m
        self.bits = bytearray(m // 8 + 1)

    def _idx(self, x: int, salt: int) -> int:
        return hash((x, salt)) & (self.m - 1)

    def _set(self, i: int) -> None:
        self.bits[i >> 3] |= 1 << (i & 7)

    def _get(self, i: int) -> bool:
        return (self.bits[i >> 3] >> (i & 7)) & 1 == 1

    def add(self, x: int) -> None:
        for salt in (17, 31, 73):
            self._set(self._idx(x, salt))

    def maybe_contains(self, x: int) -> bool:
        return all(self._get(self._idx(x, salt)) for salt in (17, 31, 73))


def bfs_k_hop(graph: List[List[int]], s: int, k: int) -> Set[int]:
    n = len(graph)
    visited = bytearray(n)  # bitmap
    q = deque([(s, 0)])
    visited[s] = 1
    result = {s}

    while q:
        u, d = q.popleft()
        if d == k:
            continue
        for v in graph[u]:
            if not visited[v]:
                visited[v] = 1
                result.add(v)
                q.append((v, d + 1))

    return result


def dfs_path_exists(graph: List[List[int]], s: int, t: int) -> bool:
    n = len(graph)
    visited = bytearray(n)
    stack = [s]
    visited[s] = 1

    while stack:
        u = stack.pop()
        if u == t:  # early stop
            return True
        for v in graph[u]:
            if not visited[v]:
                visited[v] = 1
                stack.append(v)

    return False


def bfs_with_bloom_prefilter(graph: List[List[int]], s: int, limit: int = 100000) -> int:
    """Example: bloom reduces set lookups; exact set still guarantees correctness."""
    q = deque([s])
    exact = {s}
    bloom = SimpleBloom()
    bloom.add(s)
    visited_count = 0

    while q and visited_count < limit:
        u = q.popleft()
        visited_count += 1
        for v in graph[u]:
            # bloom says "not seen" => definitely unseen, enqueue directly
            if not bloom.maybe_contains(v):
                bloom.add(v)
                exact.add(v)
                q.append(v)
                continue
            # bloom says "maybe seen" => confirm with exact set
            if v not in exact:
                exact.add(v)
                q.append(v)

    return visited_count


if __name__ == "__main__":
    graph = [
        [1, 2],  # 0
        [3],     # 1
        [3, 4],  # 2
        [5],     # 3
        [],      # 4
        [],      # 5
    ]

    print("k-hop<=2:", sorted(bfs_k_hop(graph, 0, 2)))
    print("path 0->5:", dfs_path_exists(graph, 0, 5))
    print("bloom+exact visits:", bfs_with_bloom_prefilter(graph, 0, limit=100))

from collections import deque

def k_hop_nodes(graph, s, k):
    q = deque([(s, 0)])
    vis = {s}
    out = {s}
    while q:
        u, d = q.popleft()
        if d == k:
            continue
        for v in graph[u]:
            if v not in vis:
                vis.add(v)
                out.add(v)
                q.append((v, d + 1))
    return out

package main

import "fmt"

func pathExists(graph [][]int, s, t int) bool {
	vis := make([]bool, len(graph))
	stack := []int{s}
	vis[s] = true
	for len(stack) > 0 {
		u := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if u == t {
			return true
		}
		for _, v := range graph[u] {
			if !vis[v] {
				vis[v] = true
				stack = append(stack, v)
			}
		}
	}
	return false
}

func main() {
	g := [][]int{{1, 2}, {3}, {3, 4}, {5}, {}, {}}
	fmt.Println(pathExists(g, 0, 5)) // true
}

#include <bitset>
#include <iostream>
#include <unordered_set>

struct Bloom {
    static const int M = 1 << 16;
    std::bitset<M> bits;
    int h1(int x) const { return (x * 1315423911u) & (M - 1); }
    int h2(int x) const { return (x * 2654435761u) & (M - 1); }
    void add(int x) { bits.set(h1(x)); bits.set(h2(x)); }
    bool maybe(int x) const { return bits.test(h1(x)) && bits.test(h2(x)); }
};

int main() {
    Bloom b;
    std::unordered_set<int> exact;
    for (int x : {1, 2, 3}) { b.add(x); exact.insert(x); }
    int q = 4;
    if (!b.maybe(q) || exact.find(q) != exact.end()) {
        std::cout << "not visited yet\n";
    }
}

from collections import deque


def bfs_k_hop(graph, s, k):
    vis = [False] * len(graph)
    q = deque([(s, 0)])
    vis[s] = True
    out = {s}
    while q:
        u, d = q.popleft()
        if d == k:
            continue
        for v in graph[u]:
            if not vis[v]:
                vis[v] = True
                out.add(v)
                q.append((v, d + 1))
    return out


def dfs_path_exists(graph, s, t):
    vis = [False] * len(graph)
    st = [s]
    vis[s] = True
    while st:
        u = st.pop()
        if u == t:
            return True
        for v in graph[u]:
            if not vis[v]:
                vis[v] = True
                st.append(v)
    return False


if __name__ == "__main__":
    g = [[1, 2], [3], [3, 4], [5], [], []]
    print(sorted(bfs_k_hop(g, 0, 2)))
    print(dfs_path_exists(g, 0, 5))

#include <stdio.h>
#include <stdbool.h>

#define N 6

void bfs_k_hop(int g[N][N], int s, int k) {
    int q[128][2], head = 0, tail = 0;
    bool vis[N] = {0};
    vis[s] = true;
    q[tail][0] = s; q[tail][1] = 0; tail++;

    while (head < tail) {
        int u = q[head][0], d = q[head][1];
        head++;
        if (d == k) continue;
        for (int v = 0; v < N; ++v) {
            if (g[u][v] && !vis[v]) {
                vis[v] = true;
                q[tail][0] = v; q[tail][1] = d + 1; tail++;
            }
        }
    }

    for (int i = 0; i < N; ++i) if (vis[i]) printf("%d ", i);
    printf("\n");
}

bool dfs_path_exists(int g[N][N], int s, int t) {
    int st[128], top = 0;
    bool vis[N] = {0};
    st[top++] = s;
    vis[s] = true;

    while (top) {
        int u = st[--top];
        if (u == t) return true;
        for (int v = 0; v < N; ++v) {
            if (g[u][v] && !vis[v]) {
                vis[v] = true;
                st[top++] = v;
            }
        }
    }
    return false;
}

int main(void) {
    int g[N][N] = {0};
    g[0][1] = g[0][2] = 1;
    g[1][3] = 1;
    g[2][3] = g[2][4] = 1;
    g[3][5] = 1;

    bfs_k_hop(g, 0, 2);          // 0 1 2 3 4
    printf("%d\n", dfs_path_exists(g, 0, 5)); // 1
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> bfsKHop(const std::vector<std::vector<int>>& g, int s, int k) {
    std::vector<char> vis(g.size(), 0);
    std::queue<std::pair<int, int>> q;
    vis[s] = 1;
    q.push({s, 0});

    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();
        if (d == k) continue;
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push({v, d + 1});
            }
        }
    }

    std::vector<int> out;
    for (int i = 0; i < (int)g.size(); ++i) if (vis[i]) out.push_back(i);
    return out;
}

bool dfsPathExists(const std::vector<std::vector<int>>& g, int s, int t) {
    std::vector<char> vis(g.size(), 0);
    std::vector<int> st = {s};
    vis[s] = 1;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        if (u == t) return true;
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                st.push_back(v);
            }
        }
    }
    return false;
}

int main() {
    std::vector<std::vector<int>> g = {{1,2},{3},{3,4},{5},{},{}};
    auto nodes = bfsKHop(g, 0, 2);
    for (int x : nodes) std::cout << x << " ";
    std::cout << "\n" << dfsPathExists(g, 0, 5) << "\n";
}

package main

import "fmt"

func bfsKHop(graph [][]int, s, k int) []bool {
	vis := make([]bool, len(graph))
	type Node struct{ u, d int }
	q := []Node{{s, 0}}
	vis[s] = true
	for head := 0; head < len(q); head++ {
		cur := q[head]
		if cur.d == k {
			continue
		}
		for _, v := range graph[cur.u] {
			if !vis[v] {
				vis[v] = true
				q = append(q, Node{v, cur.d + 1})
			}
		}
	}
	return vis
}

func dfsPathExists(graph [][]int, s, t int) bool {
	vis := make([]bool, len(graph))
	stack := []int{s}
	vis[s] = true
	for len(stack) > 0 {
		u := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if u == t {
			return true
		}
		for _, v := range graph[u] {
			if !vis[v] {
				vis[v] = true
				stack = append(stack, v)
			}
		}
	}
	return false
}

func main() {
	g := [][]int{{1, 2}, {3}, {3, 4}, {5}, {}, {}}
	fmt.Println(bfsKHop(g, 0, 2))
	fmt.Println(dfsPathExists(g, 0, 5))
}

use std::collections::VecDeque;

fn bfs_k_hop(graph: &Vec<Vec<usize>>, s: usize, k: usize) -> Vec<bool> {
    let mut vis = vec![false; graph.len()];
    let mut q: VecDeque<(usize, usize)> = VecDeque::new();
    vis[s] = true;
    q.push_back((s, 0));

    while let Some((u, d)) = q.pop_front() {
        if d == k {
            continue;
        }
        for &v in &graph[u] {
            if !vis[v] {
                vis[v] = true;
                q.push_back((v, d + 1));
            }
        }
    }
    vis
}

fn dfs_path_exists(graph: &Vec<Vec<usize>>, s: usize, t: usize) -> bool {
    let mut vis = vec![false; graph.len()];
    let mut st = vec![s];
    vis[s] = true;

    while let Some(u) = st.pop() {
        if u == t {
            return true;
        }
        for &v in &graph[u] {
            if !vis[v] {
                vis[v] = true;
                st.push(v);
            }
        }
    }
    false
}

fn main() {
    let graph = vec![vec![1, 2], vec![3], vec![3, 4], vec![5], vec![], vec![]];
    println!("{:?}", bfs_k_hop(&graph, 0, 2));
    println!("{}", dfs_path_exists(&graph, 0, 5));
}

function bfsKHop(graph, s, k) {
  const vis = Array(graph.length).fill(false);
  const q = [[s, 0]];
  let head = 0;
  vis[s] = true;

  while (head < q.length) {
    const [u, d] = q[head++];
    if (d === k) continue;
    for (const v of graph[u]) {
      if (!vis[v]) {
        vis[v] = true;
        q.push([v, d + 1]);
      }
    }
  }
  return vis;
}

function dfsPathExists(graph, s, t) {
  const vis = Array(graph.length).fill(false);
  const st = [s];
  vis[s] = true;

  while (st.length) {
    const u = st.pop();
    if (u === t) return true;
    for (const v of graph[u]) {
      if (!vis[v]) {
        vis[v] = true;
        st.push(v);
      }
    }
  }
  return false;
}

const g = [[1, 2], [3], [3, 4], [5], [], []];
console.log(bfsKHop(g, 0, 2));
console.log(dfsPathExists(g, 0, 5));