greedy_branching(G, attr='weight', default=1, kind='max', seed=None)[source]#

Returns a branching obtained through a greedy algorithm.

This algorithm is wrong, and cannot give a proper optimal branching. However, we include it for pedagogical reasons, as it can be helpful to see what its outputs are.

The output is a branching, and possibly, a spanning arborescence. However, it is not guaranteed to be optimal in either case.


The directed graph to scan.


The attribute to use as weights. If None, then each edge will be treated equally with a weight of 1.


When attr is not None, then if an edge does not have that attribute, default specifies what value it should take.


The type of optimum to search for: ‘min’ or ‘max’ greedy branching.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Bdirected graph

The greedily obtained branching.