Граф вызывает большой интерес к информатике, а также к исследованиям недавнего прошлого. С 1980 года, с изобретением Интернета, к этой области, особенно к информатике, возник большой интерес.
С изобретением Интернета они представляют всю Всемирную паутину в виде графика. Таким образом, каждая веб-страница на самом деле является узлом (вершинами), и это ссылка с одной веб-страницы на другую веб-страницу, то есть ребро (ссылки). Теперь всю WWW можно смоделировать в виде графа.
И теперь мы заинтересованы в знании различных свойств этого графа, изучение различных свойств на основе поиска будет актуальным, и время поиска может быть улучшено.
Более того, с изобретением социальных сетей, таких как facebook и другие сайты социальных сетей, на самом деле произошло следующее:
они начали представлять всю эту социальную сеть еще и в виде графа. Если вы человек, вы на самом деле «узел» в графе, и если у вас есть друзья, они также являются узлами в графе, и у вас будет следующая ссылка:
В Facebook они предлагают друзей и показывают, что этот человек может быть вашим другом. Как это возможно?
-Ну, они делают какие-то обходы…
Самое важное в графах — это то, что все проблемы связаны с «обходом» и «поиском». Теперь информация присутствует на графике, и мы должны получить эту информацию. Итак, как мы читаем информацию?
-просто "обходом" или "иском"... просто :)
Теперь проблема заключается в предложениях друзей, с помощью которых они могут увидеть ваших друзей. Итак, как это получить?
решение для этого, если мы обозначим профиль как узел в социальной сети, то что такое список друзей, список друзей есть не что иное, как список смежности (согласно концепции графа). Итак, список смежности в графе равен списку друзей в фейсбуке. понятно!…
и теперь их проблема в том, что вы можете знать человека, которого может знать ваш друг, верно!…
поэтому мы начинаем с определенного узла и пытаемся искать, так как же мы ищем? хммм… , мы ищем в стиле BFS (поиск в ширину).
Он ищет все элементы, которые находятся на расстоянии один. Эти элементы не что иное, как все ваши друзья. Опять ищем все элементы, которые находятся на расстоянии два, это друзья вашего друга и так далее… поняли? НЕТ!
посмотрите на приведенную схему-
пусть E будет вашим профилем, тогда ваши друзья B,G,C, они на расстоянии 1, и A,F,D, на расстоянии 2(друзья ваших друзей). и продолжается….
Если мы попробуем BFS, начнем с узла и попробуем изучить своих друзей, а затем друзей ваших друзей…, тогда вы можете получить людей, которых вы, возможно, знаете. Вот как Facebook будет давать вам предложения.
Модифицированная версия этого.
Есть еще один тип поиска, который называется DFS (поиск в глубину). На самом деле это говорит о том, что вы идете как можно глубже и находите ценность (какого-то человека) их.
скажем, если вы находитесь в Индии, это может остановиться на каком-то человеке в США, и вы можете вообще его/ее не знать. Поэтому DFS здесь не работает.
