深度优先搜索（DFS)

介绍

DFS是另一种用于图遍历的搜索算法。与BFS不同，DFS会尽可能深地访问图的节点，直到不能再继续前进为止， 然后回溯到上一个节点，继续探索其他路径。DFS递归地探索每个可能的路径，直到找到目标节点或遍历完整个图。 DFS使用堆栈数据结构来辅助实现，它常用于寻找路径、拓扑排序、连通性检测等场景。

路径一般不会是最短的

😦

代码上与 BFS 唯一区别: DFS 用堆， BFS 用队列；

动画模拟

工作原理

• 从图的某个起始节点开始，首先访问该节点。
• 然后沿着其连通路径尽可能深地访问其他节点，直到不能再继续前进为止。
• 回溯到上一个节点，继续探索其他未访问的路径。
• 重复上述过程，直到所有节点都被访问过。

算法特性

• 递归特性：DFS可以用递归（函数自调用）实现。在递归中，函数调用栈自动管理节点状态。
• 栈的使用：在非递归版本中，需要显式使用栈来模拟递归过程。
• 路径回溯：当某条路径探索完成后，回退到上一个节点继续探索未访问的邻居。

源码

<script setup lang="ts">
import SortBarChart from "../comp/sort-bar-chart.vue";
import { onMounted, ref } from "vue";
import { genMatrix, genRandArray, GenRandomFromPool, index2xy } from "../sort.util";
import SearchMatrixChart from "../comp/search-matrix-chart.vue";
import { sleep } from "../../../utils/cmm.util";

const w = 34;
const h = 20;

// 00 可通行，1 起点 15 已访问的起点 2 终点 3 障碍物 4 最终路径 5 已经访问过的
const data = ref<number[][]>();
const barrierCount = ref<number>(100);
let start = ref();

const refreshData = () => {
  data.value = genMatrix(w, h, () => 0);
  const gen = new GenRandomFromPool(GenRandomFromPool.toArray(0, w * h - 1));
  start.value = index2xy(gen.poll(1)[0], w);
  data.value[start.value[1]][start.value[0]] = 1;
  const barrier = gen.poll(barrierCount.value).map(i => index2xy(i, w));
  barrier.forEach(([x, y]) => (data.value[y][x] = 3));
  const end = index2xy(gen.poll(1)[0], w);
  data.value[end[1]][end[0]] = 2;
};

const setValue = (p: number[], v: number) => {
  const [x, y] = p;
  data.value[y].splice(x, 1, v);
};

onMounted(refreshData);

const stepInterval = ref<number>(20);

const DX = [0, 1, 0, -1];
const DY = [-1, 0, 1, 0];

/**
 * 开始搜索
 */
const search = async () => {
  const queue = [[...start.value, []]];
  while (queue.length) {
    const p = queue.pop();
    const [x, y, path] = p;
    if ([3, 5, 15].includes(data.value[y][x])) {
      continue;
    }
    const v = data.value[y][x];

    setValue(p, 4);
    await sleep(stepInterval.value);
    setValue(p, v);

    if (data.value[y][x] === 2) {
      for (const [x, y] of path) {
        if (data.value[y][x] != 15) {
          setValue([x, y], 4);
        }
      }
      return;
    }
    setValue(p, data.value[y][x] === 1 ? 15 : 5);
    const nextP = [...path, [x, y]];
    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + DX[i], y + DY[i]];
      if (nx >= 0 && nx < w && ny >= 0 && ny < h) queue.push([nx, ny, nextP]);
    }
  }
};
</script>

<template>
  <div class="">
    <a-space direction="horizontal">
      <a-input-number v-model="stepInterval" :step="50" :min="5" style="width: 200px">
        <template #suffix>ms</template>
        <template #prefix> 步进间隔</template>
      </a-input-number>
      <a-input-number v-model="barrierCount" :step="50" :min="5" style="width: 160px">
        <template #prefix> 障碍物数量</template>
      </a-input-number>
      <a-button @click="search()" type="primary">开始搜索</a-button>
      <a-button @click="refreshData">刷新数据</a-button>
    </a-space>
    <div class="mt-sm">
      <search-matrix-chart :data="data" :start="start" />
    </div>
  </div>
</template>

<style scoped lang="less"></style>