28 lines
1.8 KiB
Markdown
28 lines
1.8 KiB
Markdown
#структура_данных
|
||
|
||
![[Pasted image 20250113103523.png]]
|
||
|
||
> Графы используются для моделирования связей между разными объектами. Каждый граф состоит из *узлов* и *ребер*. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются *соседями*.
|
||
|
||
В ненаправленном графе стрелок нет, и каждый из узлов является
|
||
соседом по отношению друг к другу. Например, оба следующих графа
|
||
эквивалентны.
|
||
|
||
![[Pasted image 20250113101326.png]]
|
||
|
||
|
||
Граф, в котором нет ребер, указывающих в обратном направлении, называется [[Дерево (Tree)]].
|
||
|
||
Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются внутренними или внешними соседями.
|
||
|
||
![[Pasted image 20250113102129.png]]
|
||
|
||
Граф с весами называется *взвешенным* графом. Граф без весов называется *невзвешенным* графом.
|
||
|
||
![[Pasted image 20250116202057.png]]
|
||
|
||
Для вычисления кратчайшего пути в невзвешенном графе используется
|
||
[[Поиск в ширину (Breadth-first search)]]. Кратчайшие пути во взвешенном графе вычисляются по [[Алгоритм Дейкстры (Dijkstra's algorithm)]]
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |