Обход в глубину (DFS) и обход в ширину (BFS)

алгоритм

BingImageOfTheDay

Фронтовик, не стесняйся, просвети меня

задний план

Прочитав обмен многими предшественниками, автор хочет организовать алгоритм обхода графа, который я понимаю сегодня.

Алгоритмы обхода графа делятся на обход в глубину и обход в ширину, если вы понимаете эти два алгоритма буквально, вы можете их хорошо знать. Один основан на глубине, чтобы постоянно находить, есть ли нижний узел, если он есть, продолжать рекурсивный поиск вниз, в противном случае вернуться на верхний уровень, а затем войти из непройденного нижнего узла. Другой основан на широте, от узла, находит все его дочерние узлы, а затем последовательно ищет все дочерние узлы вниз от всех дочерних узлов.

Это поверхностный взгляд автора на обход в глубину и в ширину. Далее будет проведен подробный анализ и понимание.

Обход в глубину (DFS)

Идею обхода в глубину можно разделить на следующие этапы:

  1. Укажите точку как вершину, отметьте ее и найдите всех соседей этого узла.

  2. Если соседний узел не был посещен, отметьте его и введите рекурсию, чтобы найти соседние узлы, которые не отмечены; посетите соседние узлы, а затем введите рекурсию, пока все вершины, которые сообщаются с начальной точкой, не будут помечены для посещения.

  3. Если все узлы отмечены и посещены, он завершится, и наоборот, если есть узлы, которые не были посещены, следующий рекурсивный поиск нужно выполнить с этим узлом в качестве вершины, пока все точки не будут помечены и посещены.

graph

Сначала в качестве вершины выбирается узел, здесь мы начинаем с 0, затем помечаем его и находим любой соседний узел узла.

line1

Если соседний узел не посещался, отметьте его и введите рекурсию, чтобы найти соседние непосещаемые узлы.

line2

Поскольку соседние узлы 3 и 0 узла 4 были посещены, вернитесь к узлу 0, а затем введите следующую рекурсию, пока все вершины, связанные с начальной точкой, не будут помечены для посещения.

line3

Все вышеперечисленные вершины помечаются как посещенные, и этот обход завершен, если остались непосещенные узлы, это означает, что непосещенные узлы не связаны с узлом 0 и не зависят от этого пути. Порядок доступа к приведенному выше неориентированному графу: v0, v1, v3, v7, v4, v2, v5, v8, v6 (не уникальный)

Обход в ширину (BFS)

Обход в ширину, также известный как «поиск в ширину» или «горизонтальный поиск», или сокращенно BFS. Идея его реализации:Начиная с точки, найдите его соседние узлы и поместите их в очередь и отметьте их, затем извлеките первый узел из очереди, найдите соседние непосещенные узлы и поместите их в очередь, пока все соседние узлы посещенного узлы были посещены; если на графе все еще есть непосещенные точки, выберите другую непосещенную точку для начала и выполняйте ту же операцию, пока не будут посещены все узлы на графе.

map1

Шаги от ближнего к дальнему:

  1. Создайте очередь и поместите начальный узел в очередь

  2. Если очередь не пуста, удалите первый узел из очереди и проверьте, является ли он целевым узлом.

    • Если это целевой узел, завершить поиск и вернуть результат
    • Если нет, добавьте в очередь все необнаруженные дочерние узлы.

  3. Если очередь пуста, значит в графе нет целевого узла, тогда обход завершается.

На приведенном выше рисунке целевой узел не задан, поэтому просматриваются все узлы. Сначала посетите узел 0, затем по очереди посетите узлы 1, 4, 2, затем посетите узлы 3, 5 и, наконец, посетите узлы 7, 8, 6, поэтому его порядок посещения следующий: v0, v1, v4, v2, v3, v5, v7, v8, v6 (не уникальный)

Создайте график:

const vertices = []; // 图的顶点集合
const edges = new Map(); // 图的边集合

/**
 * 添加节点
 **/
addVertex = (v: string) => {
  this.vertices.push(v);
  this.edges.set(v, []);
};

/**
 * 添加边
 **/
addEdge = (v: string, w: string) => {
  const vEdge = edges.get(v);
  vEdge.push(w);
  const wEdge = edges.get(w);
  wEdge.push(v);
  edges.set(v, vEdge);
  edges.set(w, wEdge);
};

formatToString = () => {
  let s = "";
  vertices.forEach(v => {
    s += `${v} -> `;
    const neighors = edges.get(v);
    neighors.forEach(n => (s += `${n} `));
    s += "\n";
  });
  return s;
};

Глубокий поиск:

graphDFS = () => {
  const marked = [];
  vertices.forEach(v => {
    if (!marked[v]) {
      dfsVisit(v);
    }
  });

  const dfsVisit = (u: string) => {
    marked[u] = true;
    const neighbors = edges.get(u);
    neighors.forEach(n => {
      if (!marked[n]) {
        dfsVisit(n);
      }
    });
  };
};

Поиск:

graphBFS = (v: string, t?: string) => {
  const queue = [],
    marked = [];
  marked[v] = true;
  queue.push(v); // 添加到队尾
  while (queue.length > 0) {
    const s = queue.shift(); // 从队首移除
    if (t && s === t) {
      console.log("target vertex: ", t);
      return;
    } else if (edges.has(s)) {
      console.log("visited vertex: ", s);
    }
    const neighbors = edges.get(s);
    neighors.forEach(n => {
      if (!marked[n]) {
        marked[n] = true;
        queue.push(n);
      }
    });
  }
};

Суммировать

Сегодня я разобрал понятные мне идеи и реализации обхода в глубину и обхода в ширину Спасибо за просмотр, спасибо!

стоя на плечах великанов

Обход в глубину и обход в ширину

Категории