Към съдържанието
wannacode

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

Накратко: Графът е множество от върхове и ребра; в програмата се пази като списък от съседи с памет O(V + E) или като матрица на съседство с памет O(V²).

Проблем

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

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

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

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

Идеята

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

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

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

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

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

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

Идеята

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

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

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

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

Виж го

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

Map<String, List<String>> graph = new HashMap<>();
Map<String, Integer> index = new HashMap<>();
for (int i = 0; i < stops.length; i++) {
    graph.put(stops[i], new ArrayList<>());
    index.put(stops[i], i);
}
int n = stops.length;
boolean[][] matrix = new boolean[n][n];
for (String[] street : streets) {
    String a = street[0], b = street[1];
    graph.get(a).add(b);
    graph.get(b).add(a);
    int i = index.get(a), j = index.get(b);
    matrix[i][j] = matrix[j][i] = true;
}
Стъпка по стъпка, с думи
  1. Осем спирки, още без улици. Всяка получава празен списък и номер: реда и колоната си в матрицата 8 × 8, цялата с нули.
  2. Първата улица, Склад – Гара: Гара влиза в списъка на Склад, а Склад в списъка на Гара. В матрицата две клетки стават 1: [0][1] и [1][0].
  3. Склад – Пазар: Пазар застава след Гара в списъка на Склад. Редът в списъка е редът на улиците.
  4. Двупосочната улица се записва два пъти: в двата списъка и в двете клетки. Затова матрицата е симетрична спрямо диагонала.
  5. Пазар – Парк и Площад – Кино минават над реката. Пазар и Площад вече имат по трима съседи, другите по двама.
  6. Последните улици на другия бряг. Всеки списък расте само с истинските си улици.
  7. 9 улици: 18 записа в списъците, 64 клетки в матрицата, 46 от тях нули. При 40 000 кръстовища това са около 120 000 записа срещу 1,6 милиарда клетки.

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

for (String stop : stops) {
    System.out.println(stop + ": " + String.join(", ", graph.get(stop)));
}
for (boolean[] row : matrix) {
    StringBuilder line = new StringBuilder();
    for (boolean cell : row) line.append(cell ? "1 " : "0 ");
    System.out.println(line.toString().trim());
}
Изход
Склад: Гара, Пазар
Гара: Склад, Площад
Пазар: Склад, Площад, Парк
Площад: Гара, Пазар, Кино
Парк: Пазар, Стадион
Кино: Площад, Болница
Болница: Кино, Стадион
Стадион: Парк, Болница
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 са еднакви, защото всяка улица е двупосочна.

Пробвай

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

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

String[][] streets = {
    {"Пазар", "Площад"}, {"Площад", "Кино"},
    {"Гара", "Площад"},
};
Map<String, List<String>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String[] street : streets) {
    graph.get(street[0]).add(street[1]);
    graph.get(street[1]).add(street[0]);
}
System.out.println(String.join(", ", graph.get("Площад")));
Отговор

Пробвай

Попълни

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

for (String[] street : streets) {
    int i = index.get(street[0]), j = index.get(street[1]);
    matrix[i][j] =  = true;
}

Идеята

Колко струва

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

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

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

int matrixLooks = 0, matrixFound = 0;
for (int i = 0; i < stops.length; i++) {
    for (int j = 0; j < stops.length; j++) {
        matrixLooks++;
        if (matrix[i][j]) matrixFound++;
    }
}
int listLooks = 0, listFound = 0;
for (String stop : stops) {
    listLooks++;
    for (String next : graph.get(stop)) {
        listLooks++;
        listFound++;
    }
}
System.out.println("Матрица: " + matrixLooks + " поглеждания, " + matrixFound + " съседи");
System.out.println("Списък: " + listLooks + " поглеждания, " + listFound + " съседи");
boolean inMatrix = matrix[index.get("Пазар")][index.get("Парк")];
boolean inList = graph.get("Пазар").contains("Парк");
System.out.println("Има ли улица Пазар - Парк? " + inMatrix + " " + inList);
Изход
Матрица: 64 поглеждания, 18 съседи
Списък: 26 поглеждания, 18 съседи
Има ли улица Пазар - Парк? true true

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

  • Матрица: целият ред на всяко кръстовище O(n²)
  • Списък от съседи: само истинските улици O(n)
Алгоритъмn = 10n = 1000n = 5000n = 100 000
Матрица: целият ред на всяко кръстовище1001 000 00025 000 000≈ 10 000 000 000
Списък от съседи: само истинските улици36487224 716498 734
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
int matrixLooks = 0, matrixFound = 0;
for (int i = 0; i < stops.length; i++) {
    for (int j = 0; j < stops.length; j++) {
        matrixLooks++;
        if (matrix[i][j]) matrixFound++;
    }
}
int listLooks = 0, listFound = 0;
for (String stop : stops) {
    listLooks++;
    for (String next : graph.get(stop)) {
        listLooks++;
        listFound++;
    }
}
System.out.println("Матрица: " + matrixLooks + " поглеждания, " + matrixFound + " съседи");
System.out.println("Списък: " + listLooks + " поглеждания, " + listFound + " съседи");
boolean inMatrix = matrix[index.get("Пазар")][index.get("Парк")];
boolean inList = graph.get("Пазар").contains("Парк");
System.out.println("Има ли улица Пазар - Парк? " + inMatrix + " " + inList);

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

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

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

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

Идеята

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

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

record Street(String to, int meters) {}


String[] lines = {
    "Склад Гара 400",
    "Склад Пазар 300",
    "Гара Площад 500",
    // …
};
Map<String, List<Street>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String line : lines) {
    String[] part = line.split(" ");
    int meters = Integer.parseInt(part[2]);
    graph.get(part[0]).add(new Street(part[1], meters));
    graph.get(part[1]).add(new Street(part[0], meters));
}
record Street е съседът заедно с дължината. Редът се разделя със split, а метрите стават число с Integer.parseInt.
String text = graph.get("Пазар").stream()
        .map(s -> s.to() + " " + s.meters() + " м")
        .collect(Collectors.joining(", "));
System.out.println("Пазар" + ": " + text);
Изход
Пазар: Склад 300 м, Площад 350 м, Парк 600 м

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

Пробвай

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

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

Map<String, List<String>> graph = new HashMap<>();
for (String stop : stops) graph.put(stop, new ArrayList<>());
for (String[] street : streets) {
    String a = street[0], b = street[1];
    graph.get(a).add(b);
    graph.get(b).add(b);
}
Изход
Склад: Гара, Пазар
Гара: Гара, Площад
Пазар: Пазар, Площад, Парк
Площад: Площад, Площад, Кино
Парк: Парк, Стадион
Кино: Кино, Болница
Болница: Болница, Стадион
Стадион: Стадион, Стадион

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

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

По-точно

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

  • HashMap не пази реда на ключовете. Затова програмите обхождат масива stops, а не graph.keySet(). Ако трябва ред, има LinkedHashMap (редът на добавяне) и TreeMap (подредени ключове).
  • Когато спирките не са известни предварително, списъкът се създава при първата улица: graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b).
  • boolean[] заема по един байт на клетка. BitSet пази по един бит, осем пъти по-малко, но 1,6 милиарда бита пак са 200 MB.

Упражнение

Улици и метри

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

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

String[] lines = {
    "Склад Гара 400",
    "Склад Пазар 300",
    "Гара Площад 500",
    "Пазар Площад 350",
    "Пазар Парк 600",
    "Площад Кино 450",
    "Кино Болница 300",
    "Парк Стадион 500",
    "Болница Стадион 250",
};
String[] 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 улици. Колко клетки има матрицата на съседство?
2. Приложението пита „има ли улица между Пазар и Парк?“. Колко струва въпросът?
3. Улицата Гара → Площад е еднопосочна. Какво има в списъка от съседи?
4. Кога матрицата е по-добрият избор?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·