Search code examples
algorithmdata-structuresminimum-spanning-tree

Does a DFS produce a MST for an unweighted directed graph?


I'm getting confused from reading online posts. I know that a BFS traversal on an unweighted directed graph will produce a minimum spanning tree and shortest path. Can a DFS traversal on an unweighted directed graph do the same?


Solution

  • Yes, Breadth-First and Depth-First both yield spanning trees. It doesn't make much sense to discuss "minimum spanning tree" for an unweighted graph, because all spanning trees on a given graph with n vertices have the same number of vertices (n) and the same number of edges (n-1).

    No, Depth-First does not guarantee shortest path. You really need Breadth-First for that. Consider a cyclic graph:

    a - h - g - f
    |           |
    b - c - d - e
    

    Starting from vertex a, there are two possible results to depth-first search: a->b->c->d->e->f->g->h, and a->h->g->f->e->d->c->b. The former returns a very long path from a to h, and the latter returns a very long path from a to b.

    Note that in this example, the graph is undirected. But undirected graphs are a special case of directed graphs; you can replace every undirected edge by two directed edges in opposing directions.