Лучшие graph-theory вопросы ИТ разработчиков

  • 5 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Можно ли хранить графики hbase? если да, то как вы моделируете базу данных для поддержки структуры графа?

Я играл с использованием графиков для анализа больших данных. Он работал отлично и действительно весело, но мне интересно, что делать, когда данные становятся все больше и больше? Дайте мне знать, если есть какое-то другое решение, но я подумал ...

Задан 26 Mar 2012, 01:54 от Error_404
  • 2 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Хм, я не уверен, как вы собираетесь использовать массив. Обратите внимание, что мы можем извлечь первый элемент из очереди и вставить его в постоянное время. Если бы вы искали в массиве любую запись, которая имеет значение undegree = 0, вы могли бы использовать O (n) время. Это больше вопрос эффективности.

омашней работы теории графов я попросил вычислить (и)Критические маршруты Маршруты [http://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique]и временной провал проекта в следующем формате: Запись: первой строкой ввода будет целое ...

Задан 15 May 2011, 08:15 от franvergara66
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Путь без цикла ко всем узлам

Существует ли алгоритм или набор алгоритмов, которые позволили бы вам найти кратчайшее расстояние ходьбы от произвольного начального узла, чтобы каждый узел ...

Задан 01 Mar 2010, 21:54 от Jon
  • 7 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

алгоритм перечисления всех возможных путей

Рассмотрим следующий график:Я пытаюсь найти способ перечислить все возможные пути от исходного узла до целевого узла. Например, от А до Е у нас есть следующи...

Задан 12 Oct 2010, 12:48 от dcp
  • 8 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Есть ли более быстрые алгоритмы, чем Дейкстра?

Имеют ли ориентированный связный граф только с положительными весами ребер, есть ли более быстрые алгоритмы для нахождения кратчайшего пути между двумя верши...

Задан 09 Nov 2009, 13:16 от Dave O.
  • 8 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Определить, имеет ли данный взвешенный граф уникальный MST

m ищет алгоритм (или любой другой способ), чтобы определить, имеет ли данный взвешенный граф уникальный MST (минимальное связующее дерево) в O (ElogV)?Я неМы...

Задан 25 Jun 2013, 19:29 от TomerGod
  • 4 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Алгоритм раздачи бус головоломки (2)

Допустим, у вас есть круг (показанный ниже) сN слоты.Ваша цель состоит в том, чтобы в каждом слоте было определенное количество бусин, и у вас есть массив ра...

Задан 21 Feb 2016, 17:48 от Bob Billy
  • 10 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Не понимаю эвристику ближайших пар из «Руководства по разработке алгоритмов»

Там почти точно так жевопрос, Но я все еще не понимаю, как работает эта эвристика и в какой последовательности проходят вершины. Также в книге есть картинка:...

Задан 23 May 2017, 11:55 от Communitydhblah
  • 7 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

@becko: только что заметил ошибку! y (i) должно быть суммой (max (x (j), y (j))) для каждого дочернего элемента j из i, поскольку мы хотим только разрешить, а не требовать, чтобы дочерние элементы были включены в независимый набор.

роблема из книги Алгоритмы Вазирани Вход в эту задачу - дерево T с целочисленными весами по краям. Веса могут быть отрицательными, нулевыми или положительными. Дайте линейный алгоритм времени, чтобы найти кратчайший простой путь в T. Длина пути ...

Задан 12 Feb 2011, 08:22 от user467871
  • 1 голос
  • 1 ответ
  • 0 просмотров
1 ответ

/home/b/bowu/boost_1_66_0/boost/graph/detail/adjacency_list.hpp:2550:53: ошибка: формирование ссылки на void <Graph, value_type, const_reference, Tag> const_type; ^

тоящее время я работаю над проектом проблемы словесности, и я уже построил график для хранения в нем всех словарных слов и добавил в него ребра, я сделал это с помощью библиотеки графов буста. Но меня смущает то, чтоbreadth_first_search() ...

Задан 27 Nov 2017, 19:56 от Boooooo
  • 68 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Найти кратчайший путь в графе, который посещает определенные узлы

У меня есть неориентированный граф с около 100 узлов и около 200 ребер. Один узел помечен как «начало», другой - как «конец», а дюжина помечена как «mustpass». Мне нужно найти кратчайший путь через этот график, который начинается в начале ...

Задан 21 Oct 2008, 16:01 от dmd
  • 2 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

 дает ограничение времени выполнения, которое является полиномиальным по длине кодирования графа; это означает, что поиск в ширину, в общем, не может генерировать все возможные пути от данного источника к данному терминалу. Кроме того, если граф содержит цикл, число путей может быть бесконечным посредством повторения цикла.

тоящее время я пытаюсь пройти все пути от источника до места назначения в графе, который использует матрицу смежности. Я пытался сделать это способом BFS. Спасибо за помощь. Я получаю только один путь. Как мне распечатать другие пути? public ...

Задан 09 Feb 2018, 05:09 от Anish
  • 9 голосов
  • 9 ответов
  • 0 просмотров
9 ответов

веб-API

аюсь нарисовать график на веб-странице ASP. Я надеюсь, что API может быть полезным, но пока я не смог его найти. График содержит помеченные узлы и немаркированные направленные ребра. Идеальный результат будет что-то вродеэто ...

Задан 16 Sep 2008, 03:55 от Kenn
  • 21 голос
  • 7 ответов
  • 0 просмотров
7 ответов

Образец ориентированного графа и код топологической сортировки [закрыто]

Кто-нибудь знает, где я могу получить пример реализации направленного графа и пример кода для выполнения топологической сортировки на ориентированном графе? ...

Задан 29 Apr 2010, 17:20 от user63904
  • 30 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

@DBedrenko Потому что, если вы рисуете его прямо, он пересечет ранее нарисованные линии. Я считаю, что кривая заставляет его выглядеть немного лучше. В строке, последней для последней, измените последний параметр draw_arrow на 0, если вы хотите, чтобы он был прямым.

ющий псевдокод взят из первой главы онлайн-версии предварительного просмотраРуководство по разработке алгоритма (страница 7 отэтот PDF [http://www.cs.sysu.edu.cn/~lxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf] ). Пример ошибочного ...

Задан 27 Aug 2011, 19:14 от ClosureCowboy
  • 24 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Как мне запустить graphx с Python / pyspark?

Я пытаюсь запустить Spark graphx с Python, используя pyspark. Моя установка кажется правильной, так как я в состоянии запустить учебники pyspark и (Java) Gra...

Задан 25 Apr 2014, 20:18 от Glenn Strycker
  • 39 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Построить минимальное связующее дерево, охватывающее определенное подмножество вершин

У меня есть неориентированный график с положительным краем(V, E) для которого я хочу минимальное связующее дерево, охватывающее подмножествоk вершинV (проблема дерева Штейнера). Я не ограничиваю размер связующего дереваk вершины; скорее я точно ...

Задан 07 Oct 2011, 09:21 от atp
  • 43 голосов
  • 8 ответов
  • 0 просмотров
8 ответов

Ему не нужен кратчайший путь, ему нужно «найти пути между двумя заданными узлами».

м, у меня есть узлы, связанные нижеуказанным способом, как мне узнать количество путей, существующих между заданными точками, и детали пути? 1,2 //node 1 and 2 are connected 2,3 2,5 4,2 5,11 11,12 6,7 5,6 3,6 6,8 8,10 8,9 Найдите пути от 1 до ...

Задан 03 Apr 2009, 11:09 от yesraaj
  • 8 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Алгоритм решения этой загадки?

Допустим, у вас есть круг (как показано ниже) сN пятна, и у вас естьN шарики распределены в слотах.Вот пример:Каждый шарик может быть перемещен по часовой ст...

Задан 21 Feb 2016, 01:29 от Bob Billy
  • 65 голосов
  • 7 ответов
  • 0 просмотров
7 ответов

Какая структура данных графа наиболее эффективна в Python? [закрыто]

Мне нужно уметь манипулировать большим (10 ^ 7 узлов) графом в Python. Данные, соответствующие каждому узлу / ребру, минимальны, скажем, небольшое количество...

Задан 22 Mar 2017, 17:42 от Dominique Fortinbgoncalves
  • 16 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Что подразумевается под диаметром сети?

Диаграмма показана наэта ссылка из &quot;Граф с 6 вершинами и 7 ребрами, где крайняя левая вершина № 6 является листовой вершиной или подвесной вершиной.&quo...

Задан 04 Jul 2010, 12:04 от user287745
  • 15 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Названия алгоритмов обхода графа

То, что я ищу, - это исчерпывающий список алгоритмов обхода графа с кратким описанием их назначения в качестве отправной точки для их исследования. До сих по...

Задан 02 Jul 2009, 08:32 от Ben Lakey
  • 6 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Библиотека графов для Какао [закрыто]

Есть ли хорошая библиотека для какого-то графического приложения? Я хочу создать узлы, добавить взвешенные ребра и т. Д. РЕДАКТИРОВАТЬМне нужен график (как на картинке ниже), а не график.

Задан 06 Mar 2012, 11:57 от Uko
  • 5 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Кратчайшие два непересекающихся пути между двумя указанными вершинами

Дан взвешенный неориентированный графG и две вершиныa, bмы хотим найти два путиa -&gt; b а такжеb -&gt; a так что они не имеют общего ребра и так, чтобы сумм...

Задан 09 Aug 2012, 09:50 от Chris
  • 9 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Если я топологически сортирую DAG, могу ли я отбросить половину матрицы смежности?

Я думаю, что я понял конкретную ситуацию, как описано ниже, но мне не хватает теоретических знаний, чтобы провести доказательство, и я не смог найти источник, который упоминает это. Если мое понимание правильное, я могу сэкономить ...

Задан 22 Apr 2009, 14:52 от Hanno Fietz
  • 7 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

это невозможно за полиномиальное время, так как, по возможности, мы могли бы использовать это, чтобы найти все циклы и, следовательно, цикл наибольшей длины, что подразумевает, что мы можем полностью решить проблему гамильтоновых циклов за полиномиальное время.

у меня есть неориентированный график, как я могу получить список всех циклов? Например, из следующего, из-за графика, я бы хотел циклы: (a,b,d,e,c) (a,b,c) (b,d,e)

Задан 21 Feb 2011, 15:54 от YXD
  • 51 голос
  • 4 ответа
  • 0 просмотров
4 ответа

C # графическая библиотека рисования? [закрыто]

Я ищу (бесплатную) библиотеку, которая позволяет мне рисоватьCFG [http://en.wikipedia.org/wiki/Control_flow_graph](график управления потоком). Что-то вродеyFiles [http://yworks.com/], но бесплатно или желательно с открытым исходным кодом? В ...

Задан 10 Apr 2009, 14:23 от newgre
  • 169 голосов
  • 10 ответов
  • 0 просмотров
10 ответов

Крускал против Прим

Мне было интересно, когда следует использоватьАлгоритм Прима и когдаКрускала & APOS; s найти минимальное остовное дерево? Они оба имеют простую логику, одина...

Задан 06 Jul 2012, 20:20 от templatetypedef
  • 51 голос
  • 12 ответов
  • 0 просмотров
12 ответов

Хороший алгоритм для нахождения диаметра (разреженного) графика?

У меня есть большой, связанный, разреженный граф в форме списка смежности. Я хотел бы найти две вершины, которые как можно дальше друг от друга, то естьдиаме...

Задан 06 Jan 2010, 18:58 от Lance RobertsA. Rex
  • 1 голос
  • 1 ответ
  • 0 просмотров
1 ответ

@Mike Constraint 2c также необходимо изменить. Но я не проверял целевую функцию, потому что она не должна влиять на осуществимость.

аюсь исправить некоторые ограничения для проблемы окраски графа, используя networkx и gurobi. Для каждого i ∈ V определим следующий набор интервалов. Каждый интервал [l, u] ∈ Ii представляет возможную пару минимального цвета l и максимального ...

Задан 12 Nov 2018, 13:48 от Mike
  • 13 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Разработка интерфейса, вдохновленного Yahoo Pipes [закрыто]

Мне очень нравится интерфейс для Yahoo Pipes (http://pipes.yahoo.com/pipes/ [http://pipes.yahoo.com/pipes/]) и хотел бы создать аналогичный интерфейс для другой проблемы. Существуют ли библиотеки, которые позволили бы мне создать интерфейс с ...

Задан 17 Sep 2008, 18:53 от sutee
  • 6 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Java-реализация с нуля для хеминформатики

алАлгоритм VF2 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf] для нахождения, если два графа изоморфны, но мне как-то не хватает общей картины. Возможно, мне не хватает соответствующего фона в этой области, ...

Задан 19 Jul 2011, 07:52 от Legend
  • 4 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Как мне найти кратчайший путь, который охватывает все узлы в ориентированном циклическом графе?

Мне нужен пример кратчайшего пути ориентированного циклического графа от одного узла (он должен достигать всех узлов графа от узла, который будет входным). Пожалуйста, если есть пример, он мне нужен в C ++ или в алгоритме.

Задан 25 Apr 2009, 15:36 от Thaier Alkhateeb
  • 38 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

В чем разница между разреженными и плотными графами?

Я прочитал, что это идеально для представления разреженных графов списками смежности и плотных графов матрицей смежности. Но я бы хотел понять главное различ...

Задан 26 Sep 2012, 07:56 от Geek
  • 12 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Топологическая сортировка циклического графа с минимальным количеством нарушенных ребер

Я ищу способ выполнить топологическую сортировку для данного ориентированного невзвешенного графа, который содержит циклы. Результат должен содержать не толь...

Задан 17 Jun 2013, 11:01 от orsg
  • 50 голосов
  • 15 ответов
  • 0 просмотров
15 ответов

На графике: A-B, B-C, A-C, D, E мы имеем | V | = 5 и | E | = 3, так что ваше условие выполняется 3 <5 - 1, даже если оно имеет цикл A-B-C-A

еориентированный графGзнак равноV, E) с участиемn вершины (|V| знак равноn), как вы найдете, если он содержит цикл вO(n)?

Задан 08 Feb 2009, 20:44 от Eran Kampf
  • 4 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Нахождение полигонов в неориентированном графе

Пожалуйста, смотрите изображение:http://i.stack.imgur.com/NPUmR.jpg [https://i.stack.imgur.com/NPUmR.jpg] У меня есть неориентированный граф, который содержит один или несколько связанных подграфов. Граф определяется набором упорядоченных пар ...

Задан 21 Mar 2012, 11:54 от Dev.D
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Если вам нужно больше места и эффективности, сожмите каждое значение (которое может быть строкой JSON ...) и распакуйте / импортируйте / десериализуйте в своем клиентском коде.

наилучший способ реализации взвешенного графика с использованием Redis? В основном мы будем искать кратчайшие пути по графу (возможно, используя алгоритм Дейкстры) В настоящее время мы рассмотрели добавление ребер в Redis Для каждого узла мы ...

Задан 18 Jun 2011, 20:09 от DuduAlul
  • 8 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Как я могу доказать концепцию «шести степеней разделения» программно?

У меня есть база данных 20 миллионов пользователей и связей между этими людьми. Как я могу доказать концепцию «Шесть степеней разделения»наиболее эффективным способомв программировании? ссылка на статью о шести степенях ...

Задан 12 Jun 2009, 20:38 от Roman Kagan
  • 4 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

В идеале был бы способ создать автономный HTML-файл, который содержал бы XML и XSLT, но я не знаю ни одного ... который сам по себе является вопросом.

долгого цикла обучения через XAML я вернулся к HTML и javascript и понял, что концепция декларативного кода - с точки зрения правил преобразования - является невероятно мощной концепцией. Несмотря на избыток синтаксиса, XSLT-обработка XML ...

Задан 28 Mar 2009, 21:52 от Phil H
  • 2 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Facebook График поиска: алгоритм поиска информации

Есть закрытый вопрос под названием "Как работает поиск по графику в Facebook? [https://stackoverflow.com/questions/14498507/how-does-facebook-graph-search-work] " Проще говоря, ОП спросил (и даже дал пример того, что он пытался): Как работает ...

Задан 14 Feb 2013, 11:22 от Yavar
  • 19 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Генерация большого случайного плоского графа

Каков наиболее эффективный способ генерации большого (~ 300 тыс. Вершин) случайного плоского графа («случайный» здесь означает равномерно распределенный)?

Задан 12 Jul 2010, 20:33 от viaclectic
  • 9 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Спасибо, сегодня утром я потратил некоторое время, чтобы просмотреть это, и я не уверен, что он действительно сделает то, что мне нужно. Документация очень легкая, и пример требует, чтобы я запустил CouchDB и node.js. Так как все, что мне действительно нужно, это простой обход дерева, я думаю, что я мог бы свернуть свой собственный, но если я все же использую data.js, я вернусь и отметлю это как ответ.

я есть набор данных, который лучше всего представлен графиком. Он состоит из узлов 6 или 7 разных «типов» с направленными ребрами (зависимости друг от друга, гарантированно не имеющие циклических зависимостей). Набор данных по сути является ...

Задан 29 Jul 2011, 17:59 от AG.
Page 1 of 2
1 2