Как Netflix рекомендует вам фильмы?
Вы когда-нибудь задумывались, как netflix рекомендует фильмы? Как Facebook/LinkedIn показывает людям, которых вы знаете, рекомендации? Простой ответ — структура данных Graph. Графы — это способ представления связи между определенными объектами с конечным числом узлов. По сути, узлы и соединения вместе составляют граф. И этот график полностью отличается от графика, который мы изучали в математике. Графики используются для рекомендаций в социальных сетях, алгоритмов отображения и маршрутизации и других оптимизаций.
ключевые слова, используемые в графиках, приведены ниже.
Вершина: узел или указатель, из которого формируется граф.
Край: соединение между узлами является краем.
Невзвешенные графики: невзвешенные графики не имеют никакой ценности.
Взвешенные графики: с ними связаны значения.
Ориентированные графы. Графы, имеющие одностороннее направление между вершинами и не могущие пройти, называются ориентированными графами.
Неориентированные графы: графы, имеющие двустороннее направление между вершинами, больше похожие на двусторонние маршруты, называются неориентированными графами.
Способы представления графиков
Матрицы смежности. Матрицы смежности представляют собой матрицу N*N, где каждое истинное значение указывает на связь между двумя вершинами.
Списки смежности: в списках смежности каждый узел будет хранить смежные вершины в списке.
Обход графика
Обход графов означает проверку или обновление каждого узла в графе. Это помогает найти кратчайший путь, GPS-навигацию, ближайшие совпадения и многое другое. Ниже приведены два распространенных способа обхода графа;
Поиск в глубину (DFS). При поиске в глубину мы начинаем с одного корневого узла и углубляемся в одно соединение, прежде чем посетить другие соединения. Здесь мы сначала идем вглубь, а затем идем вширь. DFS использует структуру данных стека, чтобы отслеживать следующее место для посещения. Этот алгоритм подходит, когда целевой узел находится далеко от источника.
Даже на приведенной выше диаграмме показано двоичное дерево поиска, оно дает представление о том, как работает DFS. Все деревья являются графами, но не все графы являются деревьями. Данная древовидная диаграмма дает краткое представление о том, как работает DFS. Он сосредоточится на одном корневом узле, т.е. «A», затем перейдет к своему брату «B», а затем к своим дочерним узлам «D» и «E». После этого он станет широким, то есть «C» и его дочерние «F» и «G».
Поиск в ширину (BFS). При поиске в ширину мы фокусируемся на корневом узле и его дочерних узлах, прежде чем переходить к их дочерним узлам. Здесь мы сначала расширяемся, а затем углубляемся. BFS использует структуру данных очереди, чтобы отслеживать следующее место для посещения. Этот алгоритм подходит, когда целевой узел находится ближе к Источнику.
Данная древовидная диаграмма дает краткое представление о том, как работает BFS. Он сосредоточится на одном корневом узле, то есть «A», затем перейдет к своим родным «B» и «E». После этого он пройдет через своего потомка «C», «D» и «F», «G» в ширину, а затем в глубину.
