从门票打印路线

Question

今天我遇到了一个我无法解决的问题。

经常旅行者收集他所有的旅行门票。 一张票只有2个属性，开始旅程地点名称和目的地名称。从德里到纽约的例子。 在年底，旅行者将所有的票都放在一起，并尝试绘制全年的旅程。以可读格式打印他可能的旅行路线。他不记得他的起始位置。他可以多次访问一个位置，也可以多次来回地点。

最初我认为它可以简单地通过制作一张图（票-A到B意味着一个有向边A-> B）并使用一个简单的深度第一次遍历从一个不等于0（??）的节点来解决。但后来我意识到它不是获得解决方案的正确方法，因为它可能会打印随机未连接的路线。
请建议正确的方法继续。

Answer 1

首先你应该检查你的图是否有欧拉迹或欧拉循环。

有向图具有欧拉循环当且仅当每个顶点有 在度和出度，和所有其顶点具有非零 度等于属于单个强连通分量。等价地，有向图具有欧拉循环当且仅当它可以分解为边缘不相交有向循环并且其具有非零度的所有顶点 属于单个强连通分量。

有向图具有欧拉线索当且仅当至多一个顶点 具有（出度） - （入度）= 1，至多一个顶点具有（入度） - （ out-degree）= 1，则每个其他顶点具有相等的入度和出度，且其非零度的所有顶点都属于底层无向图的单连通分量。

如果您的图形具有欧拉循环，则可以从任意节点启动DFS，并且可以确保您的路径是正确的。

如果你的图具有欧拉线索，首先找到(out-degree) − (in-degree) = 1节点，并调用它source与(in-degree) − (out-degree) = 1找到节点，并调用它sink。您应该从source开始您的DFS，并尽可能避免去sink。这意味着无论何时在进入节点sink和某个其他节点之间有一个选项，只有当您没有其他选项（不完全正确但使其更简单）时，您应该转到其他节点并使用sink节点。通过这种方式，您可以确定您最终得到了正确的线索。