Многие объекты окружающей действительности могут быть смоделированы с использованием графов: карта метро, лабиринт, знакомства в соцсетях, возможные ходы в настольной игре — все это графы. Самое простое и частое действие, которое можно сделать с графом — это перебрать его вершины в каком-то порядке. Под катом я бы хотел рассказать про два самых известных алгоритма на графах — об обходах в глубину и в ширину.
Рубрика «графы» - 9
Графы для самых маленьких: DFS и BFS
2013-10-28 в 8:49, admin, рубрики: bfs, dfs, Алгоритмы, графы, метки: bfs, dfs, графы
Структуры данных, PHP. Часть вторая
2013-08-28 в 11:00, admin, рубрики: Dijkstra's algorithm, heap, php, php 5.3, priority queue, война и мир, графы, куча, переводыПродолжаю совмещать приятное с полезным и переводить. Сегодня речь зайдет о кучах (heaps) и графах. Как обычно, материал скорее подойдет новичкам — большая часть информации, если не вся, уже где-то так или иначе освещалась.
В конце прошлой статьи затрагивались деревья, поэтому начнем с кучи, поскольку между кучей и деревьями есть общие корни. Затем перейдем к графам и реализуем алгоритм Дейкстры.
Дебри филогенетики — демонстрация и объяснение
2012-12-31 в 9:24, admin, рубрики: Алгоритмы, биоинформатика, генетика, геномика, геномы, графы, поисковые системы, происхождение видов, эволюция, метки: генетика, геномика, геномы, графы, поисковые системы, происхождение видов, эволюцияДумаю многие ИТ-специалисты интересуются не только программированием, но и вопросами более земными и частенько их можно застать рассуждающими о происхождении человека, разума и т.д. Мы обратимся к самому началу — происхождению видов бактерий. И хотя там есть много узкоспециальных вопросов, сам принцип построения филогенетических деревьев не такой легкий, но захватывающий. О нем то мы и будем говорить.
Чуть ранее я написал статью Систематика прокариот — дальние родственники, где сообщил о грубых результатах и методе их получения. Он несколько не классический, но вполне укладывается в научную парадигму. Достаточно «жесткий» диалог с Davidov, который имел место быть в этой статье, может создать впечатление проблематичности метода о котором я говорю. Но мы потом сели и спокойно обсудили, и подвели некоторые итоги. Суть диалога представляет некоторый интерес и я его вначале частично опубликую.
А затем хочу продемонстрировать один наглядный пример построения дерева «происхождения видов» с помощью моего подхода (назовем его «детерминированный подход»). По сути метод можно обобщить, и тогда он не будет относится только к филогенетике и его можно использовать в других областях, когда нужно граф превратить в дерево, выкинув слабые связи.
MilkyWeb — Graph of Everything
2012-12-23 в 10:57, admin, рубрики: big data, semantic web, графы, онтологии, Семантическая Сеть, социальные сети, Социальные сети и сообщества, я пиарюсь, метки: big data, semantic web, графы, онтологии, социальные сети 
В данной статье я хочу поделиться своими мыслями по поводу способов решения фундаментальных проблем современного Интернета. Хочу описать модель, которая, по моему мнению, может помочь ещё лучше упорядочить знания в интернете, и продемонстрировать свою попытку реализации такой модели.
Читать полностью »
Маленькие секреты больших графов
2012-07-20 в 12:35, admin, рубрики: data mining, Алгоритмы, графы, Программирование, социальные сети, метки: data mining, графы, социальные сети 
Если вам интересно, какие знания можно извлечь из большого массива данных, насколько большими бывают графы и какие задачи по анализу социальных графов предлагают Facebook, Twitter и др., то эта статья именно для вас.
Читать полностью »
Поиск в социальных сетях на основе поведения муравьёв
2012-06-09 в 13:44, admin, рубрики: алгоритм поиска, Алгоритмы, графы, Мадрид, переводы, социальные сети, метки: алгоритм поиска, графы, Мадрид, социальные сети 
Исследователи из Мадридского университета имени Карлоса III (Universidad Carlos III de Madrid, UC3M) разработали алгоритм, основанный на поведении муравьёв при поиске еды. Данный алгоритм, как утверждают авторы, ускоряет поиск связей между элементами социальных сетей.
Читать полностью »