mediumGraphsPattern: BFS/DFS

Minimum Traversal Edges Solution

Problem Statement

Given an adjacency list representing a graph, find the minimum number of edges that need to be traversed to visit all nodes.

Examples

Example 1:

Input:{1: [2, 3], 2: [1, 3], 3: [1, 2]}

Output:2

Explanation: The minimum number of edges to traverse all nodes is 2, e.g., visiting node 1 -> node 2 -> node 3 in order.

Example 2:

Input:{1: [], 2: [1], 3: [2, 3], 4: [3]}

Output:2

Explanation: The minimum number of edges to traverse all nodes is 2, e.g., visiting node 1 -> node 2 -> node 3 -> node 4 in order.

Example 3:

Input:{}

Output:0

Explanation: The minimum number of edges to traverse all nodes is 0, as there are no nodes to visit.

Constraints

The graph is represented as an adjacency list.
The graph is connected.
The graph has n nodes and m edges.
Each edge has a non-negative weight.
The nodes are numbered from 1 to n.

Time: O(V + E) Space: O(V)

Use a graph traversal algorithm with a time complexity of O(V + E) and a space complexity of O(V), where V is the number of vertices and E is the number of edges.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

from collections import defaultdict

def min_traversal_edges(graph):
    if not graph:
        return 0

    n = len(graph)
    visited = set()
    edges = 0

    # Find connected components
    components = []
    for node in graph:
        if node not in visited:
            component = set()
            stack = [node]
            while stack:
                curr = stack.pop()
                if curr not in visited:
                    visited.add(curr)
                    component.add(curr)
                    for neighbor in graph.get(curr, []):
                        stack.append(neighbor)
            components.append(component)
    
    # For each component, we need at least |V|-1 edges to connect all nodes within it.
    # If a component has only one node, it contributes 1 to the edge count.
    for component in components:
        if len(component) > 1:
            edges += len(component) - 1
        else:
            edges += 1

    return edges