Граф: списък от съседи и матрица
Накратко: Графът е множество от върхове и ребра; в програмата се пази като списък от съседи с памет 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, string)[] streets =[ ("Склад", "Гара"), ("Склад", "Пазар"), ("Гара", "Площад"), ("Пазар", "Площад"), ("Пазар", "Парк"), ("Площад", "Кино"), ("Кино", "Болница"), ("Парк", "Стадион"), ("Болница", "Стадион"),];Същият град ще ни трябва през целия модул: за най-късия път, за островите след затворен мост, после за Dijkstra.
Идеята
Два начина да го пазиш
Матрица на съседство. Номерираш спирките от 0 до V − 1. Таблицата е V × V, а клетката [i][j] казва дали има улица от i до j. Това е таблицата от проблема.
Списък от съседи. За всяка спирка пазиш списък само с нейните съседи. В кода това е речник от име към списък: Dictionary<string, List<string>>. Празни места няма: улица, която я няма, не заема нищо.
Двата се строят от един и същ списък с улици, в един и същ цикъл.
Виж го
Една улица, два записа
var graph = new Dictionary<string, List<string>>();var index = new Dictionary<string, int>();for (int i = 0; i < stops.Length; i++){ graph[stops[i]] = []; index[stops[i]] = i;}var matrix = new bool[stops.Length, stops.Length];foreach (var (a, b) in streets){ graph[a].Add(b); graph[b].Add(a); int i = index[a], j = index[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 милиарда клетки.
Цялата програма печата списъците и матрицата:
foreach (string stop in stops){ Console.WriteLine(stop + ": " + string.Join(", ", graph[stop]));}for (int i = 0; i < stops.Length; i++){ var row = Enumerable.Range(0, stops.Length).Select(j => matrix[i, j] ? 1 : 0); Console.WriteLine(string.Join(" ", row));}Склад: Гара, ПазарГара: Склад, ПлощадПазар: Склад, Площад, ПаркПлощад: Гара, Пазар, КиноПарк: Пазар, СтадионКино: Площад, БолницаБолница: Кино, СтадионСтадион: Парк, Болница0 1 1 0 0 0 0 01 0 0 1 0 0 0 01 0 0 1 1 0 0 00 1 1 0 0 1 0 00 0 1 0 0 0 0 10 0 0 1 0 0 1 00 0 0 0 0 1 0 10 0 0 0 1 0 1 0Списъкът на всяка спирка е в реда, в който са дошли улиците. Матрицата е симетрична: ред 2 и колона 2 са еднакви, защото всяка улица е двупосочна.
Пробвай
Предвиди изхода
Три улици около Площад, в друг ред. Какво печата програмата?
(string, string)[] streets =[ ("Пазар", "Площад"), ("Площад", "Кино"), ("Гара", "Площад"),];var graph = new Dictionary<string, List<string>>();foreach (string stop in stops) graph[stop] = [];foreach (var (a, b) in streets){ graph[a].Add(b); graph[b].Add(a);}Console.WriteLine(string.Join(", ", graph["Площад"]));Пробвай
Попълни
Двупосочната улица трябва да се запише и в двете клетки:
foreach (var (a, b) in streets)
{
int i = index[a], j = index[b];
matrix[i, j] = = true;
}Клетката [i][j] е улицата от i до j, а [j][i] е същата улица обратно. В ненасочен граф двете са винаги еднакви.
Идеята
Колко струва
Трите въпроса, които куриерското приложение задава постоянно, струват различно:
| матрица | списък от съседи | |
|---|---|---|
| памет | 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;foreach (string stop in stops){ listLooks++; foreach (string next in graph[stop]) { listLooks++; listFound++; }}Console.WriteLine($"Матрица: {matrixLooks} поглеждания, {matrixFound} съседи");Console.WriteLine($"Списък: {listLooks} поглеждания, {listFound} съседи");bool inMatrix = matrix[index["Пазар"], index["Парк"]];bool inList = graph["Пазар"].Contains("Парк");Console.WriteLine($"Има ли улица Пазар - Парк? {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 |
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;foreach (string stop in stops){ listLooks++; foreach (string next in graph[stop]) { listLooks++; listFound++; }}Console.WriteLine($"Матрица: {matrixLooks} поглеждания, {matrixFound} съседи");Console.WriteLine($"Списък: {listLooks} поглеждания, {listFound} съседи");bool inMatrix = matrix[index["Пазар"], index["Парк"]];bool inList = graph["Пазар"].Contains("Парк");Console.WriteLine($"Има ли улица Пазар - Парк? {inMatrix} {inList}");При 1000 кръстовища матрицата прави 1 000 000 поглеждания, а списъкът 4 872. При 5000 матрицата вече е 25 000 000, списъкът 24 716. Тези числа са и паметта: матрицата държи n² клетки, списъкът толкова записа, колкото поглеждания прави.
Затова картите на градове, социалните мрежи и зависимостите между пакети се пазят като списъци от съседи. Те са редки графи: E е от порядъка на V, не на V².
По-точно, за любопитните
Матрицата печели, когато графът е гъст: почти всеки е свързан с почти всеки, например таблица на разстоянията между 50 склада. Тогава V² клетки не са разхищение, а „има ли ребро“ е една клетка. Има и среден път: списъкът от съседи с множество (HashSet) вместо списък отговаря на „има ли улица“ средно за O(1), с цената на повече памет на запис.
Идеята
Посока и дължина
В истинската система улицата идва с дължина, а някои улици са еднопосочни. Списъкът от съседи пази тогава двойка: накъде и колко метра. Системата ги изпраща като текст, по улица на ред: „от до метри“.
record Street(string To, int Meters);
string[] lines =[ "Склад Гара 400", "Склад Пазар 300", "Гара Площад 500", // …];var graph = new Dictionary<string, List<Street>>();foreach (string stop in stops) graph[stop] = [];foreach (string line in lines){ string[] part = line.Split(' '); int meters = int.Parse(part[2]); graph[part[0]].Add(new Street(part[1], meters)); graph[part[1]].Add(new Street(part[0], meters));}record Street е съседът заедно с дължината. Редът се разделя със Split, а метрите стават число с int.Parse.var text = graph["Пазар"].Select(s => $"{s.To} {s.Meters} м");Console.WriteLine("Пазар" + ": " + string.Join(", ", text));Пазар: Склад 300 м, Площад 350 м, Парк 600 мЕднопосочната улица е само първото добавяне: в списъка на a влиза b, обратното не. В матрицата се пълни само [i][j], и тя спира да е симетрична. В претеглена матрица клетката пази дължината, а липсващата улица е специална стойност, например безкрайност.
Пробвай
Намери грешката
Колега строи списъка от съседи. Програмата печата:
var graph = new Dictionary<string, List<string>>();foreach (string stop in stops) graph[stop] = [];foreach (var (a, b) in streets){ graph[a].Add(b); graph[b].Add(b);}Склад: Гара, ПазарГара: Гара, ПлощадПазар: Пазар, Площад, ПаркПлощад: Площад, Площад, КиноПарк: Парк, СтадионКино: Кино, БолницаБолница: Болница, СтадионСтадион: Стадион, СтадионГара се оказва съсед сама на себе си, а Склад липсва от списъка ѝ. На кой ред е грешката?
Избери реда с грешката.
Втората посока трябва да сложи a в списъка на b: graph[b].Add(a);. Сега всяка улица записва b в собствения му списък. Пътят от Склад до Гара има, а обратният го няма, сякаш всички улици са еднопосочни, плюс по една „улица“ от всяка спирка до самата нея.
По-точно
Как е в другите езици
bool[,]е правоъгълна таблица в едно парче памет, аbool[][]е масив от редове (jagged), всеки отделен обект. За матрица на съседство[,]е по-компактна.Dictionaryв днешния .NET обхожда ключовете в реда на добавяне, ако нищо не е махано, но това не е обещано в документацията. Затова програмите обхождат масиваstops.boolзаема един байт.BitArrayпази по един бит, но 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. Кой ще ти трябва, ако питаш „от кои спирки се стига до Болница“?
Тест