getting vertices in order from spanning tree

I've got spanning tree for some weighted graph (edges labeled 1-6) - for example:

graphMatrix = {{0, 0.140892, 0.298153, 1.13827, 1.27866, 1.4}, {0.140892, 0,
0.167897, 1.16492, 1.3422, 1.49614}, {0.298153, 0.167897, 0,
1.13035, 1.35045, 1.54743}, {1.13827, 1.16492, 1.13035, 0, 0.375184,
0.773562}, {1.27866, 1.3422, 1.35045, 0.375184, 0, 0.412249}, {1.4,
1.49614, 1.54743, 0.773562, 0.412249, 0}};

VertexLabels -> "Name"];
tree = Graph[FindSpanningTree[graph], VertexLabels -> "Name"]


How can I get vertices of tree in order in which they appear in this tree?

(In this case it should be {1,2,3,4,5,6}).

Edit: Second example, when given such tree:

Result should be {68, 2, 193, 88, 129, …} or {197, 198, …}

• For your graph, VertexList[tree] does the right thing... Sep 23, 2014 at 10:36
• VertexList[tree] will always return all vertices with normal ordering (1,2,3,…) - even if tree is something like (3 -> 1, 1 -> 2).
– Esse
Sep 23, 2014 at 12:40
• Notice that there is no canonical ordering on trees that I am aware of, so what would you expect? Sep 23, 2014 at 12:47
• @IgorRivin I've added some clarification.
– Esse
Sep 23, 2014 at 14:39
• Esse, VertexList returns all vertices in the order they are appear in the input to Graph. So, if you don't use an explicit vertex list as the first argument in Graph VertexList gives the vertices in the order they appear in the edge list you enter as the first argument of Graph. Try, for example, g= Graph[{3 -> 1, 1 -> 2}]; VertexList[g].
– kglr
Sep 23, 2014 at 14:41

If your graph is a path graph, only thing you need to do is finding root (starting vertex). Once you find root, you could do DepthFirstScan (like Igor Rivin suggested), BreadthFirstScan, VertexComponent, etc...

For example:

g = PathGraph[RandomSample[Range[100], 100], VertexLabels -> "Name"]


roots = VertexList[g][[Flatten[Position[VertexDegree[g], 1]]]]


{21, 83}

r1 = Reap[DepthFirstScan[g, roots[[1]], {"PrevisitVertex" -> Sow}]][[2, 1]]


{21, 12, 5, 6, 97, 99, 29, 47, 96, 10, 26, 14, 56, 78, 46, 44, 70, 92, 42, 24, 91, 16, 40, 87, 65, 48, 77, 79, 69, 31, 43, 85, 9, 3, 64, 35, 58, 7, 67, 81, 60, 20, 8, 19, 36, 11, 13, 86, 90, 62, 4, 53, 84, 51, 52, 22, 72, 88, 2, 95, 30, 18, 1, 61, 93, 45, 80, 34, 39, 37, 25, 50, 75, 68, 71, 27, 32, 49, 82, 73, 57, 100, 28, 17, 76, 55, 59, 15, 74, 54, 41, 94, 89, 66, 23, 98, 63, 38, 33, 83}

r2 = Reap[
BreadthFirstScan[g, roots[[1]], {"PrevisitVertex" -> Sow}]][[2, 1]]

r3 = VertexComponent[g, 21]

r1 == r2 == r3


True

• runs like a charm - thank you very much!
– Esse
Sep 24, 2014 at 14:37
• +1 p.s. That's quite nice form of your roots function: Pick[VertexList[#], VertexDegree[#], 1]&
– Kuba
Nov 17, 2015 at 12:12

What you want is DepthFirstScan, as in:

vlist = {}
DepthFirstScan[tree, 1, {"PrevisitVertex"-> (vlist = Append[vlist, #]&)}]


UPDATE

As Mark points out, that does not work, what does work (almost) is

Reap[DepthFirstScan[tree2, 1, {"PrevisitVertex" -> Sow}]]


However, this will give non-leaf vertices multiple times. What do you actually want it to do?

• I get a sequence of errors of the form: Function::flpar: Parameter specification Append[vlist,#1] in Function[Append[vlist,#1],1] should be a symbol or a list of symbols. >> I guess this can be fixed using SetDelayed rather than Set. Sep 23, 2014 at 13:07
• @MarkMcClure See the edit for a more elegant solution, sorry. Sep 23, 2014 at 13:21
• I'e added some clarification - I'm interested in some particular trees, with only one branch (in other words where such ordering occurs).
– Esse
Sep 23, 2014 at 13:50