树的直径（最远距离）

拼搏现实的明天。 2022-06-15 04:30 193阅读 0赞

输入数据

5 5  
1 2 2  
2 4 3  
2 5 1  
4 5 4  
1 3 5

有5个点5条边

![Center][]

第一次bfs从1号点开始找到最远距离3号距离为5

第二次bfs从3号点开始找最远距离点10

#include<stdio.h>
    #include<string.h>
    #include<queue>
    #define MAX 100000
    using namespace std;
    int head[MAX];
    int vis[MAX];//标记当前节点是否已经用过
    int dis[MAX];//记录最长距离
    int n,m,ans;
    int sum;//记录最长路径的长度
    int aga;
    struct node
    {
        int u,v,w;
        int next;
    }edge[MAX];
    void add(int u,int v,int w)//向邻接表中加边
    {
        edge[ans].u=u;
        edge[ans].v=v;
        edge[ans].w=w;
        edge[ans].next=head[u];
        head[u]=ans++;
    }
    void getmap()
    {
        int i,j;
        int a,b,c;
        ans=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
    }
    void bfs(int beg)
    {
        queue<int>q;
        //dis记录权值
    	//vis标记已访问 
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        int i,j;
        while(!q.empty())
            q.pop();
        aga=beg;
        sum=0;
        vis[beg]=1; //标记起始点已经到达了 
        q.push(beg); //把起点放入队列 
        int top;
        while(!q.empty())
        {
            top=q.front();//获取对头点 
            q.pop();
            for(i=head[top];i!=-1;i=edge[i].next) //从起点top出发 
            {
                if(!vis[edge[i].v])
                {//记录到达相应点的 权值，标记相应点已访问，将到达的
    			//点送入队列，更新最大sum，更新点aga 
                    dis[edge[i].v]=dis[top]+edge[i].w; //到达v点的权值 
                    vis[edge[i].v]=1; //标记已到到的点 
                    q.push(edge[i].v);//已到达入栈 
                    if(sum<dis[edge[i].v])//更新最大值sum 
                    {
                        sum=dis[edge[i].v];
                        aga=edge[i].v;//到达的点 
                    }
                }
            }
        }
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            getmap();
            bfs(1);//搜索最长路径的一个端点
            bfs(aga);//搜索另一个端点
            printf("%d\n",sum);
        }
        return 0;
    }

[Center]: /images/20220615/0d31e54390e9470a99abce7428f9927f.png