найти глубину сетевой цепочки в мультикарте - PullRequest
Новая
       31

найти глубину сетевой цепочки в мультикарте

0 голосов
/ 19 октября 2019

У меня есть программа, которая соединяет 2 человек. Соединение сохраняется в мультикарте как пара ключ-значение. Например, add john tim добавляет Тима как соединение с Джоном, Тим может добавить больше людей, а его связи могут добавить больше людей.

Мне нужно найти глубину подсети человека, то есть самую длинную цепочку найма, начинающуюся с этого человека. Например, учитывая, что следующий набор данных 

> add john mary
> add john tom
> add mary brad
> add tom Maria
> add mary Eli
> add brad Sofia

Depth John должен возвращать 4, поскольку самая длинная цепочка John имеет значение 4.

John -> Mary -> Brad -> sofia (4)

John -> tom -> Maria (3)

и Depth sofia вернут 1, поскольку она сама по себе и не распространяется ни на кого.

Вот что я пытался.

  • для каждого ключа, найдите, сколько существует на карте (используя equal_range)
  • , затем выполните итерацию по этому и для каждого из них, посчитайте их глубину
  • saveглубину как максимальную и сравнивайте ее после каждой итерации и возвращайте максимальную

Вот код. 

void count_depth_recursive(std::multimap<std::string, std::string>networkMap, std::string id, int depth)
{
    for(auto itr = networkMap.begin(); itr != networkMap.end(); ++itr)
    {
      if(itr->first == id)
      {
        ++depth;
        count_recursive(networkMap, itr->second, depth);
      }
    }

}

Функция драйвера. 

int count_depth(std::multimap<std::string, std::string>networkMap, std::string id)
{
    int depth = 0;
    int max = 0;
    auto find = networkMap.equal_range(id);
    for(auto itr = find.first; itr != find.second; ++itr)
        count_depth_recursive(networkMap, itr->first, depth);
        std::cout << depth << std::endl;

    return depth;
}

Я продолжаю получать ноль в качестве ответа, и я начинаю сомневаться в правильности моего подхода к этому.

1 Ответ

0 голосов
/ 19 октября 2019

Вместо использования мультикарты вы можете использовать структуру данных списка смежности для представления графика: unordered_map<string, vector<string>> Adj, где вектор в Adj[person] будет представлять прямые соединения этого человека.

После этого вы можетереализовать алгоритм , чтобы найти самый длинный путь для каждого человека. Временная сложность этого алгоритма составляет O(V+E).

...