# 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... – Igor Rivin Sep 23 '14 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 '14 at 12:40
• Notice that there is no canonical ordering on trees that I am aware of, so what would you expect? – Igor Rivin Sep 23 '14 at 12:47
• @IgorRivin I've added some clarification. – Esse Sep 23 '14 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 '14 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 '14 at 14:37
• +1 p.s. That's quite nice form of your roots function: Pick[VertexList[#], VertexDegree[#], 1]& – Kuba Nov 17 '15 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. – Mark McClure Sep 23 '14 at 13:07
• @MarkMcClure See the edit for a more elegant solution, sorry. – Igor Rivin Sep 23 '14 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 '14 at 13:50