Mencari pusat diameter pohon grafik menggunakan BFS?

Jadi fungsi ini, large_dist, mencari diameter grafik (grafik yang diberikan dalam tugas selalu berupa pohon).

Yang ingin saya temukan adalah menemukan pusat diameter, simpul dengan jarak maksimum terkecil ke semua simpul lainnya.

Saya "agak" memahami gagasan bahwa kita dapat melakukan ini dengan menemukan jalur dari u ke t (jarak antara udan tadalah diameternya) dengan melacak induk untuk setiap node. Dari sana saya memilih simpul di tengah udan t? Pertanyaan saya adalah bagaimana cara menerapkannya untuk fungsi ini di sini? Apakah ini akan menjadikannya output node 2 untuk grafik ini?

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 sumber
comment
Untuk pohon, ada algoritma lucu yang dapat Anda gunakan: hapus semua daun dalam grafik secara bersamaan dan ulangi ini sampai Anda hanya memiliki satu atau dua simpul. Node-node yang tersisa kemudian menjadi pusat. Apakah itu berhasil untuk Anda, atau Anda secara khusus ingin bekerja dengan kode di atas?   -  person templatetypedef    schedule 17.01.2015
comment
Uhh... Anda bisa memperlakukannya sebagai grafik dan dfs dari u ke t lalu mengembalikan diameter/2 kali. Atau jika itu benar-benar lebih nyaman sebagai pohon karena alasan tertentu Anda dapat melakukan root pada pohon, menemukan semua kedalaman dan kemudian menemukan induk (diameter/2) dari simpul bawah... (menurut saya?) EDIT: bagaimana kode Anda carilah diameter grafiknya, sepertinya tinggal mencari jarak terjauh dari node v?   -  person flight    schedule 17.01.2015

Jawaban (1)


arrow_upward
2
arrow_downward

Faktanya, fungsi ini tidak menghitung diameter. Ini menghitung simpul terjauh dari simpul tertentu v.

Untuk menghitung diameter pohon, pertama-tama Anda harus memilih titik sembarang (misalkan v), kemudian cari titik sudut yang terjauh dari v (katakanlah w), lalu cari titik sudut yang terjauh dari w, ayo duduk u. Jarak antara w dan u adalah diameter pohon, namun jarak antara v dan w (apa yang dilakukan fungsi Anda) tidak dijamin menjadi diameternya.

Untuk membuat fungsi Anda menghitung diameter, Anda harus mengembalikan titik sudut yang ditemukan bersamaan dengan jarak. Mudahnya, ini akan selalu menjadi elemen terakhir yang Anda proses, jadi buatlah fungsi Anda mengingat elemen terakhir yang diproses bersamaan dengan jarak ke elemen tersebut, dan kembalikan keduanya. Kemudian panggil fungsi Anda dua kali, pertama dari titik sembarang, lalu dari titik di mana panggilan pertama dikembalikan.

Untuk membuatnya benar-benar menemukan pusatnya, Anda juga dapat mengingat induk untuk setiap node selama BFS Anda. Untuk melakukannya, alokasikan array tambahan, misalnya prev, dan kapan Anda melakukannya

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

juga melakukan

prev[nghbr] = pos;

Kemudian di akhir panggilan kedua ke fungsi tersebut, Anda cukup turunkan bdist/2 kali ke sebelumnya, seperti:

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

Jadi dengan sedikit penyesuaian pada fungsi Anda (membuatnya mengembalikan simpul terjauh dari v dan simpul yang berada di tengah jalur tersebut, dan tidak mengembalikan diameter sama sekali), kode ini kemungkinan akan mengembalikan Anda ke tengah pohon (Saya hanya mengujinya pada contoh Anda, jadi mungkin ada beberapa kesalahan satu per satu)

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
Jawaban persis yang saya cari! Terima kasih! :-) - person Geir; 17.01.2015