Comments 10
Все беды программистов с графами начинаются с того, что преподают им их люди, искренне верящие в то, что деревья растут ветвями вниз, как на примере выше и ниже :]
У дерева нет цикла , только путь.
Я думаю программисты и так в курсе. Они могут представить данные так как им удобнее будет их использовать.
Но я так понял что иногда, некоторые математики, считают что без них и теории графов программисты не справятся :). И так же не смогут посмотреть пересечение двух коллекций без теории множеств. Без математики никуда.
Очень понравилось - сама тема и то, как написано. Раньше в сон тянуло от всех этих множеств и O(n), но со временем стала интересна эта тема - увы, спустя годы программирования без математики, теории алгоритмов и структур данных становится скучно и сложно решать действительно интересные и масштабные задачи. Буду ждать второй статьи по алгоритмам с графами, и ещё было бы очень приятно видеть изображения с визуализацией (если уж совсем выразить предпочтения - то хотелось бы цветные изображения). Спасибо за интересный материал.
Нет никакой теории по графам, есть теория графов :) удивительная безграмотность!
спасибо, интересно, тема графов интересная, наблюдать как это работает интересно ), хотя вроде и нет в этом ничего такого, нпц в 3д ходють прям как в скайриме ), автопуть вот это вот всё это тоже графы поидее, одного графа с рандомным броском поиска в ограниченном пространстве достаточно, чтобы нпц зажили прям - это удивительно
Деревом, называется связанный неориентированный граф без циклов.
Это не совсем точное определение, так как дерево это иерархическая структура. То есть, чтобы вписать эту иерархичность в графы, можно определить дерево как ориентированный граф с исходящими из корня ребрами, где каждый узел кроме корня имеет одно входящее ребро - который, будучи представлен как неориентированный, является связанным и ациклическим.
Ошибка при заполнении матрицы смежности:
vector<vector<int>> g(n+1, vector<int>(n+1, INF));
for (int i = 1; i <= n; i++) g[i][i] = 0; Выше матрица заполненяется сначала INF, затем обнуляются диагональные элементы, а далее заполняются значения по ребрам - то есть по остальным ячейкам останется INF.
Правильно было бы так:
vector<vector<int>> g(n+1, vector<int>(n+1, 0));При этом занулять диагональ уже не нужно.
Ну и чуть эффективнее было бы индексировать вершины в матрице с нуля, а не с единицы - но это уже мелочи.
Теория графов для программистов