飞行旅行者航空公司

Question

我对这个问题的算法有一点问题。

问题陈述：

飞行旅行者航空公司(FTAir)想要一个程序来处理客户从某个始发地城市飞往某个目的地城市的请求。对于每个客户，指出是否存在从始发地城市到目的地城市的FTAir航班序列，并生成航班的行程序列。输入:三个输入文本文件，指定所有航班信息，如下所示：·FTAir服务的城市名称(至少15个城市)。·城市名称对；每对城市名称代表FTAir的一个航班的始发地和目的地。·一对城市名称；每一对代表一个从某个始发城市飞往某个目的地的请求(至少5个不同场景的请求)。每个请求都被认为是单程飞行。

规则：

找到一条从起始城市到目的地城市的路径，如果关于它访问cities.Do的顺序的信息没有访问超过once.If的城市有多条路径，您可以将它们全部列出并查找访问次数最少的城市。(可选)。此外，通过堆栈(使用链表)和递归！

我的方法是：

首先，我们需要一个数据结构来包含所有的输入文本文件。假设我们在一个数组中有城市的名称，在一个2D数组中有一对城市(origin --> destination)，在一个2D数组中也有reuqest。

对于请求矩阵中的退出路径，它必须由我们的FTAir提供服务，因此对于每个请求，我们需要在城市数组中搜索起点和目的地，如果两者都匹配，则只需进行下一步。

找到匹配后，我们必须将请求来源映射到航班来源，即我们必须检查是否有从所需来源出发的任何航班，如果没有，则再次没有旅行请求的可能路径。

但如果有匹配，我们将该起点放到堆栈中，检查它的目的地，并将其与请求的目的地进行比较，如果匹配，我们就得到一个直达航班，如果不匹配，则将其放到堆栈中，并在航班的2D数组中查找目的地作为起点。继续执行该过程，直到出现匹配项。但是如果我们访问一个城市两次呢？检查您在堆栈中输入的数据，如果发现重复数据，则中止！

我不能将我的想法转换成代码，这里有人能帮我吗？

Answer 1

因此，让我们通过一个例子来看看这个问题。

我们有以下航空公司要去的城市列表

1. Cambridge (A)
2. Harvard   (B)
3. Hampshire (C)
4. Toronto   (D)
5. Montreal  (E)
6. Quebec    (F)

现在，我们有了航班往返的城市对的映射。

1. (A,B)
2. (C,D)
3. (D,E)
4. (B,C)

现在，如果把这个画在纸上，我们有5个城市的地图看起来像这样

A -> B -> C -> D -> E

所以现在如果你问我是否想要从A到C，有没有路径，你可以简单地启动一个DFS(A)，如果你到达C，那么答案是肯定的。

假设我问是否有一条从A到F的路由，那么应用DFS(A)会给出false，我的答案是否。

现在，要检查您是否已经访问过某个城市，只需保留一个gloval数组作为visited[]，并且在使用DFS方法时，继续将这些城市标记为已访问。

希望这能消除你的疑虑。在下面的评论部分提出更多问题。