Поиск центра диаметра диаграммы с использованием BFS?

Question

Таким образом, эта функция, наибольшая_дист, находит диаметр графика (данный график в задаче всегда дерево).

Вместо этого я хочу найти центр диаметра, узел с наименьшим максимальным расстоянием до всех остальных узлов.

Я «своего рода» понять идею, что мы можем сделать это, находя путь от u к t (расстояние между ut и является диаметр), отслеживая родителя для каждого узла. Оттуда я выбираю узел в середине u и t? Мой вопрос в том, как это реализовать здесь для этой функции? Будет ли это сделать вывод узла 2 для этого графика?

int biggest_dist(int n, int v, const vector< vector<int> >& graph) 
//n are amount of nodes, v is an arbitrary vertex 
{ //This function finds the diameter of thegraph 
int INF = 2 * graph.size(); // Bigger than any other length 
vector<int> dist(n, INF); 

dist[v] = 0; 
queue<int> next; 
next.push(v); 

int bdist = 0; //biggest distance 
while (!next.empty()) { 
    int pos = next.front(); 
    next.pop(); 
    bdist = dist[pos]; 

    for (int i = 0; i < graph[pos].size(); ++i) { 
     int nghbr = graph[pos][i]; 
     if (dist[nghbr] > dist[pos] + 1) { 
      dist[nghbr] = dist[pos] + 1; 
      next.push(nghbr); 
     } 
    } 
} 

return bdist; 
} 

Answer 1

На самом деле эта функция не вычисляет диаметр. Он вычисляет самую удаленную вершину из заданной вершины v.

Для вычисления диаметра дерева, вам нужно сначала выбрать произвольную вершину (скажем v), а затем найти вершину, которая дальше от v (скажем w), а затем найти вершину, которая дальше от w, давайте сядем u. Расстояние между w и u - это диаметр дерева, но расстояние между v и w (что делает ваша функция) не гарантируется как диаметр.

Чтобы ваша функция вычислила диаметр, вам нужно будет вернуть верхушку, найденную рядом с расстоянием. Удобно, что это всегда будет последний элемент, который вы обрабатываете, поэтому просто заставьте свою функцию запомнить последний обработанный элемент вместе с расстоянием до этого элемента и вернуть их оба. Затем дважды вызовите свою функцию, сначала из любой произвольной вершины, затем из вершин, которые возвратил первый вызов.

Чтобы на самом деле найти центр, вы также можете вспомнить родителя для каждого узла во время вашей BFS. Для этого выделить дополнительный массив, скажем prev, и когда вы делаете

dist[nghbr] = dist[pos] + 1; 

также сделать

prev[nghbr] = pos; 

Затем в конце второго вызова функции, вы можете просто сходить bdist/2 раза в предыд, что-то вроде:

center = lastVertex; 
for (int i = 0; i + i < bdist; ++ i) center = prev[center]; 

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

pair<int, int> biggest_dist(int n, int v, const vector< vector<int> >& graph) 
{ 
    int INF = 2 * graph.size(); // Bigger than any other length 
    vector<int> dist(n, INF); 
    vector<int> prev(n, INF); 

    dist[v] = 0; 
    queue<int> next; 
    next.push(v); 

    int bdist = 0; //biggest distance 
    int lastV = v; 
    while (!next.empty()) { 
     int pos = next.front(); 
     next.pop(); 
     bdist = dist[pos]; 
     lastV = pos; 

     for (int i = 0; i < graph[pos].size(); ++i) { 
      int nghbr = graph[pos][i]; 
      if (dist[nghbr] > dist[pos] + 1) { 
       dist[nghbr] = dist[pos] + 1; 
       prev[nghbr] = pos; 
       next.push(nghbr); 
      } 
     } 
    } 

    int center = lastV; 
    for (int i = 0; i + i < bdist; ++ i) center = prev[center]; 

    return make_pair(lastV, center); 
} 

int getCenter(int n, const vector< vector<int> >& graph) 
{ 
    // first call is to get the vertex that is furthest away from vertex 0, where 0 is just an arbitrary vertes 
    pair<int, int> firstResult = biggest_dist(n, 0, graph); 
    // second call is to find the vertex that is furthest away from the vertex just found 
    pair<int, int> secondResult = biggest_dist(n, firstResult.first, graph); 
    return secondResult.second; 
}