Какво е граф
Графът е една от най-важните структури от данни. Той се състои от върхове (vertices, nodes) и ребра (edges), които ги свързват.
Графите моделират почти всичко около нас:
- Социална мрежа — върховете са хора, ребрата „приятелства".
- Карта на градове — върхове = градове, ребра = пътища.
- Уеб — върхове = страници, ребра = линкове.
- Метро мрежа — върхове = станции, ребра = линии.
- Семейно дърво — частен случай (дърво).
Видове графи
Насочен срещу ненасочен
| Ненасочен граф | Насочен граф (digraph) | |
|---|---|---|
| Ребро A—B означава | A и B са свързани (в двете посоки) | От A има стрелка към B (не задължително обратно) |
| Пример | Приятелство (взаимно) | Followers в Twitter, връзки в web (линкове) |
| В код | Добавяш A→B И B→A в списъка със съседи | Добавяш само A→B |
Тегловен срещу нетегловен
Тегловен граф — всяко ребро има число (тегло). Пример: разстояние между градове в км, време за пътуване, цена на самолетен билет. Нетегловен граф просто казва „има/няма връзка".
Други полезни понятия
- Път — последователност от свързани върхове (1 → 2 → 3 → 4).
- Цикъл — път, който се връща в стартовия връх (1 → 2 → 3 → 1).
- Свързан — между всеки два върха има път.
- Дърво — свързан граф без цикли. Винаги има точно n−1 ребра.
- Степен на връх — броят на ребрата, които излизат от него. (При насочените: in-degree и out-degree.)
Как се представя граф в код
Има два основни начина да съхраним граф в паметта.
1. Матрица на съседство (Adjacency Matrix)
Двумерен масив n × n, където m[i, j] = 1 ако има ребро i→j, иначе 0. (При тегловен граф — съхраняваме теглото.)
int n = 5;
int[,] m = new int[n + 1, n + 1];
// ребра: 1-2, 1-5, 2-3, 3-4, 4-5, 2-5
m[1, 2] = m[2, 1] = 1;
m[1, 5] = m[5, 1] = 1;
m[2, 3] = m[3, 2] = 1;
m[3, 4] = m[4, 3] = 1;
m[4, 5] = m[5, 4] = 1;
m[2, 5] = m[5, 2] = 1;
// Проверка дали 2 и 4 са съседи:
Console.WriteLine(m[2, 4] == 1); // False2. Списък на съседство (Adjacency List)
За всеки връх пазим списък/множество от съседите му.
using System.Collections.Generic;
var graph = new Dictionary<int, HashSet<int>>();
void AddEdge(int a, int b)
{
if (!graph.ContainsKey(a)) graph[a] = new HashSet<int>();
if (!graph.ContainsKey(b)) graph[b] = new HashSet<int>();
graph[a].Add(b);
graph[b].Add(a); // за насочен граф махаме този ред
}
AddEdge(1, 2);
AddEdge(1, 5);
AddEdge(2, 3);
AddEdge(3, 4);
AddEdge(4, 5);
AddEdge(2, 5);
// Съседите на връх 2:
foreach (var n in graph[2])
Console.Write(n + " "); // 1 3 5 (или в друг ред)Кое да ползваш
| Adjacency Matrix | Adjacency List | |
|---|---|---|
| Памет | n × n (винаги много) | пропорционална на броя ребра |
| Проверка „има ли ребро?" | O(1) — мигновено | O(степен) — обхождане |
| Обхождане на съседите | O(n) — за всеки потенциален съсед | O(степен) — само истинските |
| Кога да ползваш | Малки графи (n < 1000) с много ребра | Големи разредени графи (повечето практически) |
Съвет
В повечето училищни и реални задачи списъкът на съседство е по-добрият избор. Затова го ползваме в следващия урок за обхождане.
Степен на връх
Степента на връх е броят на ребрата, излизащи от него. За графа от Фиг. 1:
| Връх | Съседи | Степен |
|---|---|---|
| 1 | {2, 5} | 2 |
| 2 | {1, 3, 5} | 3 |
| 3 | {2, 4} | 2 |
| 4 | {3, 5} | 2 |
| 5 | {1, 2, 4} | 3 |
Ключово
Свойство (ръкуване): Сумата на степените във всеки ненасочен граф = 2 × (брой ребра). Защото всяко ребро добавя 1 към степента на двата си края.
Дървото като специален граф
Дървото е свързан ненасочен граф без цикли. Има няколко еквивалентни дефиниции:
- Свързан граф с точно n−1 ребра, ако има n върха.
- Между всеки два върха има точно един път.
- Премахването на което и да е ребро прави графа несвързан.
Дърветата ще ги изучаваме отделно — но добре е да знаеш, че всяко „дърво" в програмирането (HTML DOM, файлова система, BST, AST) е специален граф.
Какво трябва да запомниш
- Граф = върхове + ребра. Моделира връзки от реалния свят.
- Видове: насочен/ненасочен, тегловен/нетегловен, цикличен/ацикличен.
- Две представяния: матрица (бърза проверка, много памет) или списък (малко памет, бавна проверка).
- За практика ползваме
Dictionary<int, HashSet<int>>— списък на съседство. - Степента е броят съседи; сума на степените = 2 · брой ребра.
- Дървото е свързан граф без цикли с n−1 ребра.