Графовые алгоритмы (матрица смежности)

предисловие

В последнее время некоторые друзья чувствуют себя очень сложно при написании отношений формы связи, и они не знают, с чего начать. В большинстве случаев back-end студенты обязаны давать вложенную структуру, но у этой структуры есть фатальный недостаток, ее нельзя связать вверх и много избыточных данных. Я рекомендовал матрицу смежности и обнаружил, что многие студенты ее не понимают.Напишите простую научно-популярную статью, чтобы объяснить ее.

Что такое матрица смежности

Не спрашивайте, почему вначале нет инерции

Матрица смежности — это структура данных, используемая для описания отношений между вершинами и ребрами. Суть его в двумерном массиве, который подходит для обработки связи между мельчайшими единицами данных. Существует два режима матрицы смежности: неориентированный граф и ориентированный граф. Основная особенность неориентированного графа заключается в том, что это не означает, что точки направления могут течь в обоих направлениях, в то время как ориентированный граф содержит направления, которые могут быть односторонними или двусторонними между двумя точками. В основном они используются в графических сценах, таких как лабиринты, простые карты, каскадные формы и т. д.

Неориентированный граф

описывать

Неориентированный граф: относится к ребрам, связанным от точки к точке, без ограничений направления. Вы можете идти туда и обратно между двумя часами

Например:

На приведенном выше рисунке представлена ​​простая связь между ребрами и точками:

Верхняя линия, к которой подключается V0, — это v2 v3.

Верхняя строка, к которой подключен V1, — это v3 v4.

Верхняя строка, к которой подключен V2, — это v0 v3 v4.

Верхняя строка, к которой подключен V3, это v0 v1 v2

Верхняя строка, к которой подключен V4, это v1 v2.

Каков формат приведенного выше графика после его оцифровки матрицей смежности?

const arr = [
// v0  v1  v2  v3  v4
   0,  0,  1,  1,  0, // v0
   0,  0,  0,  1,  1, // v1
   1,  0,  0,  1,  1, // v2
   1,  1,  1,  0,  0, // v3
   0,  1,  1,  0,  0, // v4
]

Функции

Некоторые характеристики неориентированных графов:

• Длина матрицы должна быть квадратом числа вершин длинны ^ 2
• Гипотенуза матрицы не может иметь никакого значения.
• Матрица симметрична относительно гипотенузы

Простая реализация

После краткого введения мы просто реализуем неориентированный граф матрицы смежности через JS

class Adjoin {
  constructor(vertex) {
    this.vertex = vertex;
    this.quantity = vertex.length;
    this.init();
  }

  init() {
    this.adjoinArray = Array.from({ length: this.quantity * this.quantity });
  }

  getVertexRow(id) {
    const index = this.vertex.indexOf(id);
    const col = [];
    this.vertex.forEach((item, pIndex) => {
      col.push(this.adjoinArray[index + this.quantity * pIndex]);
    });
    return col;
  }

  getAdjoinVertexs(id) {
    return this.getVertexRow(id).map((item, index) => (item ? this.vertex[index] : '')).filter(Boolean);
  }

  setAdjoinVertexs(id, sides) {
    const pIndex = this.vertex.indexOf(id);
    sides.forEach((item) => {
      const index = this.vertex.indexOf(item);
      this.adjoinArray[pIndex * this.quantity + index] = 1;
    });
  }
}

// 创建矩阵
const demo = new Adjoin(['v0', 'v1', 'v2', 'v3', 'v4'])

// 注册邻接点
demo.setAdjoinVertexs('v0', ['v2', 'v3']);
demo.setAdjoinVertexs('v1', ['v3', 'v4']);
demo.setAdjoinVertexs('v2', ['v0', 'v3', 'v4']);
demo.setAdjoinVertexs('v3', ['v0', 'v1', 'v2']);
demo.setAdjoinVertexs('v4', ['v1', 'v2']);

// 打印
console.log(demo.getAdjoinVertexs('v0'));
// ['v2', 'v3']

Сценарий приложения: связанная форма

После краткого введения выше у нас должна быть основная концепция неориентированного графа матрицы смежности. Итак, как мы применим это к реальным проектам? Ниже приведена страница выбора спецификации заказа Tmall, с которой мы все знакомы Страница заказа этой страницы продаж содержит три ключевых фактора, таких как цвет, тип упаковки и объем памяти. И существует корреляция между тремя ключевыми факторами.

Анализ взаимодействий

• Когда пользователь выбирает спецификацию цвета, подсвечиваются все доступные для выбора параметры, связанные с черным.
• Опция той же спецификации также освещена
• Когда пользователь выбирает тип пакета, некоторые характеристики подсвечиваются под цветом и общедоступной функцией пакета.

Если бэкенд отправляет рекурсивную древовидную структуру 1: это создаст много избыточных данных. 2: Величина передаваемых данных становится больше. 3: Расчет размещается на сервере для увеличения нагрузки на сервер.

данные контракта

const data = [
  { id: '1', specs: [ '紫色', '套餐一', '64G' ] },
  { id: '2', specs: [ '紫色', '套餐一', '128G' ] },
  { id: '3', specs: [ '紫色', '套餐二', '128G' ] },
  { id: '4', specs: [ '黑色', '套餐三', '256G' ] },
];
const commoditySpecs = [
  { title: '颜色', list: [ '红色', '紫色', '白色', '黑色' ] },
  { title: '套餐', list: [ '套餐一', '套餐二', '套餐三', '套餐四' ]},
  { title: '内存', list: [ '64G', '128G', '256G' ] }
];

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

Применить неориентированный граф

Из приведенных выше данных видно, что все данные о продукте представляют собой единый идентификатор продукта, который связан с разными спецификациями. Тогда эти спецификации могут быть как отдельные вершины. Сочетание различных спецификаций одного продукта можно рассматривать как ассоциативное отношение различных спецификаций. Здесь следует отметить, что в различных сценариях

Игнорировать родного брата (необязательно)

Тот же уровень опционально

Попробуем объяснить приведенное выше взаимодействие с помощью неориентированного графа.

• Если не выбрано, все достижимые вершины кликабельны. (Рисунок 1)
• После выбора вершины находятся все опции текущей вершины (рисунок 2)
• При выборе нескольких вершин возможен вариант объединения соседних точек каждой вершины (рис. 3).

Фигура 1:

Рисунок II:

Рисунок 3:

Количество охватов >= количество вершин

Код

class Adjoin {
  ********
  ****
  **
  getRowToatl(params) {
    params = params.map(id => this.getVertexRow(id));
    const adjoinNames = [];
    this.vertex.forEach((item, index) => {
      const rowtotal = params.map(value => value[index]).reduce((total, current) => {
        total += current || 0;
        return total;
      }, 0);
      adjoinNames.push(rowtotal);
    });
    return adjoinNames;
  }

  // 交集
  getUnions(params) {
    const row = this.getRowToatl(params);
    return row.map((item, index) => item >= params.length && this.vertex[index]).filter(Boolean);
  }

  // 并集
  getCollection(params) {
    params = this.getRowToatl(params);
    return params.map((item, index) => item && this.vertex[index]).filter(Boolean);
  }
}

class ShopAdjoin extends Adjoin {
  constructor(commoditySpecs, data) {
    super(commoditySpecs.reduce((total, current) => [
      ...total,
      ...current.list,
    ], []));
    this.commoditySpecs = commoditySpecs;
    this.data = data;
    // 单规格矩阵创建
    this.initCommodity();
    // 同类顶点创建
    this.initSimilar();
  }

  initCommodity() {
    this.data.forEach((item) => {
      this.applyCommodity(item.specs);
    });
  }

  initSimilar() {
    // 获得所有可选项
    const specsOption = this.getCollection(this.vertex);
    this.commoditySpecs.forEach((item) => {
      const params = [];
      item.list.forEach((value) => {
        if (specsOption.indexOf(value) > -1) params.push(value);
      });
      // 同级点位创建
      this.applyCommodity(params);
    });
  }

  querySpecsOptions(params) {
    // 判断是否存在选项填一个
    if (params.some(Boolean)) {
      // 过滤一下选项
      params = this.getUnions(params.filter(Boolean));
    } else {
      // 兜底选一个
      params = this.getCollection(this.vertex);
    }
    return params;
  }

  applyCommodity(params) {
    params.forEach((param) => {
      this.setAdjoinVertexs(param, params);
    });
  }
}


export default function App({ data, commoditySpecs }) {
  const [specsS, setSpecsS] = useState(Array.from({ length: commoditySpecs.length }));
  // 创建一个购物矩阵
  const shopAdjoin = useMemo(() => new ShopAdjoin(commoditySpecs, data), [
    commoditySpecs,
    data,
  ]);
  // 获得可选项表
  const optionSpecs = shopAdjoin.querySpecsOptions(specsS);

  const handleClick = function (bool, text, index) {
    if (specsS[index] !== text && !bool) return;
    specsS[index] = specsS[index] === text ? '' : text;
    setSpecsS(specsS.slice());
  };

  return (
    <div className="container">
      {
        commoditySpecs.map(({ title, list }, index) => (
          <div key={index}>
            <h1>{title}</h1>
            <Flex wrap="wrap">
              {
                list.map((value, i) => (
                  <span
                    key={i}
                    className={classnames({
                      option: optionSpecs.indexOf(value) > -1,
                      active: specsS.indexOf(value) > -1,
                    })}
                    onClick={() => handleClick(optionSpecs.indexOf(value) > -1, value, index)}
                  >{value}
                  </span>
                ))
              }
            </Flex>
          </div>
        ))
      }
    </div>
  );
}

ориентированный граф

описывать

Направленный граф: Относится к направлению связи между двумя точками. Он дает понятие направления на основе неориентированного графа. Его основным сценарием применения является карта

Например:

На приведенном выше рисунке представлена ​​простая связь между ребрами и точками.

Вершина, в которую может перейти V0, — это v2.

Вершина, в которую может перейти V1, — это v4.

Доступно для вершины V2 - v3

Вершины, которых может достичь V3, это v0 v1

Вершины, в которые может перейти V4, это v2 v3

Каков формат приведенного выше графика после его оцифровки матрицей смежности?

const arr = [
// v0  v1  v2  v3  v4
   0,  0,  1,  0,  0, // v0
   0,  0,  0,  0,  1, // v1
   0,  0,  0,  1,  0, // v2
   1,  1,  0,  0,  0, // v3
   0,  0,  1,  1,  0, // v4
]

Функции

Степень i-й вершины равна сумме количества ненулевых элементов в i-й строке и i-м столбце

• Длина матрицы должна быть квадратом числа вершин длинны ^ 2
• Гипотенуза матрицы не может иметь никакого значения.
• Количество ненулевых элементов в i-й строке равно исходящей степени i-й вершины
• Количество ненулевых элементов в i-м столбце равно входящей степени i-й вершины

алгоритм матрицы связи

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

алгоритм поиска в глубину

Алгоритм поиска в глубину начинается с точки и начинает обход всего графа, предпочтительно посещает его ближайший узел и продолжает посещать последний непосещенный узел на одностороннем пути, а затем возвращается к исходному пути и исследует следующий путь (сначала- вход, последний выход)

Конкретные шаги:

• Начиная с вершины v в графе, начните посещение.
• Найдите первого непосещенного соседа своей вершины, посетите вершину.
• Возьмите эту вершину в качестве новой вершины и повторяйте этот шаг до тех пор, пока текущая вершина не будет иметь непосещенных соседей.
• Возвращает ранее посещенную вершину с непосещенными соседями, находит следующего непосещенного соседа вершины и посещает вершину.
• Повторяйте шаги 2, 3 и 4, пока не будут посещены все вершины графа.

Для ранее созданной матрицы путь доступа следующий: начиная с v0

Давайте реализуем вышеуказанные функции. При этом можно добавить еще одну функцию, а также согласовать узел отсечки

******
  // 深度优先遍历
  dfs(startId, endID) {
    const nodes = [];

    if (startId != null) {
      const stack = [];
      stack.push([startId]);
      while (stack.length !== 0) {
        const sides = stack.pop();
        const side = sides[0];

        if (nodes.every(item => item[0] !== side)) {
          // 注册节点
          nodes.push(sides);
          // 结束点退出
          if (side === endID) break;
          const children = this.getAdjoinVertexs(side);
          children.slice().reverse().forEach((item) => {
            stack.push([item, side]);
          });
        }
      }
    }
    return nodes;
  }
  // 搜寻链路
  lookupLink(params) {
    return params.reduceRight((total, current) => {
      if (total[total.length - 1] === current[0] && current[1]) {
        total.push(current[1]);
      }
      return total;
    }, params[params.length - 1]).reverse();
  }

*******
 console.log(demo.lookupLink(demo.dfs('v0', 'v4')));
 console.log(demo.lookupLink(demo.dfs('v3', 'v4')));

// ["v0", "v2", "v3", "v1", "v4"]
// ["v3", "v0", "v2", "v4"]

Этот метод может быстро найти путь между двумя точками. Но не гарантируется оптимальное решение

алгоритм в ширину

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

Конкретные шаги:

• Начиная с вершины v в графе, начните посещение.
• Найти всех непосещенных соседей текущей вершины, посетить все узлы.
• Продолжайте шаг 2 с доступными узлами, пока не будут посещены все вершины графа.

Для ранее созданной матрицы путь доступа следующий: начиная с v0

Давайте реализуем вышеперечисленные функции и заодно добавим еще одну функцию. Срок можно согласовать

  // 广度优先遍历
  bfs(startId, endID) {
    const nodes = [];
    if (startId != null) {
      const stack = [];
      stack.unshift([startId]);
      while (stack.length !== 0) {
        const sides = stack.shift();
        const side = sides[0];

        if (nodes.every(item => item[0] !== side)) {
          nodes.push(sides);
          // 结束点退出
          if (side === endID) break;
          const children = this.getAdjoinVertexs(side);
          children.forEach((item) => {
            stack.push([item, side]);
          });
        }
      }
    }
    return nodes;
  }

console.log(demo.lookupLink(demo.dfs('v0', 'v3')));
console.log(demo.lookupLink(demo.bfs('v0', 'v3')));
// ["v0", "v2", "v3"]
// ["v0", "v3"]

Этот метод позволяет быстро найти путь оптимального решения между двумя точками.

приложение карты

простая карта

Простая карта учитывает только количество шагов в расчете и не учитывает размер шага.

Алгоритм поиска в глубину и алгоритм поиска в ширину были представлены выше и помогают нам указать конечный узел. Давайте проверим график

demo.setAdjoinVertexs('v0', ['v2']);
demo.setAdjoinVertexs('v1', ['v4']);
demo.setAdjoinVertexs('v2', ['v3']);
demo.setAdjoinVertexs('v3', ['v0', 'v1']);
demo.setAdjoinVertexs('v4', ['v2', 'v3']);

console.log(demo.lookupLink(demo.dfs('v4', 'v3')));
console.log(demo.lookupLink(demo.bfs('v4', 'v3')));
// ["v4", "v2", "v3"]
// ["v4", "v3"]

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

взвешенный ориентированный граф

Не ходите подростком, есть предельная проблема

описывать

В предыдущей демонстрации мы решали задачу простых карт через матрицу связи ориентированного графа, которая соответствует наименьшему переносу в карте Гаоде. Но есть и другие режимы при навигации по карте Гаоде: кратчайшее расстояние, кратчайшее время. Этот тип режима навигации фактически дает понятие размера шага (время, расстояние и т. д.) матрице связи направленного графа.Такой тип графа в совокупности называется взвешенной матрицей связи ориентированного графа. Например, следующая картинка:

На приведенном выше рисунке добавлено понятие расстояния к ориентированному графу, введенному ранее, давайте создадим двумерную матрицу. Из-за концепции добавления весов мы больше не можем использовать 0 для недостижимых путей. Недостижимые пути представлены ∞

const arr = [
// v0  v1  v2  v3  v4
   0,  ∞,  1,  ∞,  ∞, // v0
   ∞,  0,  ∞,  ∞,  4, // v1
   ∞,  ∞,  0,  3,  ∞, // v2
   5,  3,  ∞,  0,  ∞, // v3
   ∞,  ∞,  1,  6,  0, // v4
]

Поскольку текущий узел связан сам с собой, вес равен 0

Как решить задачу о кратчайшем ребре в случае графов с весами? Посмотрите на следующий алгоритм

Алгоритм Дейкстры

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

Конкретные шаги:

• Начиная с вершины v в графе, начните посещение.
• Найдите всех непосещенных соседей текущей вершины и отсортируйте их по весу, чтобы сформировать массив A.
• Посетите кратчайшее ребро и посетите все непосещенные соседние узлы.
• Текущий вес вершины +, если вес соседней вершины
• Повторяйте шаги 2-4, пока не будут посещены все вершины.

Например: каков кратчайший путь от V0 до различных вершин?

1: Построить взвешенную матрицу связей

фигура 1

2: взять v0 во все вершины, вынуть массив и отсортировать по весу вершины.

3: указана вершина V0, вес равен 0, и вводится следующая вершина.

Рисунок II

4: Переупорядочивание непосещенных вершин

5: Вершина V2 ставится в очередь, и все ведущие вершины, которые не были посещены, посещаются.

6: взвешивание v0v2 + взвешивание v2v3

Рисунок 3

Рисунок 4

Рисунок 5

Рисунок 6

// 迪科斯彻最短路径  
dijkstra(startId, endID) {
    const stack = this.getVertexRow(startId).map((item, index) => [
      item,
      this.vertex[index],
      startId,
    ]).sort((a, b) => b[0] - a[0]);
    const nodes = [];

    while (stack.length) {
      // 删除最后节点
      const node = stack.pop();
      const [weights, side] = node;

      nodes.push(node);
      if (side === endID) break;

      if (weights) {
        const children = this.getVertexRow(side).map((item, index) => [item, this.vertex[index]]);
        children.forEach((item) => {
          let single = [];
          stack.some((value) => {
            if (value[1] === item[1]) {
              single = value;
              return true;
            }
            return false;
          });

          const [nodeWeights, id] = single;
          // const index
          if (id && weights + item[0] < nodeWeights) {
            single[0] = weights + item[0];
            single[2] = side;
          }
        });
      }
      stack.sort((a, b) => b[0] - a[0]);
    }

    return nodes;
  }

const router = demo2.dijkstra('v4', 'v3');
console.log(`距离：${router[router.length - 1][0]}, 路线：${demo.lookupLink(router.map(item => [item[1], item[2]]))}`);
// 距离：4, 路线：v4,v2,v3

Суммировать

Эта статья носит ознакомительный характер, существует множество алгоритмов для решения такого рода графических сетевых ассоциаций, например: Floyd, Johnson, SPFA, A*, В* и т. д. Заинтересованы в дальнейших исследованиях.

Вот ключ:👇👇👇👇👇