[LeetCode]Bus Routes

题目链接

找最短路径的问题，我们第一个想到的就应该是BFS。但是这里的问题是，我们如何建图。如果用站点当节点，bus的线路当edge的话，我们对不同的route染色，我们需要DFS找到经过最少颜色的路径，会比较麻烦。相反，如果我们用bus当节点，如果两个bus经过相同的节点我们在他们之间连一条线，我们从所有经过起始站点的bus开始bfs，直到扫到route包含终站点的bus，就是我们最少需要换乘的次数。时间复杂度O(n + m)，n为bus的数量，m为站点的数量。代码如下：