题目描述

给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）。那么可以得到旅程路线为：北京-＞上海，上海-＞大连，大连-＞西安，西安-＞成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。

分析

主要是要找到旅程的起点。

如何找到旅程的起点？
遍历Tickets，对于遍历到的key值，判断这个值是否在ReverseTickets中的key中存在，如果不存在，那么说明遍历到的Tickets中的key值就是旅途的起点。

理由就是，如果key在ReverseTickets中，那么该票就是中间站，而不是起点。

代码

  1. tickets = dict()
  2. tickets['西安'] = '成都'
  3. tickets['北京'] = '上海'
  4. tickets['大连'] = '西安'
  5. tickets['上海'] = '大连'
  8. reverseTickets = {value: key for key, value in tickets.items()}
  10. start = None
  11. # 找到起点
  12. for k, v in tickets.items():
  13.     if k not in reverseTickets:
  14.         start = k
  15.         break
  17. if start is None:
  18.     print('输入不和理')
  19. else:
  20.     # 从起点出发按照顺序遍历路径
  21.     to = tickets[start]
  22.     print(start + '->' + to, end=' ')
  24.     start = to
  25.     to = tickets[to]
  26.     while to is not None:
  27.         print(',' + start + '->' + to, end=' ')
  28.         start = to
  29.         to = tickets.get(to, None)