如何在路线仍然唯一的情况下简化路线的描述

本文关键字：唯一 情况下 描述 化路 何在路 在路 | 更新日期: 2023-09-27 18:30:33

如果我举个例子，有一个这样的图表：

                     -- 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

如何在路线仍然唯一的情况下简化路线的描述？换句话说：在开始和结束之间找到定义路线以及开始和结束的节点？

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

 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

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

感谢您的任何帮助或提示

如何在路线仍然唯一的情况下简化路线的描述

想法：

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

  • 路径拆分后：

    • 如果最后一个记录的节点不是永久性的，则将其删除，并且

    • 记录当前节点。

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

  • 记录终端节点。

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

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

使节点永久化的想法是防止在此处删除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
相关文章：