7
BFS 取得距離的小技巧 (/z/programming-contest)

先來個原始版本的 BFS:

Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
boolean[] visited = new boolean[n];
visited[src] = true;

while (!queue.isEmpty()) {
    int u = queue.poll();

    // we need the distance here

    for (int v:g[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        queue.offer(v);
    }
}

如果想知道 destination 和 src 的距離是多少, 常見的作法是另外開一個 array 來存, 或著把 distance 也一起放入 queue 裡。 (假設 distance 跟 u 型態一致,否則就只好另外開一個 queue)

以下提供一個多年前在線上競賽中看到其他參賽者的寫法。 總共只需要增加四行,充分利用了 BFS 每次只會深入一層的特性。

Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
boolean[] visited = new boolean[n];
visited[src] = true;

int dis = -1;                               // 1
while (!queue.isEmpty()) {
    dis++;                                  // 2
    for (int i=queue.size(); i>0; i--) {    // 3
        int u = queue.poll();

        // `dis` is the distance between `src` and `u`

        for (int v:g[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            queue.offer(v);
        }
    }                                       // 4
}
sayuan 積分 1

唔,這篇好像應該寫在 blog 裡,再貼連結過來才對....XD

koji 積分 0

哈好主意,也忘記你 blog 在哪 :~。

sayuan 積分 2 編輯於

趁現在馬上打廣告 my blog1 XD

整整一年多沒寫文章,希望接下來可以針對程式競賽寫個幾篇。

koji 積分 1

來個每次解題的解說吧~