VKGraph

Go-сервис для поиска кратчайшей цепочки знакомств между двумя пользователями VK через граф друзей и двусторонний BFS.

VK API · Алгоритм · API · Быстрый-старт

---

О проекте

VKGraph — небольшой backend-проект на Go, который работает с социальным графом VK.

Пользователь вводит два VK ID, сервис получает списки друзей через VK API и ищет кратчайший путь между людьми: кто через кого связан. По сути, это мини-версия идеи «теории шести рукопожатий», но поверх реального графа друзей.

Проект, на мой взгляд, интересен тем, что здесь есть не просто CRUD или работа с API, а реальная алгоритмическая задача: обход графа с внешними API-вызовами, восстановление пути и отдача результата через HTTP.

---

Что реализовано

• подключение к VK API через access token;
• получение списка друзей пользователя;
• получение информации о пользователях: имя, ссылка, аватар, пол;
• поиск кратчайшего пути между двумя пользователями VK;
• двусторонний BFS для ускорения поиска;
• восстановление найденного пути;
• HTTP API на Go;
• простой web-интерфейс для ввода двух ID;
• базовые тесты для графовой логики и VK client слоя.

---

Как это работает

VK ID A + VK ID B
        ↓
Backend получает друзей A и B через VK API
        ↓
Запускается bidirectional BFS
        ↓
Поиск идет одновременно от A и от B
        ↓
Когда фронты поиска пересекаются — путь найден
        ↓
Backend восстанавливает цепочку пользователей
        ↓
Frontend показывает кратчайший путь

---

Архитектура

flowchart TD
    A["Web UI"] --> B["Go HTTP Server"]
    B --> C["gorilla/mux router"]

    C --> D["/friends/{userID}"]
    C --> E["/friends/{userIDa}/{userIDb}"]
    C --> F["/friends/info/{userIDa}/{userIDb}"]

    D --> G["VK client"]
    E --> H["Bidirectional BFS"]
    F --> H

    H --> G
    G --> I["VK API"]

    H --> J["Shortest path: IDs"]
    F --> K["User details"]
    K --> L["JSON response"]

Loading

---

Алгоритм

Обычный BFS от одного пользователя может быстро стать тяжелым: социальный граф широкий, у каждого пользователя могут быть сотни друзей, а каждый шаг требует внешних API-вызовов.

Поэтому используется двусторонний BFS:

start user → → →
               встреча
end user   ← ← ←

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

В проекте это вынесено в отдельную графовую логику:

• bidirectionalSearch — основной поиск;
• bfsStep — один шаг BFS;
• mergePaths — склейка двух половин пути;
• backtrace — восстановление маршрута по map предыдущих вершин.

---

API

Получить друзей пользователя

GET /friends/{userID}

Возвращает список друзей пользователя с базовой информацией.

Найти кратчайший путь между двумя пользователями

GET /friends/{userIDa}/{userIDb}

Возвращает путь как список VK ID.

Найти путь с деталями пользователей

GET /friends/info/{userIDa}/{userIDb}

Возвращает путь с именами, аватарами и ссылками на профили.

Пример ответа:

[
  {
    "id": 1,
    "name": "User A",
    "source": "https://vk.com/id1",
    "photo": "https://...",
    "sex": 2
  },
  {
    "id": 2,
    "name": "Mutual Friend",
    "source": "https://vk.com/id2",
    "photo": "https://...",
    "sex": 1
  },
  {
    "id": 3,
    "name": "User B",
    "source": "https://vk.com/id3",
    "photo": "https://...",
    "sex": 1
  }
]

---

Стек

Область	Технологии
Язык	Go 1.22
HTTP router	gorilla/mux
VK integration	SevereCloud/vksdk
Config	godotenv, .env
Algorithm	bidirectional BFS
Frontend	HTML, CSS, JavaScript

---

Структура проекта

.
├── main.go              # запуск сервера, маршруты, static files
├── go.mod               # Go module и зависимости
├── src/
│   ├── graph.go         # bidirectional BFS и восстановление пути
│   ├── handlers.go      # HTTP handlers
│   ├── models.go        # модели ответа
│   ├── vk_client.go     # работа с VK API
│   ├── graph_test.go    # тесты графовой логики
│   └── vk_client_test.go
└── static/
    ├── index.html       # web-форма
    ├── script.js        # запросы к backend
    └── style.css

---

Быстрый старт

1. Клонировать репозиторий

git clone https://github.com/Optoed/VKGraph.git
cd VKGraph

Сейчас основной код находится в ветке visual. Если GitHub открывает не ее, переключись:

git checkout visual

2. Создать .env

ACCESS_TOKEN=your_vk_access_token_here

Токен нужен для запросов к VK API.

3. Установить зависимости

go mod download

4. Запустить сервер

go run main.go

Сервер запускается на:

http://localhost:8081

---

Пример использования

Через браузер:

http://localhost:8081

Через HTTP API:

curl http://localhost:8081/friends/info/USER_ID_A/USER_ID_B

Где USER_ID_A и USER_ID_B — числовые VK ID пользователей.

---

Важные ограничения

• VK API может ограничивать количество запросов;
• закрытые профили и приватные списки друзей могут ломать полноту графа;
• поиск по большому социальному графу может быть медленным без кэша;
• проект рассчитан на исследование графовой логики и интеграции с VK API, а не на production-нагрузку.

---

Что можно улучшить дальше

• добавить кэширование друзей, чтобы не дергать VK API повторно;
• добавить лимит глубины поиска;
• добавить rate limiting и обработку ошибок VK API;
• визуализировать путь как граф, а не только как список;
• добавить Dockerfile;
• добавить Swagger/OpenAPI;
• улучшить frontend: карточки пользователей, аватары, ссылки, loader;
• добавить хранение уже найденных путей.

---

Авторство

Проект создан как развлекательная практическая работа с Go, VK API и алгоритмами на графах.

---

Лицензия

MIT License.