Преобразование 2d-массива в график
Как преобразовать двумерный массив в график. Где каждый элемент массива соединяется со своим соседом (сосед вверх, вниз, вправо и влево).
Предположим, что массив 2x2:
[
[A, B]
[C, D]
]
График будет такой:
Матрица смежности графа выглядит так:
Список смежности графа выглядит следующим образом:
A -> B,C
B -> A,D
C -> A,D
D -> B,C
Какой алгоритм для этого понадобится?
Я просто пытаюсь преобразовать 2D-массив в график в JS.
У меня есть класс с именем vertex:
class Vertex {
constructor(value) {
this.value = value;
this.neighbors = [];
}
/**
*
* @param {Vertex} v
*/
addNeighborsVertex(v) {
this.neighbors.push(v);
}
}
Например, 2D-массив:
let arr = [
["A","B"],
["C","D"]
]
Функция, которая может принимать двумерный массив, преобразовывать его в вершины графа и возвращать список вершин. Каждая вершина содержит значение arr и своего соседа. Также список соседей содержит экземпляр Vertex. Например, вершина для элемента «А» выглядит так:
{
value : "A",
neighbors : [
instanceOfVertexB,
instanceOfVertexC
]
}
Дубликат не допускается. «A» и «D» имеют одинаковых соседей — «B». В этом случае и вершина «A», и вершина «D» содержат один и тот же экземпляр вершины «B».
Как я могу это сделать в js?
Я разместил свой код. Я не хочу писать полный код, мне просто нужно понять, как я могу это сделать.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
Как вы сказали в комментарии, вам не нужен полный код, я не буду предоставлять полный код, а просто идею простого подхода, как это можно сделать.
- создайте
allvertices: Map<string, Vertex>для хранения всех существующих вершин - перебрать весь входной массив
Для каждой вершины во время итерации:
получить текущую вершину с карты.
let v = allvertices.get(vertexname);это либо вернет вершину, если она уже содержится на карте, либо
undefined, если нет.если
v— этоundefined, создайтеv = new Vertex(vertexname)и добавьте его на картуallvertices.set(vertexname, v);получить все
let neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]]текущей вершины. Вам не нужно заботиться о внешних индексах в JS. Доступ к несуществующему индексу массива не выдаст ошибку, а просто вернетundefined
Для каждого соседа в массиве neighbours, который не является undefined:
проверьте, существует ли он уже на карте
allvertices. Если нет, создайте его и добавьте вallvertices(как указано выше)добавьте его в список соседей вершины
vv.addNeighbour(neighbour);
Таким образом, вы создадите ровно один Vertex для каждой записи вашего входного массива, а также ссылки всегда будут идти на один и тот же узел, т.е. у вас не будет дубликатов, как и просили...
Еще один, еще более простой подход, который не требует дополнительной карты (но требует двух итераций входного массива).
повторите свой
arrодин раз и для каждой вершины заменитеstring, который у вас сейчас есть в массиве, на экземпляр классаVertexarr[row][col] = new Vertex(arr[row][col]);повторите
arrвторой раз и добавьте всех соседей к текущей вершинеlet neighbours = [arr[row-1][col],arr[row+1][col],arr[row][col-1],arr[row][col+1]] for (let n of neighbours) { if (n !== undefined) { arr[row][col].addNeighbour(n); } }Вместо создания массива
neighboursвы, конечно, также можете выполнить соответствующие проверки, определен ли сосед, и затем добавить его.if (arr[row-1][col]) arr[row][col].addNeighbour(arr[row-1][col]); if (arr[row+1][col]) arr[row][col].addNeighbour(arr[row+1][col]); ...
Или вы, конечно, могли бы сделать это только за одну итерацию.
при повторении массива проверьте, является ли текущий элемент
stringилиVertex. Если этоstring, замените его наVertex.if (typeof arr[row][col] === "string") arr[row][col] = new Vertex(arr[row][col]);Затем сделайте то же самое для соседей.
if (typeof arr[row+1][col] === "string") arr[row+1][col] = new Vertex(arr[row+1][col]); if (typeof arr[row-1][col] === "string") arr[row-1][col] = new Vertex(arr[row-1][col]); ...Опять же, здесь вам не нужно заботиться об индексах, выходящих за пределы границ, потому что
typeof undefined === "undefined"таким образом, приведенные выше условия будут оцениваться какfalseи, таким образом, ничего не будет сделано, если, например,row+1находится за пределами границ.И добавьте соседей к текущей вершине (как указано выше)
// Спасибо за это. Обе идеи мне очень помогли.
пожалуйста, опубликуйте код, который вы пробовали, и опишите проблему, с которой вы столкнулись. Как написано, это запрос на бесплатный код, чего этот сайт не делает, особенно если в вопросе или тегах не указана ни одна платформа кодирования.