给出一个无向图，其中每个节点在空间中具有笛卡尔坐标，并且具有树的一般形状，是否有一种算法可以将图形转换成树，并找到合适的根节点?
Given an undirected graph in which each node has a Cartesian coordinate in space that has the general shape of a tree, is there an algorithm to convert the graph into a tree, and find the appropriate root node?
请注意，我们对树"的定义要求分支不要以锐角偏离父节点.
Note that our definition of a "tree" requires that branches do not diverge from parent nodes at acute angles.
请参见下面的示例图.我们如何找到红色节点?
See the example graphs below. How do we find the red node?
推荐答案
这是有关如何解决问题的建议.
here is a suggestion on how to solve your problem.
- 符号:
- g图，g.v图顶点
- v,w,z:单个顶点
- e:单个边缘
- n:顶点数
- notation:
- g graph, g.v graph vertices
- v,w,z: individual vertices
- e: individual edge
- n: number of vertices
- 通过g所隐含的有向树中的方向和g的节点处的局部计算来补充g的边缘.
- 这些方向将表示节点(v -> w:v子级，w父级)之间的父子关系.
- 完全标记的树将包含一个度数为0的唯一节点，这是所需的根节点.您可能最终得到0个或多个根节点.
- complement the edges of g by orientations in the directed tree implied by g and the yet-to-be-found root node by local computations at the nodes of g.
- these orientations will represent child-parent-relationsships between nodes (v -> w: v child, w parent).
- the completely marked tree will contain a sole node with outdegree 0, which is the desired root node. you might end up with 0 or more than one root node.
假设图形/树结构(例如，邻接表)的标准表示形式
assumes standard representation of the graph/tree structure (eg adjacency list)
- g.v中的所有顶点最初都标记为未访问，尚未完成.
-
以任意顺序访问所有顶点.跳过标记为完成"的节点. 设v为当前访问的顶点.
- all vertices in g.v are marked initially as not visited, not finished.
visit all vertices in arbitrary sequence. skip nodes marked as 'finished'. let v be the currently visited vertex.
- 2.1从所有随机选择的e_0开始的顺时针方向依次扫描v的边缘，按边缘与e_0的角度顺序.
-
2.2.将相邻的边缘e_1=(v,w_1), e_2(v,w_2)定向为锐角. 相邻:根据它们与e_0包围的角度排序.
- 2.1 sweep through all edges linking v clockwise starting with a randomly chosen e_0 in the order of the edges' angle with e_0.
2.2. orient adjacent edges e_1=(v,w_1), e_2(v,w_2), that enclose an acute angle. adjacent: wrt being ordered according to the angle they enclose with e_0.
[注意:不能保证存在这样的对，请参阅第二条评论和最后一句话.如果没有锐角，则从2.下一个节点继续. ]
[ note: the existence of such a pair is not guaranteed, see 2nd comment and last remark. if no angle is acute, proceed at 2. with next node. ]
-
2.2.1边缘e_1, e_2的方向是已知的:
- w_1 -> v -> w_2:不可能，因为祖父母-儿童段会围成一个锐角
- w_1 <- v <- w_2:不可能，原因相同
-
w_1 <- v -> w_2:不可能，树中没有度数大于1的节点
- w_1 -> v -> w_2: impossible, as a grandparent-child-segment would enclose an acute angle
- w_1 <- v <- w_2: impossible, same reason
w_1 <- v -> w_2: impossible, there are no nodes with outdegree >1 in a tree
w_1 -> v <- w_2: 唯一可能的一对方向. e_1, e_2以前可能已经被定位.如果先前的方向违反了当前的分配，则问题实例没有解决方案.
w_1 -> v <- w_2: only possible pair of orientations. e_1, e_2 might have been oriented before. if the previous orientation violates the current assignment, the problem instance has no solution.
2.2.2这种分配意味着子图上的树结构，该子图由从w_1(w_2)到达的不包含e_1 ( e_2`的路径上的所有顶点所诱导.将两个诱导子树中的所有顶点标记为已完成
2.2.2 this assignment implies a tree structure on the subgraphs induced by all vertices reachable from w_1 (w_2) on a path not comprising e_1 (e_2`). mark all vertices in both induced subtrees as finished
[注意:子树结构可能违反角度约束.在这种情况下，问题无法解决. ]
[ note: the subtree structure might violate the angle constraints. in this case the problem has no solution. ]
2.3标记v.在顶点v完成步骤2.2之后，检查尚未分配方向的连接边数nc.
2.3 mark v visited. after completing steps 2.2 at vertex v, check the number nc of edges connecting that have not yet been assigned an orientation.
- nc = 0:这是您一直在寻找的根-但您必须检查解决方案是否与您的约束兼容.
-
nc = 1:将此边设为(v,z). 就像在树上一样，这条边的方向是v-> z.将v标记为完成.
- nc = 0: this is the root you've been searching for - but you must check whether the solution is compatible with your constraints.
nc = 1: let this edge be (v,z). the orientation of this edge is v->z as you are in a tree. mark v as finished.
- 2.3.1检查z是否标记为完成. 如果不是，请检查连接z的未定向边缘的数量nc2. nc2 = 1:对v取z，重复步骤2.3.
- 2.3.1 check z whether it is marked finished. if it is not, check the number nc2 of unoriented edges connecting z. nc2 = 1: repeat step 2.3 by taking z for v.
如果尚未找到根节点，则问题实例是不确定的: 随意调整其余未定向的边缘.
if you have not yet found a root node, your problem instance is ambiguous: orient the remaining unoriented edges at will.
备注
-
终止: 每个节点最多访问4次:
termination: each node is visited at max 4 times:
- 每2步一次
- 每个步骤2.2.2最多两次
- 每个步骤2.3最多一次
正确性:
- 围绕锐角的所有边缘均按步骤2.2.1定向
复杂度(时间):
- 访问每个节点:O(n);
-
在连接给定顶点的所有边上进行顺时针扫描需要对这些边进行排序. 因此，您需要在约束sum_i=1..m k_i = n下的m <= n顶点处的O( sum_i=1..m ( k_i * lg k_i ) ).
- visiting every node: O(n);
the clockwise sweep through all edges connecting a given vertex requires these edges to be sorted. thus you need O( sum_i=1..m ( k_i * lg k_i ) ) at m <= n vertices under the constraint sum_i=1..m k_i = n.
总共需要O ( n * lg n)，对于任何m <= n，给定sum_i=1..m k_i = n的sum_i=1..m ( k_i * lg k_i ) <= n * lg n(可通过应用滞后范围优化来证明).
in total this requires O ( n * lg n), as sum_i=1..m ( k_i * lg k_i ) <= n * lg n given sum_i=1..m k_i = n for any m <= n (provable by applying lagrange optimization).
[注意:如果您的树的度数受常数限制，则理论上您会在受影响的每个节点上按恒定的时间进行排序；在这种情况下总计:O(n)]
[ note: if your trees have a degree bounded by a constant, you theoretically sort in constant time at each node affected; grand total in this case: O(n) ]
子树标记: 如果实现为dfs，则此过程最多可访问图形中的每个节点2次.因此，用于调用此子例程的O(n)总计.
subtree marking: each node in the graph is visited at max 2 times by this procedure if implemented as a dfs. thus a grand total of O(n) for the invocation of this subroutine.
总计:O(n * lg n)
复杂度(空格):
- O(n)用于排序(顶点度不是常数约束).
- O(n) for sorting (with vertex-degree not constant-bound).
问题可能定义不清:
- 多种解决方案:例如斯坦纳树 没有解决方案:例如形状像双尖箭头(<->)
的图形
- multiple solutions: e.g. steiner tree
- no solution: e.g. graph shaped like a double-tipped arrow (<->)
更多推荐
无向图转换为树
发布评论