Нахождение центра диаметра графического дерева с помощью BFS?

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

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

Я «отчасти» понимаю идею, что мы можем сделать это, найдя путь от u до t (расстояние между u и t является диаметром), отслеживая родителя для каждого узла. Оттуда я выбираю узел в середине 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;
}

graph breadth-first-search
person Geir    schedule 16.01.2015    source источник
comment
Для деревьев есть симпатичный алгоритм, который вы можете использовать: одновременно удалите все листья в графе и повторяйте это, пока не останется один или два узла. Эти оставшиеся узлы являются центрами. Будет ли это работать для вас, или вы специально хотите работать с приведенным выше кодом?   -  person templatetypedef    schedule 17.01.2015
comment
Э-э... вы могли бы просто рассматривать это как график и преобразовать в глубину от u до t, а затем вернуть диаметр/2 раза. Или, если по какой-то причине это действительно удобнее, как дерево, вы можете укоренить дерево, найти все глубины, а затем найти (диаметр/2)-го родителя нижнего узла... (я думаю?) РЕДАКТИРОВАТЬ: как ваш код найти диаметр графа, кажется, просто найти самое дальнее расстояние от узла v?   -  person flight    schedule 17.01.2015

Ответы (1)


arrow_upward
2
arrow_downward

На самом деле, эта функция не вычисляет диаметр. Он вычисляет самую дальнюю вершину от заданной вершины 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 и вершину, которая находится в середине этого пути, и вообще не возвращать диаметр), этот код, вероятно, вернет вам центр дерева (Я тестировал его только на вашем примере, поэтому он может иметь некоторые ошибки на единицу)

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;
}
person Ishamael    schedule 17.01.2015
comment
Именно тот ответ, который я искал! Благодарю вас! :-) - person Geir; 17.01.2015