无向图的直径以及树的直径

转载：http://www.csie.ntnu.edu.tw/~u91029/Path3.html

在一張無向圖上面，給定圖上一點，以最短路徑長度當作距離，找出離此點最遠的一點，這兩點之間的距離就叫做「偏心距」。

要計算一張無向圖的直徑與半徑是很簡單的，首先算好所有兩點之間最短路徑，然後按照定義來算就可以了。

先用floyd算法，再找最长的即可

int d[10][10];  // adjacency matrix

int ecc[10];    // 各點的偏心距

 

void diameter_radius()

{

    // Floyd-Warshall Algorithm

    for (int k=0; k<10; ++k)

        for (int i=0; i<10; ++i)

            for (int j=0; j<10; ++j)

                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

 

    // 計算偏心距

    memset(ecc, 0x7f, sizeof(ecc));

    for (int i=0; i<10; ++i)

        for (int j=0; j<10; ++j)

            ecc[i] = min(ecc[i], d[i][j]);

 

    // 計算直徑和半徑

    int diameter = 0;

    int radius = 1e9;

    for (int i=0; i<10; ++i)

    {

        diameter = max(diameter, ecc[i]);

        radius   = min(radius  , ecc[i]);

    }

 

/*

    // 直徑也可以這樣算

    for (int i=0; i<10; ++i)

        for (int j=0; j<10; ++j)

            diameter = max(diameter, d[i][j]);

*/

}

树形图的最长路径（边无权重）

方法1：

一棵無根樹的「直徑」，就是相離最遠的兩個點的距離。

稍微修改一下計算高度的程式碼，就可以順便計算直徑。

樹的直徑，邊無權重（adjacency matrix）

bool adj[9][9];

int diameter = 0;

 

int DFS(int x, int px)  // px是x的父親

{

    int h1 = 0, h2 = 0; // 紀錄最高與次高的高度

    for (int y=0; y<9; ++y)

        if (adj[x][y] && y != px)//记录父亲节点，防止重复访问

        {

            int h = DFS(y, x) + 1;

            if (h > h1) h2 = h1, h1 = h;

            else if (h > h2) h2 = h;

        }

    diameter = max(diameter, h1 + h2);

    return h1;

}

 

void tree_diameter()

{

    diameter = 0;   // 初始化

 

    int root = 0;   // 隨便選一個樹根

    DFS(root, root);

    cout << "樹的直徑是" << diameter;

}

一棵樹的各種直徑一定會相交在同一點（同一群點）。

1. 反證法。 現在有兩條分開的直徑， 可是一棵樹上各點都得連通， 所以這兩條分開的直徑，中間一定有某處互相連接， 一旦連接起來，勢必變成更長的直徑，矛盾。 故所有直徑必相交。2. 反證法。 現在已有兩條直徑相交在某一點， 如果另外一條直徑與這兩條直徑相交在另一點， 勢必變成更長的直徑，矛盾。 故所有直徑必相交在同一點（同一群點）。

方法二：

在一个迷宫中找距离最长的两个点。迷宫可以看作是一个无根树，因此，这个问题等价与在一个树形图中找最远的两个节点，也叫做这个图的直径。

迷宫、树形图有个很好的特点：任意两个节点之间的距离就是这两点之间的最短路径、也是两个节点的最长路径，也可以说任意两个节点之间的距离一定。基于这个想法，可以很快想到：穷举每个点对，计算其距离，取最大值，即可。这个计算量比较大，思想上可行，实践起来，时间代价有点不靠谱。查了下，已经有好的解决方案了：

1 取任意节点作为起点，找出到该点最远的点，记为A；

2 以点A为起点，找出到该点最远的点，记为B；

AB之间的距离，就是图中距离最远的两个点的距离（这样的点对可能有多个，但最大距离值只有一个）。

因此，两次dfs即可搞定。也可以用bfs

代码如下：

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

 

int m,n;

int f[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

char map[1002][1002];

bool flag[1002][1002];

 

int max,step,maxM,maxN;

int si,sj;

 

void dfs(int i,int j)

{

    int ii,a,b;

    for(ii=0;ii<4;ii++)

    {

        a = i+ f[ii][0];

        b = j+ f[ii][1];

        if(a>=0 && a<m && b>=0 && b<n && map[a][b]=='.' && flag[a][b])

        {

            step++;

            flag[a][b] = false;

            if(max < step)

            {

                max = step;

                maxM = a;

                maxN = b;

            }

            dfs(a,b);

            flag[a][b] = true;

            step--;

        }

    }

}

int main()

{

    int t,i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        si = -1;

        for(i=0;i<m;i++)

        {

            scanf("%s",map[i]);

            if(si==-1)

                for(j=0;j<n;j++)

                    if(map[i][j]=='.')

                    {

                        si = i;

                        sj = j;

                        break;;

                    }

        }

        

        memset(flag, true, sizeof(flag));

        flag[si][sj] = false;

        max = 0;

        step = 0;

        dfs(si,sj);

        

        memset(flag, true, sizeof(flag));

        flag[maxM][maxN] = false;

        max = 0;

        step = 0;

        dfs(maxM, maxN);

        

        printf("Maximum rope length is %d.\n",max);

    }

    system("pause");

    return 0;

}

如果边有权重的话，感觉着两个算法也能正常工作

总结

以上是生活随笔为你收集整理的无向图的直径以及树的直径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。