CODEWITHSUNDEEP
graphbreadth-first-search
Geir
Geir

Reputation: 59

Finding the center of the diameter of a graphtree using BFS?

So this function, biggest_dist, finds the diameter of a graph(the given graph in the task is always a tree).

What I want it instead to find is to find the center of the diameter, the node with the least maximum distance to all the other nodes.

I "kinda" understand the idea that we can do this by finding the path from u to t (distance between uand tis the diameter) by keeping track of the parent for each node. From there I choose the node in the middle of uand t? My question is how do I implement that for this function here? Will this make it output node 2 for this graph? 

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;
}

Upvotes: 2

Views: 1300

Answers (1)

Ishamael
Ishamael

Reputation: 12795

As a matter of fact, this function does not compute the diameter. It computes the furthest vertex from a given vertex v.

To compute the diameter of a tree, you need first to choose an arbitrary vertex (let's say v), then find the vertex that is furthest away from v (let's say w), and then find a vertex that is furthest away from w, let's sat u. The distance between w and u is the diameter of the tree, but the distance between v and w (what your function is doing) is not guaranteed to be the diameter.

To make your function compute the diameter, you will need to make it return the vertex it found alongside with the distance. Conveniently, it will always be the last element you process, so just make your function remember the last element it processed alongside with the distance to that element, and return them both. Then call your function twice, first from any arbitrary vertex, then from the vertex that the first call returned.

To make it actually find the center, you can also remember the parent for each node during your BFS. To do so, allocate an extra array, say prev, and when you do

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

also do

prev[nghbr] = pos;

Then at the end of the second call to the function, you can just descend bdist/2 times into the prev, something like:

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

So with a little tweaks to your function (making it return the furthest vertex from v and a vertex that is on the middle of that path, and not return the diameter at all), this code is likely to return you the center of the tree (I only tested it on your example, so it might have some off by one errors)

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;
}

Upvotes: 2

Related Questions