29. Graph Diameter
✅ GFG solution to the Graph Diameter problem: find the longest path in an undirected tree using two BFS traversals. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an undirected connected graph with V vertices numbered from 0 to V-1 and E edges, represented as a 2D array edges[][], where each element edges[i] = [u, v] represents an undirected edge between vertex u and vertex v.
Find the diameter of the graph. The diameter of a graph (sometimes called the width) is the number of edges on the longest path between two vertices in the graph.
Note: Graph does not contain any cycle (it's a tree).
📘 Examples
Example 1
Input: V = 6, E = 5, edges[][] = [[0, 1], [0, 4], [1, 3], [1, 2], [2, 5]]
Output: 4
Explanation: The longest path in the graph is from vertices 4 to vertices 5 (4 -> 0 -> 1 -> 2 -> 5).Example 2
Input: V = 7, E = 6, edges[][] = [[0, 2], [0, 4], [0, 3], [3, 1], [3, 5], [1, 6]]
Output: 4
Explanation: The longest path in the graph is from vertices 2 to vertices 6 (2 -> 0 -> 3 -> 1 -> 6).🔒 Constraints
$2 \le V \le 10^5$
$1 \le E \le V - 1$
$0 \le \text{edges}[i][0], \text{edges}[i][1] < V$
✅ My Approach
The optimal approach uses the Two BFS Technique to find the diameter of a tree:
Two BFS Traversal
Build Adjacency List:
Convert the edge list into an adjacency list representation for efficient traversal.
Since the graph is undirected, add edges in both directions.
First BFS - Find One End of Diameter:
Start BFS from any arbitrary node (e.g., node 0).
Track distances from the starting node to all other nodes.
The farthest node from the starting point will be one end of the diameter.
Second BFS - Find Diameter:
Start another BFS from the farthest node found in step 2.
Track distances again and find the maximum distance reached.
This maximum distance is the diameter of the tree.
Why This Works:
In a tree, the farthest node from any starting point must be one endpoint of the longest path.
A second BFS from this endpoint will traverse the entire longest path.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(V + E), as we perform two BFS traversals where each BFS visits every vertex and edge once. Since E = V - 1 for a tree, this simplifies to O(V).
Expected Auxiliary Space Complexity: O(V), for storing the adjacency list, distance array, and BFS queue. Each data structure requires space proportional to the number of vertices.
🧑💻 Code (C++)
class Solution {
public:
int diameter(int V, vector<vector<int>>& edges) {
vector<vector<int>> adj(V);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
auto bfs = [&](int src) {
vector<int> d(V, -1);
queue<int> q;
q.push(src);
d[src] = 0;
int far = src, maxD = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
if (d[v] > maxD) {
maxD = d[v];
far = v;
}
}
}
}
return make_pair(far, maxD);
};
auto [end1, _] = bfs(0);
auto [end2, diam] = bfs(end1);
return diam;
}
};☕ Code (Java)
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[] first = bfs(0, adj);
int[] second = bfs(first[0], adj);
return second[1];
}
private int[] bfs(int src, List<List<Integer>> adj) {
int n = adj.size();
int[] dist = new int[n];
Arrays.fill(dist, -1);
Queue<Integer> q = new LinkedList<>();
q.add(src);
dist[src] = 0;
int far = src, maxD = 0;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.add(v);
if (dist[v] > maxD) {
maxD = dist[v];
far = v;
}
}
}
}
return new int[]{far, maxD};
}
}🐍 Code (Python)
class Solution:
def diameter(self, V, edges):
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def bfs(src):
dist = [-1] * V
q = deque([src])
dist[src] = 0
far, maxD = src, 0
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
if dist[v] > maxD:
maxD = dist[v]
far = v
return far, maxD
end1, _ = bfs(0)
_, diam = bfs(end1)
return diam🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated