Tree root finding

How could I get from s开发者_如何学运维et of nodes and edges get tree with a root? (I'm working with connectivity-matrix, each edge has weight: graph[i][j], without any negative edges). Later I need to do DFS and find LCA's in that tree, so it would be good for optimize.

---

I suppose that your matrix represents the child relationship (i.e. M[i][j] tells that j is the child of i), for a directed graph G(V,E).

You have 2 different strategies:

• use a bit vector, go through each cell of your matrix, and mark the child index in the vector if the cell's weight is not null): the root is the vertex not set in the vector,
• look for the columns (or rows, if your matrix is column first) whose cells are all null (no ancestors),

The second solution is better for dense matrices. Its worst running time would be when the root is the last entry (O(V²)). In this case you can stop at the first hit, or run til the end to get all the roots, if your graph has many.

The first one is better suited for sparse matrices, since you have to go through all the cells. It's running time is in O(E). You also get all the roots with this algorithm.

If you are certain that your graph has only one root, you can use the walk the edges up technique, as described in other answers.

---

Here is a computationally MUCH SLOWER version that is also much easier to code. For small graphs, it is just fine.

Find the node with in-degree zero!

You have to compute all node degrees, O(n), but depending on the setting, this is often much easier to code and thus less prone to error.

---

Pick one node in the tree and walk up, that is, against the orientation of the edges. When you find a node without an ancestor you have the root.

If you need to do something like this often, just remember the parent node for each node.

---

a DFS search from any graph gives you a tree (assuming the graph is connected, of course).

you can iterate it, and start from each node as a possible root, you will get a spanning tree eventually this way, if there is one. complexity will be O(V^2+VE)

EDIT: it works because for any finite graph, if there is a root form node a to node b, there will be a path from a to b in the tree DFS creates. so, assuming there is a possible spanning tree, there is a root r, which you can get from to each v in V. when iterating when r chosen as root, there is a path from r to each v in V, so there will be a path from r to it in the spanning tree.