合并线性列表-重建铁路网
我需要从任意站点请求的单程序列重建铁路网中的站点序列。数据中没有给出方向。但是每个请求都会返回一个终止停止。单次行程的序列可以有间隙。(end-)结果总是线性列表-不允许forking。
例如：
从请求的站点"4“开始的结果行程：
4 - 3 - 2 - 1 4 - 1 4 - 5 - 6 4 - 8 - 9 4 - 6 - 7 - 8 - 9
手动重新排序：
1 - 2 - 3 - 4 1 - 4 - 4 - 5 - 6 - 4 - 8 - 9 - 4 - 6 - 7 - 8 - 9
合并后的结果应为：
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
开始/停止: 1，9
有没有一种算法来计算得到的“珍珠绳”列表？我试着用perls的图形模块来解决这个问题，但是没有成功。我的算法方面的书也帮不上忙。
我认为，在病理情况下，根据输入数据，多种解决方案是可能的。
也许有人有办法解决这个问题！
正如你在答案中看到的，有不止一种解决方案。下面是一个真实的数据集：
2204236 -> 2200007 -> 2200001
2204236 -> 2203095 -> 2203976 -> 2200225 -> 2200007 -> 2200001
2204236 -> 2204805 -> 2204813 -> 2204401 -> 2219633 -> 2204476 -> 2202024 -> 2202508 -> 2202110 -> 2202026
2204236 -> 2204813 -> 2204401 -> 2219633 -> 2202508 -> 2202110 -> 2202026 -> 3011047 -> 3011048 -> 3011049
2204236 -> 2204813 -> 2204401 -> 2219633 -> 2204476 -> 2202024 -> 2202508 -> 2202110 -> 2202352 -> 2202026
2204236 -> 2204813 -> 2204401 -> 2219633 -> 2204476 -> 2202024 -> 2202508 -> 2209637 -> 2202110用perl解决示例数据问题：
use Graph::Directed;
use Graph::Traversal::DFS;
my $g = Graph::Directed->new;
$g->add_path(1,2,3,4);
$g->add_path(1,4);
$g->add_path(4,5,6);
$g->add_path(4,8,9);
$g->add_path(4,6,7,8,9);
print "The graph is $g\n";
my @topo = $g->toposort;
print "g toposorted = @topo\n";输出
> The graph is 1-2,1-4,2-3,3-4,4-5,4-6,4-8,5-6,6-7,7-8,8-9
> g toposorted = 1 2 3 4 5 6 7 8 9使用另一个方向
$g->add_path(4,3,2,1);
$g->add_path(4,1);
$g->add_path(4,5,6);
$g->add_path(4,8,9);
$g->add_path(4,6,7,8,9);揭示了第二种解决方案
The graph is 2-1,3-2,4-1,4-3,4-5,4-6,4-8,5-6,6-7,7-8,8-9
g toposorted = 4 3 2 1 5 6 7 8 9回答 2
Stack Overflow用户
发布于 2016-04-20 20:47:03
处理图中的列表节点链接。4-3-2-1应该意味着4必须在3之前，3在2之前，2在1之前。所以添加从4到3，3到2，2到1的弧线。当你得到所有这些之后，你就在结果图上运行拓扑排序(在维基百科上查找它)。这将保证你得到的顺序将始终尊重你得到的偏序。
唯一不能找到解决方案的情况是数据本身相互矛盾(如果您有4-3-2和4-2-3，就没有可能的排序)。
你说得对，确实有很多案例。对于您的示例，另一个很好的解决方案是4-5-6-7-8-9-3-2-1。
Stack Overflow用户
发布于 2016-04-20 21:38:19
终端停止站是连接节点，它将图分割成多个分区:分区内的所有节点彼此可达，不同分区中的节点只能通过已知的终端停止站到达。在您的示例中，分区的数量是2，但可能要大得多，例如，考虑星型结构1 - 2, 1 - 3, 1 - 4, 1 - 5。
首先，您需要枚举分区。您将您的图视为无向图，并在每个方向上从停止站运行DFS。在第一次运行时发现分区#1，在第二次运行时发现分区#2，依此类推。
然后，将您的图视为有向图，并将stop station作为所有分区的根节点，并为每个分区运行拓扑排序(TS)。
可能的结果：
其中一个分区的
- TS失败。这意味着没有分区的solution.
- Number是一个，并且它的TS成功。解决方案是唯一的，
- 的分区数不止一个，所有分区TS都成功。这意味着有多种解决方案。要获得任何一个有效的结果，您可以选择某个分区并声明它包含另一个终端站。所有其他分区都插入到任意一对节点之间的第一个分区中。
https://stackoverflow.com/questions/36743561
复制相似问题
腾讯云开发者
