5,337
edits
Parallel Algorithms: Difference between revisions
→Rooting a tree
| Line 334: | Line 334: | ||
* Vector of edges e.g. (1,2) | * Vector of edges e.g. (1,2) | ||
* Vector of pointers to identical edges e.g. index of (1,2) -> index of (2,1) | * Vector of pointers to identical edges e.g. index of (1,2) -> index of (2,1) | ||
* A vertex <math>r</math> | |||
Goal: | |||
* Select a direction for each edge to make our graph a tree with root <math>r</math> | |||
Algorithm | Algorithm | ||
* Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math> | * Step 1: For every edge <math>(u,v)</math>, add two edges <math>u \rightarrow v</math> and <math>v \rightarrow u</math> | ||
* Step 2: For every directed edge <math>u \rightarrow v</math>, set a pointer to another directed edge from <math>v</math>, <math>next(u \rightarrow v)</math> | |||
* Step 3: <math>next(u_{r,1} \rightarrow r) = NIL </math> | |||
* Step 4: Apply a list ranking algorithm. | |||
==Resources== | ==Resources== | ||