Графи в JavaScript: списък от съседи и матрица

Проблем

Таблицата, която не се събира

Куриерска фирма пази уличната мрежа на града в таблица: ред и колона за всяко кръстовище, а в клетката пише 1, ако между двете има улица. Когато фирмата работеше в един квартал с 300 кръстовища, таблицата беше 90 000 клетки и никой не се оплакваше.

После фирмата покри целия град: 40 000 кръстовища. Таблицата стана 40 000 × 40 000 = 1,6 милиарда клетки. Дори по един байт на клетка това са 1,6 GB, а сървърът започна да пада при всяко зареждане на картата.

Най-обидното е, че почти всичко в таблицата е 0. От кръстовище излизат три-четири улици, не 40 000. Как да пазиш само улиците, които ги има?

Идеята

Спирки и улици: граф

Картата на доставките се описва с две неща: спирки (кръстовища, складове, адреси) и улици между тях. Такова нещо се казва граф. Спирките са върховете му (vertex), а улиците са ребрата (edge). Броят върхове се бележи с V, а броят ребра с E.

Ненасочен граф: улицата е двупосочна. Ако има път от Гара до Площад, има и обратно.
Насочен граф: еднопосочните улици. Ребро Гара → Площад не дава път Площад → Гара.
Претеглен граф: всяко ребро носи число: дължина в метри, минути, цена в €.

Ето нашия град: 8 спирки и 9 двупосочни улици. Реката го дели на две части, свързани с два моста. Така идва графът от системата на фирмата: списък със спирките и списък с улиците (по двойка имена на ред).

const stops = [
  "Склад", "Гара", "Пазар", "Площад",
  "Парк", "Кино", "Болница", "Стадион",
];
const streets = [
  ["Склад", "Гара"], ["Склад", "Пазар"],
  ["Гара", "Площад"], ["Пазар", "Площад"],
  ["Пазар", "Парк"], ["Площад", "Кино"],
  ["Кино", "Болница"], ["Парк", "Стадион"],
  ["Болница", "Стадион"],
];

Същият град ще ни трябва през целия модул: за най-късия път, за островите след затворен мост, после за Dijkstra.

Идеята

Два начина да го пазиш

Матрица на съседство. Номерираш спирките от 0 до V − 1. Таблицата е V × V, а клетката [i][j] казва дали има улица от i до j. Това е таблицата от проблема.

Списък от съседи. За всяка спирка пазиш списък само с нейните съседи. В кода това е речник от име към списък: Map от име към масив. Празни места няма: улица, която я няма, не заема нищо.

Двата се строят от един и същ списък с улици, в един и същ цикъл.

Виж го

Една улица, два записа

const graph = new Map(stops.map((stop) => [stop, []]));
const index = new Map(stops.map((stop, i) => [stop, i]));
const n = stops.length;
const matrix = stops.map(() => new Array(n).fill(false));
for (const [a, b] of streets) {
  graph.get(a).push(b);
  graph.get(b).push(a);
  const i = index.get(a);
  const j = index.get(b);
  matrix[i][j] = matrix[j][i] = true;
}

Стъпка по стъпка, с думи

Осем спирки, още без улици. Всяка получава празен списък и номер: реда и колоната си в матрицата 8 × 8, цялата с нули.
Първата улица, Склад – Гара: Гара влиза в списъка на Склад, а Склад в списъка на Гара. В матрицата две клетки стават 1: [0][1] и [1][0].
Склад – Пазар: Пазар застава след Гара в списъка на Склад. Редът в списъка е редът на улиците.
Двупосочната улица се записва два пъти: в двата списъка и в двете клетки. Затова матрицата е симетрична спрямо диагонала.
Пазар – Парк и Площад – Кино минават над реката. Пазар и Площад вече имат по трима съседи, другите по двама.
Последните улици на другия бряг. Всеки списък расте само с истинските си улици.
9 улици: 18 записа в списъците, 64 клетки в матрицата, 46 от тях нули. При 40 000 кръстовища това са около 120 000 записа срещу 1,6 милиарда клетки.

Цялата програма печата списъците и матрицата:

for (const stop of stops) {
  console.log(`${stop}: ${graph.get(stop).join(", ")}`);
}
for (const row of matrix) {
  console.log(row.map((cell) => (cell ? 1 : 0)).join(" "));
}

Склад: Гара, Пазар
Гара: Склад, Площад
Пазар: Склад, Площад, Парк
Площад: Гара, Пазар, Кино
Парк: Пазар, Стадион
Кино: Площад, Болница
Болница: Кино, Стадион
Стадион: Парк, Болница
0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
0 1 1 0 0 1 0 0
0 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0

Списъкът на всяка спирка е в реда, в който са дошли улиците. Матрицата е симетрична: ред 2 и колона 2 са еднакви, защото всяка улица е двупосочна.

Пробвай

Предвиди изхода

Три улици около Площад, в друг ред. Какво печата програмата?

const streets = [
  ["Пазар", "Площад"], ["Площад", "Кино"],
  ["Гара", "Площад"],
];
const graph = new Map(stops.map((stop) => [stop, []]));
for (const [a, b] of streets) {
  graph.get(a).push(b);
  graph.get(b).push(a);
}
console.log(graph.get("Площад").join(", "));

Отговор

Пазар, Кино, Гара

Гара, Кино, Пазар

Гара, Пазар, Кино

Пробвай

Попълни

Двупосочната улица трябва да се запише и в двете клетки:

for (const [a, b] of streets) {
  const i = index.get(a);
  const j = index.get(b);
  matrix[i][j] =  = true;
}

Идеята

Колко струва

Трите въпроса, които куриерското приложение задава постоянно, струват различно:

	матрица	списък от съседи
памет	V² клетки	V списъка и 2E записа: O(V + E)
има ли улица между a и b?	една клетка: O(1)	преглед на съседите на a: O(съседи)
кои са съседите на a?	целият ред: O(V)	само съседите: O(съседи)

Програмата обхожда съседите на всяка спирка и по двата начина и брои всяко поглеждане: в матрицата всяка клетка, в списъка всяка спирка и всеки запис.

let matrixLooks = 0;
let matrixFound = 0;
for (let i = 0; i < stops.length; i++) {
  for (let j = 0; j < stops.length; j++) {
    matrixLooks++;
    if (matrix[i][j]) matrixFound++;
  }
}
let listLooks = 0;
let listFound = 0;
for (const stop of stops) {
  listLooks++;
  for (const next of graph.get(stop)) {
    listLooks++;
    listFound++;
  }
}
console.log(`Матрица: ${matrixLooks} поглеждания, ${matrixFound} съседи`);
console.log(`Списък: ${listLooks} поглеждания, ${listFound} съседи`);
const inMatrix = matrix[index.get("Пазар")][index.get("Парк")];
const inList = graph.get("Пазар").includes("Парк");
console.log(`Има ли улица Пазар - Парк? ${inMatrix} ${inList}`);

Матрица: 64 поглеждания, 18 съседи
Списък: 26 поглеждания, 18 съседи
Има ли улица Пазар - Парк? true true

При 8 спирки разликата е малка. Пусни същото върху град-решетка от n кръстовища, всяко свързано с десния и долния си съсед:

Матрица: целият ред на всяко кръстовище O(n²)
Списък от съседи: само истинските улици O(n)

Алгоритъм	n = 10	n = 1000	n = 5000	n = 100 000
Матрица: целият ред на всяко кръстовище	100	1 000 000	25 000 000	≈ 10 000 000 000
Списък от съседи: само истинските улици	36	4872	24 716	498 734

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

let matrixLooks = 0;
let matrixFound = 0;
for (let i = 0; i < stops.length; i++) {
  for (let j = 0; j < stops.length; j++) {
    matrixLooks++;
    if (matrix[i][j]) matrixFound++;
  }
}
let listLooks = 0;
let listFound = 0;
for (const stop of stops) {
  listLooks++;
  for (const next of graph.get(stop)) {
    listLooks++;
    listFound++;
  }
}
console.log(`Матрица: ${matrixLooks} поглеждания, ${matrixFound} съседи`);
console.log(`Списък: ${listLooks} поглеждания, ${listFound} съседи`);
const inMatrix = matrix[index.get("Пазар")][index.get("Парк")];
const inList = graph.get("Пазар").includes("Парк");
console.log(`Има ли улица Пазар - Парк? ${inMatrix} ${inList}`);

При 1000 кръстовища матрицата прави 1 000 000 поглеждания, а списъкът 4 872. При 5000 матрицата вече е 25 000 000, списъкът 24 716. Тези числа са и паметта: матрицата държи n² клетки, списъкът толкова записа, колкото поглеждания прави.

Затова картите на градове, социалните мрежи и зависимостите между пакети се пазят като списъци от съседи. Те са редки графи: E е от порядъка на V, не на V².

По-точно, за любопитните

Матрицата печели, когато графът е гъст: почти всеки е свързан с почти всеки, например таблица на разстоянията между 50 склада. Тогава V² клетки не са разхищение, а „има ли ребро“ е една клетка. Има и среден път: списъкът от съседи с множество (Set) вместо списък отговаря на „има ли улица“ средно за O(1), с цената на повече памет на запис.

Идеята

Посока и дължина

В истинската система улицата идва с дължина, а някои улици са еднопосочни. Списъкът от съседи пази тогава двойка: накъде и колко метра. Системата ги изпраща като текст, по улица на ред: „от до метри“.

const lines = [
  "Склад Гара 400",
  "Склад Пазар 300",
  "Гара Площад 500",
  // …
];
const graph = new Map(stops.map((stop) => [stop, []]));
for (const line of lines) {
  const [a, b, text] = line.split(" ");
  const meters = Number(text);
  graph.get(a).push({ to: b, meters });
  graph.get(b).push({ to: a, meters });
}

Съседът и дължината са обект { to, meters }. split(" ") разделя реда, а Number прави метрите число.

const text = graph.get("Пазар").map((s) => `${s.to} ${s.meters} м`);
console.log(`Пазар: ${text.join(", ")}`);

Пазар: Склад 300 м, Площад 350 м, Парк 600 м

Еднопосочната улица е само първото добавяне: в списъка на a влиза b, обратното не. В матрицата се пълни само [i][j], и тя спира да е симетрична. В претеглена матрица клетката пази дължината, а липсващата улица е специална стойност, например безкрайност.

Пробвай

Намери грешката

Колега строи списъка от съседи. Програмата печата:

const graph = new Map(stops.map((stop) => [stop, []]));
for (const [a, b] of streets) {
  graph.get(a).push(b);
  graph.get(b).push(b);
}

Склад: Гара, Пазар
Гара: Гара, Площад
Пазар: Пазар, Площад, Парк
Площад: Площад, Площад, Кино
Парк: Парк, Стадион
Кино: Кино, Болница
Болница: Болница, Стадион
Стадион: Стадион, Стадион

Гара се оказва съсед сама на себе си, а Склад липсва от списъка ѝ. На кой ред е грешката?

Избери реда с грешката.

По-точно

Как е в другите езици

Капан: new Array(n).fill([]) слага един и същ масив във всяка клетка. Затова редовете се правят с stops.map(() => new Array(n).fill(false)).
Масивът от true/false не е компактен. За голяма матрица има Uint8Array(n * n) (по един байт, клетката е m[i * n + j]): така е направена матрицата в Bench отгоре.
Map пази реда на добавяне на ключовете, обикновеният обект {} невинаги (числовите ключове отиват напред). Затова графът е Map.

Упражнение

Улици и метри

Реши задачата в редактора си.

Улиците на спирката. Системата изпраща двупосочните улици като редове „от до метри“, а еднопосочните отделно:

const lines = [
  "Склад Гара 400",
  "Склад Пазар 300",
  "Гара Площад 500",
  "Пазар Площад 350",
  "Пазар Парк 600",
  "Площад Кино 450",
  "Кино Болница 300",
  "Парк Стадион 500",
  "Болница Стадион 250",
];

const oneWay = [
  "Гара Пазар 650",
  "Стадион Кино 550",
];

Построй претегления граф: двупосочните в двете посоки, еднопосочните само от първата спирка към втората. За всяка спирка изведи колко улици излизат от нея и колко метра са общо, а накрая спирката с най-много улици (при равенство първата по ред):

Склад: 2 улици, 700 м
Гара: 3 улици, 1550 м
Пазар: 3 улици, 1250 м
Площад: 3 улици, 1300 м
Парк: 2 улици, 1100 м
Кино: 2 улици, 750 м
Болница: 2 улици, 550 м
Стадион: 3 улици, 1300 м
Най-много улици: Гара (3)

Още задачи

Задънени улици. Изведи спирките, от които излиза само една улица.
Матрица с метри. Построй матрица, в която клетката е дължината на улицата или -1, ако улица няма, и я изведи.
Обратна посока. От графа с еднопосочните улици построй обратния: всяко ребро a → b става b → a. Кой ще ти трябва, ако питаш „от кои спирки се стига до Болница“?

Тест

Провери се

1. Градът има 40 000 кръстовища, а от всяко излизат около 3 улици. Колко клетки има матрицата на съседство?120 000: по една за всеки край на улица60 000: по една за всяка улица1,6 милиарда: 40 000 × 40 000

2. Приложението пита „има ли улица между Пазар и Парк?“. Колко струва въпросът?И в двете една стъпкаВ матрицата една клетка, в списъка обхождане на съседите на ПазарВ матрицата целият ред, в списъка една стъпка

3. Улицата Гара → Площад е еднопосочна. Какво има в списъка от съседи?Двете са една в списъка на другаПлощад е в списъка на Гара, но Гара не е в списъка на ПлощадНикоя от двете

4. Кога матрицата е по-добрият избор?Когато графът е гъст и често питаш „има ли ребро между тези два“Винаги, защото е по-бързаКогато градът е голям и рядък

Граф: списък от съседи и матрица

Бисквитки