# Spanning Tree Algorithm

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).

## ST (G,s):

Input:     Graph G=(V, E [, W]) and a node s. The weight function W: E --> R (reals) is optional
Output:
A tree T rooted at s and spanning its connected component (more precisely, for directed G, the tree includes all nodes reachable from s by a directed path). T is represented as a subset of E.

Algorithm:

``` Initialize: ```

`for```` each node v do v.init ```

```S.init; S.store( <s,s [, d0]> )```

`T <-- emptyset`

```while NOT S.empty do {```

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

```if NOT v.visited then do {```

T <-- T + uv  // adds edge uv to the tree T

`v.visit( [x] )`

```for each edge vw do S.store( <v, w [, dvw ]> ) ```

`}`

`}`

`return T;`

### Node data and optional parameters

#### Un-weighted graphs

In the case of un-weighted graphs G=(V,E) the optional parameters, denoted by "[...]" in the algorithm above are not used, and node data can be implemented using a single Boolean flag `v.visited`. Then we can define ```v.init ```and ```v.visit ```as follows:

```v.init :     v.visited <-- false```

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

#### Weighted graphs

In the case of weighted graphs G=(V, E, W) the situation is somewhat more complex. In particular, the optional parameters need to be used. But the specifics of their use and the node data may depend on the specific task at hand. For example, in the case of MST, the node data can be handled the same way as for the un-weighted graphs above. And the optional parameter `dvw` in the ``` S.store``` (and ``` S.extract```) is simply the weight W(vw) of the corresponding edge.

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 ( NOT v.dist == infinity )```

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

In the initialization use `d0`=0, and in the main part of the algorithm storing an edge is done as follows:

```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.

### Storage S

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)

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.