Graph Diameter

Time: O(V+E)

Space: O(V)

Intuition

Find diameter of a graph (longest shortest path between any two nodes). Two BFS for trees; Floyd-Warshall for general graphs.

Algorithm

1For tree: BFS from any node to find farthest node u. BFS from u to find farthest node v. Diameter = dist(u,v).
2For general graph: Floyd-Warshall, then max of all dist[i][j].

Common Pitfalls

•Tree diameter: two-BFS trick works perfectly. General graph: O(V^3) Floyd-Warshall.

Graph Diameter.java

Java

// Approach: Two BFS passes: BFS from any node finds the farthest node u; BFS from u gives the diameter.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    public int diameter(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int nodeA = bfs(0, adj, V)[0];
        int[] result = bfs(nodeA, adj, V);
        return result[1];
    }

    private int[] bfs(int start, List<List<Integer>> adj, int V) {
        int[] dist = new int[V];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[start] = 0;
        int farthestNode = start;
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int nei : adj.get(node)) {
                if (dist[nei] == -1) {
                    dist[nei] = dist[node] + 1;
                    q.add(nei);
                    if (dist[nei] > dist[farthestNode])
                        farthestNode = nei;
                }
            }
        }
        return new int[] { farthestNode, dist[farthestNode] };
    }
}

Was this solution helpful?