3

例如，如果我有这样的图表：

                     -- 528a - 526 -
                    /               \
380 - 404 - 420 - 522 - 530 - 526a - 686 - 564
                          \                /
                           ------ 540 -----

从开始（380）到结束（564）遍历它会导致以下路线

 1. 380 404 420 422 522 528a 526  686 564 
 2. 380 404 420 422 522 530  526a 686 564
 3. 380 404 420 422 522 530  540  564

我怎样才能简化路线的描述，同时它们仍然是独一无二的？换句话说：在 start 和 end 之间找到与 start 和 end 一起定义路由的节点？

在这个例子中，我希望它归结为这个结果。

 1. 380 404 420 422 522 528a 526  686 564  =>  380 528a 564 OR 380 526 564 
 2. 380 404 420 422 522 530  526a 686 564  =>  380 526a 564 
 3. 380 404 420 422 522 530  540  564      =>  380 540  564

我正在寻找一种不会通过遍历图形来进行反复试验的算法。

感谢您提供任何帮助或提示

4

1 回答 1

3

主意：

  • 将起始节点记录为永久。

  • 路径拆分后：

    • 如果它不是永久的，则删除最后记录的节点，并且

    • 记录当前节点。

  • 如果路径合并，则将最后一个节点设为永久。

  • 记录结束节点。

要检查路径是否分裂，您需要检查一个节点有多少个子节点（大多数图形实现应该存储它）。

要检查路径是否合并，您需要检查节点有多少父节点（大多数图形实现可能不会存储）。

使节点永久化的想法是防止在此处删除2或3：

    2       5
  /   \   /   \
1 - 3 - 4 - 6 - 7

我还必须补充一点，我不确定您为什么要记录开始和结束节点，因为这些对于您的所有示例都是相同的，除非它们对于其他示例可能不同。

例子：

Graph:
                     -- 528a - 526 -
                    /               \
380 - 404 - 420 - 522 - 530 - 526a - 686 - 564
                          \                /
                           ------ 540 -----

Input: 380 404 420 422 522 528a 526 686 564

Splits before 528a, so record it.
Make 528a permanent at 686.

Output: 380 528a 564


Input: 380 404 420 422 522 530  526a 686 564

Splits before 530, so record it.
Splits before 526a, so remove 530 and record 526a.
Make 526a permanent at 686.

Output: 380 526a 564


Input: 380 404 420 422 522 530  540 564

Splits before 530, so record it.
Splits before 540, so remove 530 and record 540.
Make 540 permanent at 564.

Output: 380 540 564
于 2013-09-06T09:04:51.543 回答