Какие проблемы могут быть решены или решены более легко, используя графики и деревья?
=====================================================================================

Каковы наиболее распространенные проблемы, которые могут быть решены с обеими этими структурами данных?

Было бы хорошо для меня, чтобы иметь также рекомендации по книгам, что:

* Реализовать структуры
* Реализовать и объяснить рассуждения алгоритмов, которые используют их

 

Первое , что я думаю о том, когда я прочитал этот вопрос: *какие типы вещей использовать графы / деревья?* и я думаю , что в обратном направлении , как я мог бы использовать их.

Например, возьмем два общих использования дерева:

* DOM
* Файловые системы

DOM и XML по этому вопросу, напоминают древовидные структуры.   

![альтернативный текст](https://i.stack.imgur.com/bk5RY.gif)

Это имеет смысл, тоже. **Это имеет смысл , так как нужно эти данные должны быть организованы** . Файловая система тоже. В системе UNIX существует корневой узел, и ветвление вниз. При установке нового устройства, вы прикрепив ее на дерево.

Вы также должны спросить себя: ли данные попадают в этот тип структуры? Создание структуры данных, которые имеют смысл к проблеме, а остальные будут следовать.

Насколько быть проще, я думаю, вот родственник. Вы хорошо с рекурсивными функциями для обхода дерева / графа? Что делать, если вам нужно, чтобы сбалансировать дерево?

Подумайте о программе, которая решает головоломки слова для поиска. Вы можете отобразить все буквы слова поиска в графе и проверить окружающие узлы, чтобы увидеть, если эта строка соответствует любому из слов. Но не могли бы вы сделать то же самое с с одним массивом? Все, что вам действительно нужно сделать, это переместить указатель проверить письма слева и справа, и по ширине, чтобы проверить выше и ниже буквы. Решение этой проблемы с графиком не сложно, но это может создать много дополнительной работы и трудности, если вы не знакомы с их помощью - конечно, что не должно препятствовать вам делать это, особенно, если вы изучаете о их.

Я надеюсь , что поможет вам думать об этих структурах. Что касается книги рекомендации, я должен был бы пойти с **[Введение в алгоритмы](http://rads.stackoverflow.com/amzn/click/0262032937)** .

 

Принципиальные схемы.

Компиляция (Directed ациклические графы)

Карты. Очень компактный в виде графиков.

Проблемы с сетевым потоком.

Решение *деревьев* для экспертных систем (SIC)

Диаграммы Fishbone для поиска неисправностей, процесс Improvment, анализ безопасности. Для бонусных баллов, реализовать код ошибки восстановления в качестве объектов, *которые* диаграмма елочки. 

 

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

 

[Руководство Алгоритм Design](http://rads.stackoverflow.com/amzn/click/0387948600) содержит некоторые интересные исследования с творческим использованием графов. Несмотря на свое название, книга очень читаемый и даже развлекательное время от времени.

 

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

Они также часто используют деревья для представления объектов в пределах мира. Если у вас есть тысячи лиц , и нужно найти один в определенном положении , то итерация линейно через список может быть неэффективной, особенно если вам нужно сделать , это часто. Поэтому область может быть подразделена на дерево , чтобы позволить ему искать более быстро. Подобно тому , как линейное пространство может быть эффективно ищутся с бинарным поиском (и , таким образом , делится на бинарное дерево), 2D пространство можно разделить на [квадрадерево](http://en.wikipedia.org/wiki/Quadtree) и 3D пространство в [октодерево](http://en.wikipedia.org/wiki/Octree) .

 

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

Кроме того, графики и дерева являются хорошим способом для моделирования многих проблем искусственного интеллекта.

 

@DavidJoiner / всего:

FWIW: Новая версия [Руководства Алгоритм проектирования](http://rads.stackoverflow.com/amzn/click/1848000693) в любой день выйдет.

Весь курс, что он профессор Skiena разработал эту книгу также можно найти на веб-сайте:

<http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html>

 

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

графы сцен обычно имеют несколько слоев и атрибуты, которые означают, что вы можете сделать только некоторый узел графа (атрибуты) в определенном порядке (слои). В зависимости от вида графа сцены у вас есть он может иметь две parralel структуры: декларации и создание экземпляров. Th

 

[Алгоритмы Java: Часть 5](http://rads.stackoverflow.com/amzn/click/0201361213) Роберт Седжвик все о графовых алгоритмов и datastructures. Это была бы хорошая первая книга работать через , если вы хотите реализовать некоторые алгоритмы графа.

 

Там есть конечно такие вещи в моем университете: [CSE 326](http://www.cs.washington.edu/education/courses/326/) . Я не думаю , что эта книга была слишком полезной, но проекты весело и научить вас изрядную немного о реализации некоторых из более простых структур.

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