New answers tagged graph-traversal
2
votes
Are reversed reverse preorder traversals equivalent to a postorder traversal?
Nathaniels simple and elegant proof is the best way to formally convince yourself your conjectures are true. I want to add a more informal and visual explanation.
The postorder traversal of a binary ...
- 27.2k
4
votes
Accepted
Are reversed reverse preorder traversals equivalent to a postorder traversal?
This can be proven by induction on trees. I give details on the conjecture 1 here.
It is clearly true for the empty tree and for leaves;
Suppose it is true for trees $l$ and $r$. Consider $t$ a node ...
- 7,154
2
votes
Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
I think there may be a mistake in your statement, unless you allow a walk to stay in the same vertex on a step, instead of crossing an edge (but that's not the usual definition of walk), or unless you ...
- 7,154
0
votes
When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
Krystal’s algorithm for constructing minimum spanning trees first sorts an array of edges in increasing order of weight, so that edges with the smallest weight can be considered first for selection.
- 1,030
0
votes
When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
Is that something we can't accomplish with some other representation?
Edge list and adjacency list represent the same thing so if you can do something with one, you can do it with the other. In the ...
- 101
Top 50 recent answers are included