k-hop 与可达性查询：BFS 限制、Reachability 索引与 2-hop Labeling ACERS 解析

graph = [
  [1,2],   # 0
  [3],     # 1
  [3,4],   # 2
  [5],     # 3
  [],      # 4
  []       # 5
]
query: k_hop(0, 2)
result: {0,1,2,3,4}

query: reachable(0, 5)
result: true
query: reachable(4, 5)
result: false

0 -> 1 -> 3
 \\        ^
  -> 2 ----|

L_out(0) ∩ L_in(3) = {1,2,3} ∩ {0,1,2} = {1,2} != ∅

from collections import deque
from typing import List, Set


def bfs_k_hop(graph: List[List[int]], s: int, k: int) -> Set[int]:
    vis = bytearray(len(graph))
    vis[s] = 1
    q = deque([(s, 0)])
    out = {s}

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

    return out


def reachable_bfs(graph: List[List[int]], s: int, t: int, hop_limit: int | None = None) -> bool:
    vis = bytearray(len(graph))
    vis[s] = 1
    q = deque([(s, 0)])

    while q:
        u, d = q.popleft()
        if u == t:
            return True
        if hop_limit is not None and d == hop_limit:
            continue
        for v in graph[u]:
            if not vis[v]:
                vis[v] = 1
                q.append((v, d + 1))

    return False


def transitive_closure_small(graph: List[List[int]]) -> List[int]:
    """小图演示：每个节点一行 bitset（Python int）。"""
    n = len(graph)
    rows = [0] * n
    for u in range(n):
        rows[u] |= 1 << u
        for v in graph[u]:
            rows[u] |= 1 << v

    # Warshall-bitset: if u reaches k, then u also reaches all nodes that k reaches
    for k in range(n):
        mk = 1 << k
        rk = rows[k]
        for u in range(n):
            if rows[u] & mk:
                rows[u] |= rk

    return rows


def reachable_by_tc(rows: List[int], u: int, v: int) -> bool:
    return ((rows[u] >> v) & 1) == 1


if __name__ == "__main__":
    g = [[1, 2], [3], [3, 4], [5], [], []]

    print("k<=2 from 0:", sorted(bfs_k_hop(g, 0, 2)))
    print("reachable 0->5:", reachable_bfs(g, 0, 5))
    print("reachable 4->5:", reachable_bfs(g, 4, 5))

    tc = transitive_closure_small(g)
    print("tc 0->5:", reachable_by_tc(tc, 0, 5))

from collections import deque

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

package main

import "fmt"

func Reachable(graph [][]int, s, t int) bool {
	vis := make([]bool, len(graph))
	q := []int{s}
	vis[s] = true
	for head := 0; head < len(q); head++ {
		u := q[head]
		if u == t {
			return true
		}
		for _, v := range graph[u] {
			if !vis[v] {
				vis[v] = true
				q = append(q, v)
			}
		}
	}
	return false
}

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

#include <iostream>
#include <vector>

std::vector<unsigned long long> closure6(const std::vector<std::vector<int>>& g) {
    int n = (int)g.size();
    std::vector<unsigned long long> row(n, 0);
    for (int u = 0; u < n; ++u) {
        row[u] |= 1ULL << u;
        for (int v : g[u]) row[u] |= 1ULL << v;
    }
    for (int k = 0; k < n; ++k) {
        unsigned long long mk = 1ULL << k;
        for (int u = 0; u < n; ++u) {
            if (row[u] & mk) row[u] |= row[k];
        }
    }
    return row;
}

int main() {
    std::vector<std::vector<int>> g = {{1,2},{3},{3,4},{5},{},{}};
    auto r = closure6(g);
    std::cout << (((r[0] >> 5) & 1ULL) ? "reachable" : "not") << "\n";
}

from collections import deque


def reachable(graph, s, t):
    vis = [False] * len(graph)
    q = deque([s])
    vis[s] = True
    while q:
        u = q.popleft()
        if u == t:
            return True
        for v in graph[u]:
            if not vis[v]:
                vis[v] = True
                q.append(v)
    return False


def 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

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

#define N 6

bool reachable(int g[N][N], int s, int t) {
    int q[128], head = 0, tail = 0;
    bool vis[N] = {0};
    q[tail++] = s;
    vis[s] = true;
    while (head < tail) {
        int u = q[head++];
        if (u == t) return true;
        for (int v = 0; v < N; ++v) {
            if (g[u][v] && !vis[v]) {
                vis[v] = true;
                q[tail++] = 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;
    printf("%d\n", reachable(g, 0, 5));
    return 0;
}

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

bool reachable(const std::vector<std::vector<int>>& g, int s, int t) {
    std::vector<char> vis(g.size(), 0);
    std::queue<int> q;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t) return true;
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    return false;
}

int main() {
    std::vector<std::vector<int>> g = {{1,2},{3},{3,4},{5},{},{}};
    std::cout << reachable(g, 0, 5) << "\n";
}

package main

import "fmt"

func reachable(graph [][]int, s, t int) bool {
	vis := make([]bool, len(graph))
	q := []int{s}
	vis[s] = true
	for head := 0; head < len(q); head++ {
		u := q[head]
		if u == t {
			return true
		}
		for _, v := range graph[u] {
			if !vis[v] {
				vis[v] = true
				q = append(q, v)
			}
		}
	}
	return false
}

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

use std::collections::VecDeque;

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

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

fn main() {
    let g = vec![vec![1, 2], vec![3], vec![3, 4], vec![5], vec![], vec![]];
    println!("{}", reachable(&g, 0, 5));
}

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

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

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