ค้นหาจุดศูนย์กลางของเส้นผ่านศูนย์กลางของกราฟทรีโดยใช้ BFS หรือไม่

ดังนั้นฟังก์ชัน big_dist นี้ค้นหาเส้นผ่านศูนย์กลางของกราฟ (กราฟที่กำหนดในงานจะเป็น เสมอ ต้นไม้)

สิ่งที่ฉันต้องการให้ค้นหาแทนคือการหาจุดศูนย์กลางของเส้นผ่านศูนย์กลาง ซึ่งเป็นโหนดที่มีระยะห่างสูงสุดน้อยที่สุดไปยังโหนดอื่นๆ ทั้งหมด

ฉัน "ค่อนข้าง" เข้าใจความคิดที่ว่าเราสามารถทำได้โดยการค้นหาเส้นทางจาก 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
เอ่อ... คุณสามารถถือว่ามันเป็นกราฟและ dfs จาก 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 ครั้งใน prev ได้ เช่น:

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