[数据结构与算法]dfs bfs求解树的直径

树的直径

树上最远的两个节点之间的距离

dfs

两次dfs搜索
第一次

任一点开始进行搜索，找到距离最远点

第二次

从第一次最远点开始搜索再次搜索记录最远距离

//
// Created by 29273 on 2022-03-07.
// dfs 求树的直径
#include "bits/stdc++.h"

using namespace std;
const int maxN = 1e3 + 10;
int vis[maxN];

struct node {
    int b;
    int w;

    node(int b, int w) {
        this->b = b;
        this->w = w;
    }
};

int no, ans, x, y, z, dist[maxN];
vector<node> V[maxN];

void dfs(int root) {
    vis[root] = 1;
    for (int i = 0; i < V[root].size(); ++i) {
        node n = V[root][i];
        if (!vis[n.b]) {
            dist[n.b] = dist[root] + n.w;
            if (ans < dist[n.b]) {
                no = n.b;
                ans = dist[n.b];
            }
            dfs(n.b);
        }
    }
}


int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        cin >> x >> y >> z;
        V[x].push_back(node(y, z));
        V[y].push_back(node(x, z));
    }
    dfs(1);
    cout << no << " " << ans << endl;
    memset(vis, 0, sizeof vis);
    memset(dist, 0, sizeof dist);
    ans = 0;
    dfs(no);
    cout << no << " " << ans << endl;
    return 0;
}

bfs

原理同上

//
// Created by 29273 on 2022-03-07.
//
#include "bits/stdc++.h"

using namespace std;
const int maxN = 1e3 + 10;
int vis[maxN];

struct node {
    int b;
    int w;

    node(int b, int w) {
        this->b = b;
        this->w = w;
    }
};

int no, ans, x, y, z, dist[maxN];
vector<node> V[maxN];

void bfs(int root) {
    queue<int> Q;
    Q.push(root);
    while (Q.size()) {
        int top = Q.front();
        Q.pop();
        vis[top] = 1;
        for (int i = 0; i < V[top].size(); ++i) {
            node n = V[top][i];
            if (!vis[n.b]) {
                dist[n.b] = dist[top] + n.w;
                if (ans < dist[n.b]) {
                    ans = dist[n.b];
                    no = n.b;
                }
                Q.push(n.b);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        cin >> x >> y >> z;
        V[x].push_back(node(y, z));
        V[y].push_back(node(x, z));
    }
    bfs(1);
    cout << no << " " << ans << endl;
    memset(vis, 0, sizeof vis);
    memset(dist, 0, sizeof dist);
    ans = 0;
    bfs(no);
    cout << no << " " << ans << endl;
    return 0;
}