演算法分析課設（四）采用分治法求樹中任意兩點之間距離小于K的點對及路徑-有解無憂

免責宣告

本文僅為個人學習筆記，請謹慎參考，如有錯誤歡迎批評指正，

參考文章

第一篇文章主要看樹的重心的部分

第二篇文章才是和本題完全一致

https://blog.csdn.net/a_forever_dream/article/details/81778649

https://blog.csdn.net/jackypigpig/article/details/69808594

要求：

（1）用偽代碼描述求樹重心的演算法，

（2）將下面的樹作為輸入時，寫出求解上述問題的求解程序以及求解結果，要求寫出求解程序中主要變數的變化程序，

（3）撰寫程式求解該問題，并分析演算法的時間復雜度，

【分析】

樹的重心，也叫樹的質心，即樹的一個結點，把它刪掉后的所有子樹的最大結點數（相比于刪掉其他結點）最小，如圖所示：

要求樹的重心，也許第一想法是遍歷一次所有結點，把每個結點都當成重心，計算每棵子樹的結點數，再來進行比較，但這種暴力法是不可取的，它會重復計算很多次相同的路徑，我們可以僅掃描一次整棵樹就能得到以每個點作為重心的最大子樹結點數，這里要用到樹的點分治法，分治法，我把它理解成后序遍歷的遞回呼叫，但是遞回也只能以一個結點為起點進行遞回呀，怎么能算出以所有點為起點的最大子樹結點數呢？這里我們還是以上面的樹為例子，用n表示整棵樹的結點數，這里n=5；用size[i]代表以i為根的樹的結點數；用max_child[i]代表以i為根的最大子樹結點數；用min來更新max_child[i]中的最小值，它用來更新重心，min起始值是很大的數，

按照后續遍歷的遞回，我們首先能算出點4的size[4]=1，紅色部分是n-size[4]=4個結點，之所以能這么分，是因為點4只會有一個父結點，所以紅色部分始終能作為它的一棵子樹，比較size[4]和n-size[4]的大小，以點4為根的最大子樹結點數max_child[4]=4，min更新為max_child[4]的4，

然后是算出點5的size[5]=1，也是類似點4，紅色部分是n-size[5]=4個結點，以點5為根的最大子樹結點數max_child[5]=4，min不變，

接著是算出點2，也就是它自身的1個結點，加上它的子樹點4和點5的size，綠色部分為它的子樹，分別為size[4]=1個結點、size[5]=1個結點，紅色部分是n-size[2]=2個結點，所以以點2為根的最大子樹結點數max_child[2]=2，min更新為2，

接著是算出點3，也就是它自身的1個結點，紅色部分是n-size[3]=4個結點，所以以點3為根的最大子樹結點數max_child[3]=4，min不變，

接著是算出點1，也就是它自身的1個結點，加上它的子樹點2和點3的size，綠色部分為兩棵子樹，size[2]=3個結點、size[3]=1個結點，紅色部分已經沒有了，n-size[1]=0個結點，所以以點1為根的最大子樹結點數max_child[1]=3，min不變，

min一旦更新，重心root也會更新為對應的結點，只是這里沒寫出來，看代碼就知道了，

所以說，這個遞回的開始點選誰不重要，選擇任意點都能算出以每個點為根的最大子樹結點數，進而求出重心，

求樹的重心的代碼如下：

// 全域變數
int n=17; // 所有結點數
int size[n];// 以n為根的樹的結點數
int max_child[n];// 以n為根的樹的最大子樹的結點數
int min;// max_child中最小的那個
int first[n+1],edge[(n-1)*2]// 頂點表，邊表
int gravity=0;// 被選為重心的結點

// 傳入引數
// start 代表當前結點
// parent 代表當前結點的父結點，這里是為了防止遍歷start的子結點的時候把父結點也遍歷進去了
void getGravity(int start, int parent)
{
    // size[start]代表當前結點的個數，初始為1是算上本身
    size[start]=1;
    // max_child[start]代表當前結點的最大子樹結點數
    max_child[start]=0;
    // 遍歷以start結點為起點的所有邊（除去連接父結點的邊）
    for(int i=first[start]; i; i=edge[i].next)
    {
        // end為當前邊的終點（也是start點的子結點）
        int end=edge[i].end;
        // 如果這個終點已經被遍歷或者這個終點是父結點，就跳過
        if(visited[end] || end==parent){
            continue;
        }
        // 繼續遍歷終點的子結點，這里其實就是遍歷start的一棵子樹的所有結點數
        getGravity(end, start);
        // 遍歷完這棵子樹的所有結點后，把子樹的結點數加起來
        size[start]+=size[end];
        // 如果這顆子樹的結點數大于max_child，就更新它
        if(size[end] > max_child[start]){
            max_child[start]=size[end];
        }
    }
    // 上面的回圈是用來遍歷start的每一棵子樹并比較出最大子樹結點
    // 接下來就是算“紅色部分”，也就是n-size[i]部分的結點數，并比較出最終的最大子樹結點
    if(n-size[start] > max_child[start]){
        max_child[start]=n-size[start];
    }
    // 從max_child中比較出最小的，以找出重心
    if(min < max_child[start]){
        min=max_child[x];
        gravity=start;
    }
}

這里對樹的存盤方法是，用頂點表first來存每個點，first[i]代表編號為i的結點的對應的第一條邊的編號，邊表edge的每一行代表一條邊，包含這條邊的起點、終點、權重和下一條相同起點的邊，因為這些邊是無向的，所以一條邊在邊表里存了兩次，

添加樹結點和邊的代碼如下：

int first[n+1],edge[(n-1)*2]// 頂點表，邊表
int num=0;
void addNodeAndEdge(int start,int end,int weight)
{
    num++;// 編號，沒錯，要從1開始
    edge[num].start=start;// 起點
    edge[num].end=end;// 終點
    edge[num].weight=weight;// 權重
    edge[num].next=first[start];// 下一條相同起點的邊
    first[start]=num;// 加入頂點
}

以上僅僅是對求樹重心的分析，找出重心以后，接下來就是要找距離小于K的點對和路徑，

在選出樹的重心之后，我們計算所有點到這個重心的距離（即權重），也是用遞回的辦法，這個應該很好理解，不做過多解釋，

int t=0;
// start是傳入的點，parent是start的父結點，weight是start和parent連線的權重
void getDistance(int start, int parent, int weight)
{
    // dis陣列保存了每個點到重心的距離（權重），為什么用t來做下標而不是點的編號呢
    // 因為后面的做法只用數點對的個數，不在乎是誰到誰
    // t是從1開始的
    dis[++t]=weight;
    for(int i=first[start]; i; i=edge[i].next)
    {
        int end=edge[i].end;
        // 如果這個終點已經被遍歷或者這個終點是父結點，就跳過
        // 這點很重要，因為如果傳入的start不是根結點而是根結點的子樹的時候
        // 它就不會把根結點再遍歷一次
        if(visited[end] || end==parent){
            continue;
        }
        getDistance(end, start, weight+edge[i].weight);
    }
}

這一步我們拿到了dis陣列，每個點到重心的距離都保存在dis里面了，再次強調，dis的下標和結點編號沒關系，還是以前面的例子，如下圖所示：

接下來要做的是求長度小于等于K的路徑數，我的第一想法是把dis中小于等于K的點找到，這樣我們就選出點到重心距離小于等于K的點對，但是！根據第二篇參考文章，并不是這樣做的，參考部分第二篇參考文章：

之后，這棵子樹中相連的路徑會經過重心且對答案有貢獻的點對(i,j) (i<j)就會是這樣： dis[i]+dis[j] <= K 且在去除重心后，i 與 j 不在同一個聯通塊里，
不過顯然要滿足“不在同一個聯通塊里”這個條件有點突兀，于是就有了一個小技巧：
先不管在不在一個聯通塊這個條件，算出當前這棵樹的符合路徑數，之后再將得出的個數減去以重心的兒子節點為根的子樹內的點對路徑距離（經過重心）小于等于K的個數，就行了，

它的意思就是我們現在有了每個點到重心的距離之后，我們把dis按照從小到大排序（排序是為了好算出比K小的點對），進行兩兩相加（相加的dis是絕對要經過重心的），比如：

2——1——3，對應dis[2]和dis[5]

4——2——1——3，對應dis[3]和dis[5]

但是有一種情況是不妙的，比如4——2——1——2，對應dis[3]和dis[2]，點4和點2他們之間本來是不用經過重心點1，這怎么排除掉呢？

第二篇文章說，我們把所有組合的點對的dis相加，計算出小于等于K的點對的數量后，再減去重心點1下的所有子樹（以點2和點3為根的樹）的經過重心的點對的數量，再對所有子樹遞回，子樹找出重心，算出dis，兩兩組合，算出點對數量，再減去它的子樹的經過重心的點對數量......一直這樣下去，直到葉子結點，這樣就把“情況不妙”的點排除了，

我不懂為什么一定是算經過重心的點對的數量，而不計算以重心為起點、其他點為終點的點對的數量，時間緊迫，看到好幾篇同類文章也是這種思路，就默認這種方法來理解代碼了，

// 傳入重心，以及重心和它的父結點之間的權重
int work(int start,int weight) {
    t=0;
    // 算出start到各個結點的距離
    getDistance(start, 0, weight);
    // 得到dis陣列后，對其進行從小到大排序
    // 注意，這里的t已經不是0了，它是全域變數，在getDistance里面遍歷了start出發的所有結點
    sort(dis+1,dis+1+t);
    // pair_num表示點對數量
    int pair_num=0；
    int i=1,j=t;
    // 這個while回圈就是把兩個dis相加的和小于等于K的點對數量計算出來
    while (i<j){
        while (i<j && dis[i]+dis[j]>K) j--;
        pair_num+=j-i;
        i++;
    }
    return pair_num;
}

回傳了以點1為重心的樹的所有點對數量之后，接下來要減去點1的子樹的點對數量，所以我們需要一個遞回來進行重復的操作，

// 遞回地求每個樹的經過重心的點對數量
// 起始點是start
void dfs(int start){
    // 以start為起點找到重心
    // 注意，雖然一開始我們說了從樹的任何一個點開始遍歷都能找出一個確定的重心，
    // 但是這里的意思是，從start開始，它的父結點就不要再遍歷的，只找它和它的子樹的重心
    getGravity(start,0);
    // 用這個重心算出所有跨過該重心的路徑數
    ans += work(gravity,0);
    // 標記這個重心已訪問
    visited[gravity]=1;
    // 從重心開始訪問子結點
    for(int i=first[start]; i; i=edge[i].next){
        int end=edge[i].end;
        if (visited[end]){
            continue;
        }
        // 減去以子結點為根的樹的所有跨過子結點的路徑數
        ans -= work(end, edge[i].weight);
        // 以子結點為根的樹繼續求重心、所有跨過路徑數
        dfs(end);
    }
    return;
}

然后放上main函式：

int main()
{
    // 輸入結點個數
    scanf("%d",&n);
    // 輸入每個結點的資訊
    for(int i=1;i<n;i++)
    {
        int start, end, weight;
        scanf("%d %d %d",&start,&end,&weight);
        addNodeAndEdge(start,end,weight);
        addNodeAndEdge(end,start,weight);
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

最后是整體代碼：

#include <stdio.h>
#define MAX 10000;

// 全域變數
int n; // 所有結點數
int size[n],max_child[n],min=MAX;// 以n為根的樹的結點數，以n為根的樹的最大子樹的結點數
int first[n+1],edge[(n-1)*2]// 頂點表，邊表
int visited[n+1];// 標記已訪問過的點
int dis[];// 每個點到重心的距離
int gravity=0;// 重心
int num=0,t=0;// 結點編號
int ans=0;// 最終結果：小于等于K的點對數量

void addNodeAndEdge(int start, int end, int weight)
{
    num++;// 編號
    edge[num].start=start;// 起點
    edge[num].end=end;// 終點
    edge[num].weight=weight;// 權重
    edge[num].next=first[start];// 下一條相同起點的邊
    first[start]=num;// 加入頂點
}

// 傳入重心，以及重心和它的父結點之間的權重
int work(int start,int weight) {
    t=0;
    // 算出start到各個結點的距離
    getDistance(start, 0, weight);
    // 得到dis陣列后，對其進行從小到大排序
    // 注意，這里的t已經不是0了，它是全域變數，在getDistance里面遍歷了start出發的所有結點
    sort(dis+1,dis+1+t);
    // pair_num表示點對數量
    int pair_num=0；
    int i=1,j=t;
    // 這個while回圈就是把兩個dis相加的和小于等于K的點對數量計算出來
    while (i<j){
        while (i<j && dis[i]+dis[j]>K) j--;
        pair_num+=j-i;
        i++;
    }
    return pair_num;
}

void getDistance(int start, int parent, int weight)//fa表示x的父親，z表示x到目標點的距離
{
    // dis陣列保存了每個點到重心的距離（權重），為什么用t來做下標而不是點的編號呢
    // 因為后面的做法只用數點對的個數，不在乎是誰到誰
    dis[++t]=weight;
    for(int i=first[start]; i; i=edge[i].next)
    {
        int end=edge[i].end;
        // 如果這個終點已經被遍歷或者這個終點是父結點，就跳過
        // 這點很重要，因為如果傳入的start不是根結點而是根結點的子樹的時候
        // 它就不會把根結點再遍歷一次
        if(visited[end] || end==parent){
            continue;
        }
        getDistance(end, start, weight+edge[i].weight);
    }
}
// 傳入引數
// start 代表當前結點
// parent 代表當前結點的父結點，這里是為了防止遍歷start的子結點的時候把父結點也遍歷進去了
void getGravity(int start, int parent)
{
    // size[start]代表當前結點的個數，初始為1是算上本身
    size[start]=1;
    // max_child[start]代表當前結點的最大子樹結點數
    max_child[start]=0;
    // 遍歷以start結點為起點的所有邊（除去連接父結點的邊）
    for(int i=first[start]; i; i=edge[i].next)
    {
        // end為當前邊的終點（也是start點的子結點）
        int end=edge[i].end;
        // 如果這個終點已經被遍歷或者這個終點是父結點，就跳過
        if(visited[end] || end==parent){
            continue;
        }
        // 繼續遍歷終點的子結點，這里其實就是遍歷start的一棵子樹的所有結點數
        getGravity(end, start);
        // 遍歷完這棵子樹的所有結點后，把子樹的結點數加起來
        size[start]+=size[end];
        // 如果這顆子樹的結點數大于max_child，就更新它
        if(size[end] > max_child[start]){
            max_child[start]=size[end];
        }
    }
    // 上面的回圈是用來遍歷start的每一棵子樹并比較出最大子樹結點
    // 接下來就是算“紅色部分”，也就是n-size[i]部分的結點數，并比較出最終的最大子樹結點
    if(n-size[start] > max_child[start]){
        max_child[start]=n-size[start];
    }
    // 從max_child中比較出最小的，以找出重心
    if(min < max_child[start]){
        min=max_child[x];
        gravity=start;
    }
}

// 遞回地求每個樹的經過重心的點對數量
// 起始點是start
void dfs(int start){
    // 以start為起點找到重心
    // 注意，雖然一開始我們說了從樹的任何一個點開始遍歷都能找出一個確定的重心，
    // 但是這里的意思是，從start開始，它的父結點就不要再遍歷的，只找它和它的子樹的重心
    getGravity(start,0);
    // 用這個重心算出所有跨過該重心的路徑數
    ans += work(gravity,0);
    // 標記這個重心已訪問
    visited[gravity]=1;
    // 從重心開始訪問子結點
    for(int i=first[start]; i; i=edge[i].next){
        int end=edge[i].end;
        if (visited[end]){
            continue;
        }
        // 減去以子結點為根的樹的所有跨過子結點的路徑數
        ans -= work(end, edge[i].weight);
        // 以子結點為根的樹繼續求重心、所有跨過路徑數
        dfs(end);
    }
    return;
}

int main()
{
    // 輸入結點個數
    scanf("%d",&n);
    // 輸入每個結點的資訊
    for(int i=1;i<n;i++)
    {
        int start, end, weight;
        scanf("%d %d %d",&start,&end,&weight);
        addNodeAndEdge(start,end,weight);
        addNodeAndEdge(end,start,weight);
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246923.html

標籤：其他

上一篇：STM32F103最小系統圖例

下一篇：FUSB302 PD物理層開發