В мою задачу входило нахождение цены через маршруты по тикетам.

Например на нашей бирже есть условно монета CAKE, нам необходимо узнать ее стоимость в USDT, однако прямых торгов CAKE/USDT нет, но есть CAKE/BNB и BNB/USDT. Значит нам нужно составить такой маршрут, чтобы получить цену в USDT. В данном примере я применил “Ненаправленный граф”. Где вершинами являются монеты, а ребрами пары. Кодовое представление такого графа можно сделать через “Матрицу смежностей” или “Список смежностей”. Минусом матрицы смежности является то количество памяти которое нужно для хранения информации про граф. Но а список смежностей является более оптимальной с точки зрения использованной памяти, но менее эффективна с точки зрения выполнения операций. Я использовал матрицу смежностей, так как в моем списке всего 50 монет, следовательно это матрица 50х50 с булевыми типами данных, по самой примитивной формуле займет всего 2.5 кб. С запасом на будущее до 500 монет - это 250 кб. Максимально примитивно, но даже с этим условием обработка будет мгновенной, так как одним из условий задачи было максимальный маршрут не больше 2 ребер. Итого: - на вход приходит монета, у каждой монеты есть свой индекс в массивах этой матрицы. - смотрим по по индексам есть ли такой тикер монеты к USDT на бирже. V[m][n], где V - это наша матрица, m - это индекс входящей монеты, n - это индекс токена USDT. - если нет, то используем алгоритм поиска в ширину, проходим циклом по массиву, до тех пор, пока не найдем смежный тикер. Получается, что в лучшем случае, если тикер есть то сложность O(1) - константная, а если нет тикера, то O(n) - что в худшем случае означает, нам нужно проверить каждый узел в матрице. 🔎 Хотите узнать больше о графах и структуры данных? Оставляйте свои вопросы в комментариях! ⚡️