Below is my version generalizing many "standard" spanning tree algorithms, including Depth-First Search (DFS), Bredth-First Search (BFS), Minimum-Weight Spanning Tree (MST), and Shortest Path Tree (also called Single-Source Shortest Path).

** Input: ** Graph

__Algorithm__:

Initialize:

`for`

each nodevdov.init

`S.init; S.store( <s,s [, d`

_{0}]> )

`T <-- emptyset`

while NOTS.emptydo {

`<u, v [, x]> <-- S.extract`

ifNOTv.visitedthen do {T <-- T + uv

// adds edge uv to the tree T

`v.visit( [x] )`

foreach edgevwdoS.store( <v, w [, d_{vw }]> )

}

}

return T;

In the case of * un-weighted* graphs

`v.visited`

.
Then we can define `v.init`*
*

and ```
v.visit
```

as follows:

`v.init`

: v.visited <--false

`v.visit : v.visited <--`

true

In the case of * weighted* graphs

`d`_{vw}

in the ```
S.store
```

(and ```
S.extract
```

) is simply the weight But in the case of the Shortest Path tree, each node would maintain a
numerical field `v.dist`

which is initiated to infinity for all nodes except **s**, and then changed
to the shortest path distance when the node is visited. Then the node data
operations are implemented as follows:

`v.init`

:v.dist <--infinity

`v.visited :`

return ( NOTv.dist ==infinity)

`v.visit(x): v.dist <-- x`

In the initialization use `d`

=0,
and in the main part of the algorithm storing an edge is done as follows: _{0}

`S.store( <v, w , v.dist +`

W(vw)> )

That is we store an edge vw together with the "candidate shortest path"
distance from **s** to w going through the edge vw.

Implementing the storage using different data structures produces different types of spanning trees:

*Stack*:**DFS***Queue*:**BFS***Priority Queue*(using the optional parameters and extracting the triplet with the minimum third value):- Using edge weight:
**Minimum Spanning Tree***(this is equivalent to Prim's algorithm)* - Using the distance as above:
**Shortest Path Tree***(this is equivalent to Dijkstra's algorithm)*

- Using edge weight:

Note: using Priority Queue extracting the *maximum* (rather than a
minimum) *will* result in a correct Maximum-Weight Spanning Tree, but *
will not *result in a Longest Path Tree (in fact, Longest Path
problem, though solvable in many special cases, is NP-complete for general
graphs and thus is unlikely to have an efficient algorithm; see also
Hamiltonian Path
problem, which is a special case of the longest path problem).

Another subtle difference is that the above MST algorithm works correctly
even if the edge weights are *negative*. But the Shortest Path Tree
algorithm is guaranteed to work correctly only if all the edge weights are *
non-negative*.